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

Во-первых, давайте покажем, что все, что можно проверить за полиномиальное время, можно решить за недетерминированное полиномиальное время. Предположим, у вас есть некоторый алгоритм 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), поскольку оно просто выполняет все шаги недетерминированного вычисления.

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

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

Учитывая L = {w : expression w is satisfiable} и время для n переменных:

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

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

Класс NP предназначен для выделения понятия «верифицируемости» полиномиального времени. NP — это класс языков, которые имеют полиномиальные верификаторы времени.