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

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

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

Теорема-1

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

Теорема-2

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

Теорема-3

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

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

Теорема-4

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

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

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

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

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