DAA — теорема Кука

Стивен Кук представил четыре теоремы в своей статье «Сложность процедур доказательства теорем». Эти теоремы изложены ниже. Мы понимаем, что в этой главе используются многие неизвестные термины, но у нас нет возможности обсуждать все подробно.

Ниже приведены четыре теоремы Стивена Кука:

Теорема-1

Если набор S строк принят некоторой недетерминированной машиной Тьюринга в течение полиномиального времени, то S сводится к P к {тавтологиям DNF}.

Теорема-2

Следующие множества P-сводимы друг к другу в парах (и, следовательно, каждый имеет одинаковую полиномиальную степень сложности): {тавтологии}, {тавтологии DNF}, D3, {пары подграфов}.

Теорема-3

• Для любого T _Q (k) типа Q  mathbf fracTQ(k) frac sqrtk(logk)2$\ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}}$ $ неограниченный

• Существует T _Q (k) типа Q такой, что TQ(k) leqslant2k(logk)2$T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2}$

Для любого T _Q (k) типа Q  mathbf fracTQ(k) frac sqrtk(logk)2$\ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}}$ $ неограниченный

Существует T _Q (k) типа Q такой, что TQ(k) leqslant2k(logk)2$T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2}$

Теорема-4

Если множество строк S принимается недетерминированной машиной в течение времени T (n) = 2 ⁿ , и если T _Q (k) является честной (то есть счетной в реальном времени) функцией типа Q , то существует постоянная K , поэтому S может быть распознан детерминированной машиной за время T _Q (K8 ⁿ ) .

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

Во-вторых, он акцентировал внимание на классе NP задач решения, которые могут быть решены за полиномиальное время с помощью недетерминированного компьютера. Большинство неразрешимых проблем относятся к этому классу NP.

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

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