Классы P и NP

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

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

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

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

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

См. также

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

Литература

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

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