Недетерминизм в сравнении с проверяемостью за полиномиальное время

Question

Я читал, что проблема NP может быть проверена за полиномиальное время или, что то же самое, разрешима за полиномиальное время с помощью недетерминированной машины Тьюринга. Почему эти определения эквивалентны?

Answer 1

Во-первых, давайте покажем, что все, что может быть проверено за полиномиальное время, может быть решено за недетерминированное полиномиальное время. Предположим, у вас есть некоторый алгоритм P(x, y), который решает, проверяет ли y x, и где P выполняется за время O (| x |^k) для некоторой константы k. Время выполнения этого алгоритма является полиномиальным по x, что означает, что он может просматривать только многочленно много битов y. Тогда вы могли бы построить этот недетерминированный алгоритм полиномиального времени, который решает проблему:

1. Недетерминистически угадать строку y длины O (| x |^k).
2. Детерминистически запустите P(x, y) и выведите все, что он говорит.

Это выполняется за недетерминированное полиномиальное время, потому что y строится за недетерминированное полиномиальное время, а затем P(x, y) выполняется за полиномиальное время. Если есть y, который проверяет x, эта машина может недетерминированно угадать его. В противном случае догадка не сработает, и машина выдаст НЕТ.

Другое направление сложнее. Предположим, что существует недетерминированный алгоритм P(x), который выполняется за недетерминированное время O (| x |^k) для некоторой константы k. Этот недетерминированный алгоритм на каждом этапе выбирает один из c различных вариантов того, что делать дальше. Следовательно, вы можете создать программу проверки Q(x, y), где y кодирует то, что нужно сделать на каждом шаге вычисления P. Затем она может моделировать P(x), просматривая варианты, закодированные в y, чтобы определить, какой шаг взять дальше. Это будет выполняться за детерминированное время O (| x |^k), потому что оно просто выполняет все шаги в недетерминированных вычислениях.

Надеюсь это поможет!

Answer 2

Возможно, этот пример дает намек:

Данный L = {w : expression w is satisfiable}и время для n переменные:

• Угадай назначение переменных O(n)
• Проверьте, удовлетворительно ли это задание O(n)
• Общее время: O(n)

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

Класс NP предназначен для выделения понятия "проверяемости" за полиномиальное время. NP - это класс языков, имеющих полиномиальные верификаторы.