Классы P и NP

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

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

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

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

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

См. также

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

Литература

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

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