クック・レヴィン定理

計算複雑性理論において、クック・レビンの定理（クックの定理とも呼ばれる）は、ブール充足可能性問題はNP 完全であると述べている。つまり、この問題はNPに属し、 NP に属するあらゆる問題は、決定論的チューリングマシンによって多項式時間でブール充足可能性問題に 簡約できる。

この定理はスティーブン・クックとレオニード・レビンにちなんで名付けられました。証明はリチャード・カープによるもので、クックによる以前の証明（異なる還元可能性の概念を使用）に基づいています。^[1]

この定理の重要な帰結は、ブール充足可能性を解決するための決定論的多項式時間アルゴリズムが存在する場合、すべてのNP問題は決定論的多項式時間アルゴリズムによって解決できるということです。したがって、ブール充足可能性のためのそのようなアルゴリズムが存在するかどうかという問題は、 P 対 NP 問題と同等であり、これは理論計算機科学において依然として最も重要な未解決問題であると広く考えられています。

NP完全性の概念は、1960年代後半から1970年代前半にかけて、北米とソ連の研究者によって並行して発展した。1971年、スティーブン・クックは、新設されたACM計算理論シンポジウムの会議論文集に「定理証明手順の複雑さ」^[2]を発表した。リチャード・カープのその後の論文「組合せ問題間の縮約可能性」^[1]は、 21のNP完全問題のリストを示し、クックの論文への関心を新たにした。カープはまた、NP完全性の現在の定義（すなわち、多項式時間の多対一縮約による）で使用される完全性の概念を導入した。クックとカープは、この研究により それぞれチューリング賞を受賞した。

NP完全性への理論的関心は、 1975年に特定のオラクルマシンモデルでNP問題を解くには指数時間が必要であることを示したセオドア・P・ベイカー、ジョン・ギル、ロバート・ソロベイの研究によっても高まりました。つまり、すべての指数以下の決定論的時間複雑性クラスTに対して、相対化複雑性クラスNP ^{AがT A}のサブセットではないようなオラクルAが存在するということです。特に、このオラクルでは、P ^A  ≠ NP ^Aです。^[3]

ソ連では、ベイカー、ギル、ソロベイの結果と同等の結果が1969年にM.デクティアルによって発表されました。^[4]その後、レオニード・レビンの論文「普遍的探索問題」^[5]は1973年に発表されましたが、講演では数年前から言及され、出版のために提出されていました。

レビンのアプローチは、単に存在を決定するのではなく、解決策を見つけることを必要とする探索問題を考慮した点で、クックやカープのアプローチとは少し異なっていました。彼は、そのような NP 完全な探索問題、または普遍的な問題を 6 つ示しました。さらに、彼はこれらの問題のそれぞれについて、最適な時間で問題を解決するアルゴリズムを発見しました (特に、これらのアルゴリズムは、 P = NPの場合にのみ多項式時間で実行されます)。

決定問題がNPに属するのは、非決定性チューリングマシンによって多項式時間で決定できる場合です。

ブール充足可能性問題の例としては、ブール演算子を使用してブール変数を組み合わせたブール式が挙げられます。このような式は、式全体が真となるような真理値の変数への割り当てがある場合に充足可能です。

NP の任意の決定問題が与えられた場合、多項式時間でその問題を解決する非決定性マシンを構築します。次に、そのマシンへの各入力に対して、その特定の入力がマシンに渡されたときにマシンが正しく実行されるか、マシンが停止して「はい」と答えるかを計算するブール式を構築します。すると、マシンが正しく実行して「はい」と答える方法がある場合にのみ、式を満たすことができるため、構築された式の充足可能性は、マシンが「はい」と答えるかどうかを尋ねることと同等になります。

この証明は、Garey & Johnson 1979、38～44 ページ、セクション 2.6 で示された証明に基づいています。

ブール充足可能性問題 (SAT) が NP 完全であることを証明するには、2 つの部分があります。1 つは、SAT が NP 問題であることを示すことです。もう 1 つは、すべての NP 問題が多項式時間の多対一縮約によって SAT 問題のインスタンスに縮約できることを示すことです。

SAT は NP に属します。なぜなら、与えられた式を満たすと主張されるブール値のブール変数への割り当ては、決定性チューリングマシンによって多項式時間で検証できるからです。(決定性チューリングマシンによって多項式時間で検証可能なステートメントと、非決定性チューリングマシンによって多項式時間で解決可能なステートメントは同等であり、その証明は、Sipser の『Introduction to the Theory of Computation』のセクション 7.3 や、NP に関する Wikipedia の記事など、多くの教科書に記載されています。)

ここで、NP の特定の問題が非決定性チューリング マシン によって解決できると仮定します。ここで、は状態の集合、はテープ記号のアルファベット、は初期状態、は受け入れ状態の集合、は遷移関係です。さらに、最大 の計算ステップ後に問題のインスタンスを受け入れるか拒否すると仮定します。ここで、はインスタンスのサイズ、は多項式関数です。 ${\displaystyle M=(Q,\Sigma ,s,F,\delta )}$${\displaystyle Q}$${\displaystyle \Sigma }$${\displaystyle s\in Q}$${\displaystyle F\subseteq Q}$${\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma )\times (Q\times \Sigma \times \{-1,+1\})}$${\displaystyle M}$${\displaystyle p(n)}$${\displaystyle n}$${\displaystyle p}$

