Классы P и NP

Материал из WikiGrapp
Перейти к:навигация, поиск

Классы \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}-полных задач, либо доказав невозможность построения эффективного алгоритма для этой задачи. До настоящего времени эта важная проблема дискретной математики остается открытой.

См. также

Литература

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