Ууууу, докторский комп флешбек. Хорошо, здесь идет.
Мы начнем с идеи решения проблемы, задачи, для которой алгоритм всегда может ответить «да» или «нет». Нам также нужна идея двух моделей компьютера (на самом деле, машины Тьюринга): детерминированной и недетерминированной. Детерминированный компьютер - это обычный компьютер, о котором мы всегда думаем; недетерминированный компьютер - это тот компьютер, к которому мы привыкли, за исключением того, что он имеет неограниченный параллелизм, так что каждый раз, когда вы приходите на ветку, вы запускаете новый «процесс» и исследуете обе стороны. Как сказал Йоги Берра, когда вы приходите к развилке на дороге, вы должны взять ее.
Решение проблемы в P, если существует известный алгоритм за полиномиальное время, чтобы получить этот ответ. Решение проблемы в NP, если для недетерминированного автомата, чтобы получить ответ, существует известный алгоритм полиномиального времени.
Проблемы, о которых известно, что они есть в P, тривиальны в NP - недетерминированная машина просто никогда не беспокоится о том, чтобы внедрить другой процесс, и действует точно так же, как детерминистская. Есть проблемы, о которых известно, что их нет ни в P, ни в NP; простой пример - перечислить все битовые векторы длины n. Независимо от того, что это занимает 2 n шагов.
(Строго говоря, проблема решения в NP, если нодерминистская машина может прийти к ответу за многократное время, а детерминированная машина может проверить , что решение является правильным за много времени.)
Но есть некоторые проблемы, о которых известно, что они есть в NP, для которых не известен детерминистический алгоритм с многократным временем; Другими словами, мы знаем, что они в NP, но не знаем, есть ли они в P. Традиционным примером является версия задачи о решении задачи коммивояжера (TSP): учитывая города и расстояния, есть ли маршрут, который охватывает все города, возвращаясь к начальной точке, на расстоянии менее x ? Легко в недетерминированной машине, потому что каждый раз, когда недетерминированный коммивояжер приходит на развилку дороги, он берет его: его клоны направляются в следующий город, который они не посетили, и в конце они сравнивают записи и смотрят любой из клонов занимал расстояние менее x .
(Тогда экспоненциально много клонов сражаются за него, за что должны быть убиты.)
Неизвестно, находится ли TSP для принятия решения в P: не существует известного решения с разным временем, но нет никаких доказательств того, что такого решения не существует.
Теперь еще одна концепция: учитывая задачи решения P и Q, если алгоритм может преобразовать решение для P в решение для Q за полиномиальное время, говорят, что Q является многократным приводимым ( или просто сводится) к П.
Проблема является NP-полной, если вы можете доказать, что (1) она находится в NP, и (2) показать, что она за многократное время сводится к задаче, уже известной как NP-полная. (Самая сложная часть этого - обеспечить первый пример NP-полной проблемы: это было сделано Стивом Куком в Теорема Кука .)
На самом деле, это говорит о том, что если кто-то когда-нибудь найдет решение по одному разу с полным временем выполнения, он автоматически получит его для всех проблем с NP-завершением; это также будет означать, что P = NP.
Проблема NP-сложна тогда и только тогда, когда она "по крайней мере такая же", как NP-полная проблема. Более обычный коммивояжёр Задача поиска кратчайшего маршрута - NP-сложная, а не строго NP-полная.