Класс NP

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Таким образом, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.

Примеры задач экспоненциальной сложности:

- построение всех подмножеств данного множества;

- задачи распознавания правильных выражений в несложных языках.

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

К задачам класса NP относятся, в частности:

- решение систем уравнений с целыми переменными, известная задача Диофанта, датируемая 410 г;

- построение цикла Гамильтона, то есть цикла, проходящего по одному разу через все вершины данного графа;

- составление расписаний и раскрасок;

- ряд задач оптимизации;

- ряд задач диагностики.

Предельно коротко и нестрого (зато интуитивно) классы P и NP можно описать так: P - это вычислительные задачи, которые легко решить; NP - задачи, для которых легко проверить, верно ли предполагаемое решение. Перейдем к более точным формулировкам.