Akademik

один из наиболее важных видов массовых проблем. Р. п. данного множества А конструктивных объектов (относительно нек-рого объемлющего множества V конструктивных объектов) наз. проблему построения алгоритма, распознающего по всякому объекту из множества V, принадлежит ли он множеству А или нет. Р. п. (более подробно – Р. п. для доказуемости) формальной системы (или исчисления) наз. Р. п. множества всех доказуемых формул этой системы относительно множества всех ее формул. Семантич. Р. п. (или Р. п. для истинности) интерпретированной формальной системы (формализованного языка) наз. Р. п. множества всех истинных формул системы относительно множества всех ее формул. (Для обозначения понятия "проблема разрешения" долгое время применялся термин "проблема разрешимости", однако этим термином правильнее обозначать проблему: "имеет ли решение данная Р. п.".)

Р. п. множеств совпадают по существу и с проблемами распознавания свойств.

Проблемой распознавания заданного св-ва (для объектов из заданной совокупности конструктивных объектов) наз. проблему построения алгоритма, распознающего по всякому объекту из заданной совокупности, обладает он заданным св-вом или нет. Всякая проблема распознавания св-ва есть в то же время Р. п. множества всех тех объектов, к-рые обладают этим св-вом. В свою очередь Р. п. множества есть проблема распознавания св-ва принадлежности к этому множеству. В частности, Р. п. для доказуемости является проблемой распознавания доказуемости, а Р. п. для истинности есть проблема распознавания истинности.

См. также ст. Алгоритм, Массовая проблема, Метатеория и лит. при них.