Задача распознавания свойств

Задача распознавания свойств (Decision problem) — такие массовые задачи, которые имеют только два возможных решения "да" или "нет". Задача распознавания свойств состоит просто из двух множеств: всех ее индивидуальных задач и тех из них, ответ для которых "да". Поэтому стандартная форма, применяемая для описания задачи распознавания свойств, состоит из двух частей: условия задачи в терминах подходящих объектов (множеств, графов, функций, чисел и т.д.) и вопроса, предполагающего один из возможных ответов — "да" или "нет".

Имеется определенное соответствие между задачами распознавания и языками, которое осуществляется с помощью кодирования, обычно применяемого для представления задачи при ее решении на ЭВМ. Выбрав способ кодирования всех возможных индивидуальных задач в виде цепочек в некотором фиксированном алфавите, можно переформулировать массовую задачу как задачу распознавания языка, состоящего из всех цепочек, представляющих индивидуальные задачи, ответ для которых — "да". При этом естественно требовать, чтобы способ кодирования давал "сжатое" представление индивидуальных задач и допускал "декодирование". Указанное соответствие позволяет отождествлять решение задачи распознавания свойств с распознаванием соответствующего языка.

Рассматриваются определенные "стандартные" представления задач, которые удовлетворяют описанным выше требованиям, и говорится, что задача принадлежит [math]\displaystyle{ {\mathcal P} }[/math] или [math]\displaystyle{ {\mathcal NP} }[/math], если ее стандартный код принадлежит классу языков [math]\displaystyle{ {\mathcal P} }[/math] или [math]\displaystyle{ {\mathcal NP} }[/math] соответственно.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.