На этом шаге мы рассмотрим понятие задачи распознавания.
Задачи обычно формулируются так: дан набор исходных данных X; требуется найти результат Y, удовлетворяющий условиям задачи. Для некоторых задач в качестве результата удобно рассматривать только значения "да" и "нет". Такие задачи формулируются как вопрос. Например, задача синтаксического анализа текста программы X: "Соответствует ли программа X правилам языка Паскаль?". Множество всех возможных программ L разделяется на два подмножества Lyes (множество всех правильных программ, ответ "да") и Lno (множество всех остальных программ, ответ "нет"). Алгоритм, решающий задачу, т. е. отвечающий "да" или "нет", по существу распознает, принадлежит ли программа X множеству Lyes. То же можно сказать и о других задачах с двумя возможными ответами. Поэтому такие задачи называются задачами распознавания или, точнее, задачами распознавания свойств. Имеется в виду свойство, которым обладает (или не обладает) вход X.
С точки зрения математической логики задаче распознавания свойств соответствует предикат P(Х).
Если, формулируя задачу, настраиваться на то, что она будет решаться алгоритмическим способом с помощью некоторого вычислителя (а не с помощью, например, озарения), то следует договориться, что исходные данные X будут задаваться на языке, понятном вычислителю. Пусть A - алфавит символов, воспринимаемых вычислителем, L - А* - множество всех возможных цепочек (слов) в алфавите A. Тогда Lyes - множество слов, кодирующих вход X, для которых вычислитель выдает ответ "да". Поскольку в теории формальных языков множество Lyes⊂L называется языком, то любую задачу распознавания можно сформулировать как задачу распознавания языка. Этот вывод нам потребуется далее при доказательстве теоремы С.Кука.
На следующем шаге мы рассмотрим понятие полиномиальной сводимости.