各入力 に対して、マシンがを受け入れる場合にのみ満たされるブール式を指定します。 ${\displaystyle I}$${\displaystyle B}$${\displaystyle M}$${\displaystyle I}$

ブール式では、次の表に示す変数を使用します。ここで、はマシンの状態、はテープ位置、はテープ シンボル、は計算ステップの番号です。 ${\displaystyle q\in Q}$${\displaystyle -p(n)\leq i\leq p(n)}$${\displaystyle j\in \Sigma }$${\displaystyle 0\leq k\leq p(n)}$

すべてのおよび について、ブール式を次の表の部分式の論理積として定義します。 ${\displaystyle B}$${\displaystyle -p(n)\leq i\leq p(n)}$${\displaystyle 0\leq k\leq p(n)}$

入力に対して を受け入れる計算がある場合、およびそれらの意図された解釈を割り当てることによって を満たすことができます。一方、 を満たすことができる場合、変数への割り当てによって示される手順に従う、入力 に対してを受け入れる計算があります。 ${\displaystyle M}$${\displaystyle I}$${\displaystyle B}$${\displaystyle T_{i,j,k}}$${\displaystyle H_{i,k}}$${\displaystyle Q_{i,k}}$${\displaystyle B}$${\displaystyle M}$${\displaystyle I}$

ブール変数があり、それぞれは空間 にエンコード可能です。節の数は^[7]なので、 のサイズはです。したがって、この変換は、要求どおり、多項式時間の多項式削減になります。 ${\displaystyle O(p(n)^{2})}$${\displaystyle O(\log p(n))}$${\displaystyle O(p(n)^{3})}$${\displaystyle B}$${\displaystyle O(\log(p(n))p(n)^{3})}$

実際に入力文字列 に依存するのは、表の最初の行 ( ) のみです。残りの行は、入力の長さとマシン のみに依存し、 ステップまでの の一般的な計算を形式化します。 ${\displaystyle T_{i,j,0}}$${\displaystyle I}$${\displaystyle n}$${\displaystyle M}$${\displaystyle M}$${\displaystyle p(n)}$

変換では、多項式 が多用されます。その結果、上記の証明は構成的ではありません。 が既知であっても、与えられた問題が NP に属することを証明して、 の時間計算量の上限も既知でなければ、変換を効果的に計算することはできません。 ${\displaystyle p(n)}$${\displaystyle M}$${\displaystyle p(n)}$${\displaystyle M}$

上記の方法は、複雑性において非決定性チューリングマシンをエンコードしますが、文献では複雑性におけるより洗練されたアプローチについて説明しています。^{[8] [9] [10] [11] [12]}準線型の結果は、クックの最初の発表から7年後に初めて登場しました。 ${\displaystyle O(\log(p(n))p(n)^{3})}$${\displaystyle O(p(n)\log(p(n)))}$

SAT を用いた NP 完全問題の存在証明は、論理学における他の計算問題や、他の計算量クラスの完全性にも拡張できる。量化ブール式問題 (QBF) は、変数にネストされた全称量指定子と存在量指定子を含むように拡張されたブール式である。QBF 問題は、多項式空間複雑度に制限されたチューリングマシンによる計算をエンコードするために使用でき、 PSPACE 完全である問題 (真の量化ブール式の認識) が存在することを証明する。同様に、依存性量化ブール式は、対数空間複雑度に制限されたチューリングマシンによる計算をエンコードし、 NL 完全である問題が存在することを証明する。^{[13] [14]}

証明は、NP のすべての問題が多項式時間 (実際、対数空間で十分) でブール充足可能性問題のインスタンスに簡約できることを示しています。つまり、ブール充足可能性問題が決定論的チューリング マシンによって多項式時間で解決できる場合、NP のすべての問題が多項式時間で解決でき、したがって複雑性クラスNP は複雑性クラス P と等しくなります。

NP完全性の重要性は、1972年にリチャード・カープが発表した画期的な論文「組合せ問題における還元可能性」によって明らかになりました。この論文でカープは、それぞれが扱いにくいことで悪名高い21の多様な組合せ問題とグラフ理論問題がNP完全であることを示しました。^[1]

カープは、すでにNP完全であることが証明されている別の問題をその問題に還元することで、それぞれの問題がNP完全であることを示した。例えば、彼は3SAT問題（節ごとにちょうど3つの変数または変数の否定を持つ連言標準形（CNF）の式のブール充足可能性問題）がNP完全であることを、SATの任意のインスタンスを3SATの同等のインスタンスに（多項式時間で）還元する方法を示すことで示した。^[15]

ゲーリーとジョンソンは、著書「コンピュータと扱いにくさ：NP完全性理論へのガイド」^[16]で300以上のNP完全問題を提示しており、その複雑性クラスに属する新しい問題が今も発見され続けています。

SAT の多くの実際的な例はヒューリスティックな方法で解決できますが、SAT (および他のすべての NP 完全問題) に対する決定論的な多項式時間アルゴリズムが存在するかどうかという問題は、複雑性理論家、数理論理学者、およびその他の専門家による数十年にわたる熱心な努力にもかかわらず、依然として未解決の問題として有名です。詳細については、記事「P 対 NP 問題」を参照してください。