Начнем с «недетерминированного». Детерминированная машина может находиться в одном состоянии одновременно. Мы действительно можем сделать их. Недетерминированная машина - это теоретическая конструкция, которая может находиться в нескольких состояниях одновременно. (Здесь есть сходство с квантовыми вычислениями, но для наших целей они вводят в заблуждение. Не обращайте на них внимания.)
Если мы хотим решить проблему с помощью детерминированной машины, мы запускаем ее, и она проходит серию шагов, чтобы попытаться найти проблему. Если мы моделируем с использованием недетерминированной машины, она может пройти все возможные серии шагов одновременно.
Множество проблем, с которыми мы столкнемся, - это проблемы с решением: с учетом формулировки проблемы, есть решение или нет. Найти решение или сообщить, что его нет. Например, предположим, что у вас есть набор логических выражений: A или не-B, B или C или D, не-D или A или B, .... Учитывая произвольный набор, вы можете найти значения истинности для всех переменных так что все утверждения верны?
Теперь давайте рассмотрим P. Предположим, что мы представляем размер задачи с помощью n. Размером может быть количество городов в задаче коммивояжера, количество логических утверждений в задаче выше, что угодно. При определенном n проблема потребует определенного количества ресурсов для решения в данной системе. Теперь, если мы удвоим ресурсы или вычислительные возможности, что произойдет с размером проблемы, которую мы можем решить? Если задача имеет полиномиальную сложность, что означает в P, размер увеличивается на определенную долю. Это может удвоиться, или подняться на 40%, или на 10%. Напротив, если это имеет экспоненциальную сложность, размер увеличивается на определенное число. Обычно мы думаем о P-задачах как о разрешимых, а экспоненциальные - о неразрешимых по мере того, как проблемы становятся большими, хотя это упрощение. С неформальной точки зрения, полиномиальная сложность заключается в том, что можно последовательно разобраться в проблеме, а в экспоненциальной - рассмотреть все возможные комбинации.
Предположим, что мы можем решить проблему за полиномиальное время на детерминированной машине. Проблема в P. Предположим, что мы можем решить ее за полиномиальное время на недетерминированной машине, что аналогично возможности проверки предложенного решения за полиномиальное время на детерминированной машине. Тогда проблема в NP. Хитрость в том, что мы не можем создавать настоящие недетерминированные машины, поэтому тот факт, что проблема в NP, не означает, что ее практично решить.
Теперь перейдем к NP-завершению. Все проблемы в P есть в NP. Для задач A и B в NP мы могли бы сказать, что если A находится в P, то же самое происходит и с B. Это делается путем нахождения способа переформулировать B как проблему A. NP-полная проблема - это такая проблема, что, если она есть в P, каждая проблема в NP находится в P. Как вы можете догадаться, найти способ переформулировать каждую возможную проблему как одну конкретную проблему было нелегко, и я буду просто скажем, что проблема с логическими утверждениями выше (проблема удовлетворенности) была первой доказанной NP-полной. После этого было проще, поскольку нужно было только доказать, что если проблема C в P, то и Удовлетворенность.
Обычно считается, что есть проблемы, которые есть в NP, но не в P, и недавно было опубликовано доказательство (которое может или не может быть действительным). В этом случае программы, завершенные NP, являются самыми сложными проблемами в NP.
Есть проблемы, которые не вписываются в эту форму. Задача коммивояжера, как обычно, состоит в том, чтобы найти самый дешевый маршрут, соединяющий все города. Это не проблема решения, и мы не можем проверить любое предлагаемое решение напрямую. Мы можем сформулировать это как проблему решения: учитывая стоимость C, есть ли маршрут дешевле, чем C? Эта проблема является NP-полной, и, немного поработав, мы можем решить исходную TSP примерно так же легко, как измененную, NP-полную форму. Следовательно, TSP является NP-сложным, поскольку он по меньшей мере так же сложен, как и NP-полная проблема.