Классы P и NP

Классы [math]\displaystyle{ \cal P }[/math] и [math]\displaystyle{ \cal NP }[/math] ([math]\displaystyle{ cal P }[/math] and [math]\displaystyle{ \cal NP }[/math] classes) - Через [math]\displaystyle{ {\cal P} }[/math] обозначается множество всех языков, допускаемых детерминированной машиной Тьюринга (ДМТ) с полиномиальной временной сложностью, а через [math]\displaystyle{ {\cal NP} }[/math]~--- множество всех языков, допускаемых недетерминированной машиной Тьюринга ([math]\displaystyle{ MT }[/math]) с полиномиальной временной сложностью.

Имеется определенное соответствие между задачами распознавания и языками, которое осуществляется с помощью кодирования, обычно применяемого для представления задачи при ее решении на ЭВМ. Указанное соответствие позволяет отождествлять решение задачи распознавания свойств с распознаванием соответствующего языка: говорят, что задача принадлежит [math]\displaystyle{ {\cal P} }[/math] (или [math]\displaystyle{ {\cal NP} }[/math]), если соответствующий язык принадлежит [math]\displaystyle{ {\cal P} }[/math] (или [math]\displaystyle{ {\cal NP} }[/math]).

Класс [math]\displaystyle{ \cal P }[/math] --- это так называемые легко решаемые задачи. Однако большинство из задач дискретной математики принадлежит [math]\displaystyle{ \cal NP }[/math]. Это так называемые переборные задачи. Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть разрешена алгоритмом полного перебора. Так, в задаче о выполнимости логических формул решение можно отыскать среди [math]\displaystyle{ 2^n }[/math] булевых векторов длины [math]\displaystyle{ n }[/math], где [math]\displaystyle{ n }[/math] --- число переменных формулы, и, перебрав это экспоненциальное множество векторов при вычислении значения формулы, мы обязательно решим задачу. Переборный алгоритм имеет экспоненциальную временную сложность и может хорошо работать на практике для небольших размеров задачи. Но с ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой рассмотренным методом перебора.

Поэтому в конечной области аналогом алгоритмической неразрешимости является необходимость перебора экспоненциального числа вариантов, а аналогом разрешимости --- существование алгоритма решения задачи за полиномиальное время на детерминированном вычислительном устройстве.

При этом [math]\displaystyle{ {\cal NP} }[/math]-полные задачи являются эталоном сложности класса переборных задач, они являются "самыми трудными" в классе [math]\displaystyle{ {\cal NP} }[/math]. На центральный вопрос, можно ли исключить перебор при решении дискретных задач, можно ответить, либо построив полиномиальный алгоритм решения одной из [math]\displaystyle{ {\cal NP} }[/math]-полных задач, либо доказав невозможность построения эффективного алгоритма для этой задачи. До настоящего времени эта важная проблема дискретной математики остается открытой.

См. также Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Задача легко разрешимая, Метод локальной замены, Метод построения компонент, Задача распознавания свойств, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), [math]\displaystyle{ \cal NP }[/math]-полная задача, Труднорешаемая задача.

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]