DAA-クックの定理
Stephen Cookは、彼の論文「The Complexity of TheoremProvingProcedures」で4つの定理を提示しました。これらの定理は以下のとおりです。この章では多くの未知の用語が使用されていることを理解していますが、すべてを詳細に説明する余地はありません。
以下はスティーブンクックによる4つの定理です-
定理-1
セットの場合 S 文字列の数は、多項式時間内に非決定性チューリングマシンによって受け入れられます。 S {DNFトートロジー}にP還元可能です。
定理-2
次のセットは、ペアで相互にP還元可能です（したがって、それぞれが同じ多項式の難易度を持ちます）：{トートロジー}、{DNFトートロジー}、D3、{サブグラフペア}。
定理-3
どんな場合でも TQ(k) タイプの Q、$ \ mathbf {\ frac {T_ {Q}（k）} {\ frac {\ sqrt {k}} {（log \：k）^ 2}}} $は無制限です
あります TQ(k) タイプの Q $ T_ {Q}（k）\ leqslant 2 ^ {k（log \：k）^ 2} $のように
定理-4
文字列のセットSが時間内に非決定性マシンによって受け入れられた場合 T(n) = 2n、 で、もし TQ(k) タイプの正直な（つまりリアルタイムの可算）関数です Q、次に定数があります K、 そう S 時間内に決定論的マシンによって認識できます TQ(K8n)。
最初に、彼は多項式の時間計算量の重要性を強調しました。これは、ある問題から別の問題への多項式時間の短縮がある場合、これにより、2番目の問題の多項式時間アルゴリズムを最初の問題の対応する多項式時間アルゴリズムに変換できることを意味します。
第二に、彼は非決定論的コンピューターによって多項式時間で解くことができる決定問題のクラスNPに注意を向けました。困難な問題のほとんどは、このクラスNPに属します。
第三に、彼は、NPの1つの特定の問題には、NPの他のすべての問題を多項式で還元できるという特性があることを証明しました。充足可能性問題が多項式時間アルゴリズムで解決できる場合、NPのすべての問題も多項式時間で解決できます。NPの問題が手に負えない場合、充足可能性問題は手に負えないものでなければなりません。したがって、充足可能性問題はNPで最も難しい問題です。
第4に、クックは、NPの他の問題が、NPの最も難しいメンバーであるというこの特性を充足可能性問題と共有する可能性があることを示唆しました。