クック＝レヴィンの定理

計算複雑性理論において、クックの定理としても知られるクック・レヴィンの定理は、ブール充足可能性問題が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が存在する。特に、このオラクルでは、PA ^≠ NP A^である。^{[ 3 ]}  

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

レヴィンのアプローチは、クックやカープのアプローチとは若干異なり、単に存在を判定するのではなく、解を見つける必要がある探索問題に着目した。彼は、そのようなNP完全探索問題、すなわち普遍問題を6つ提示した。さらに、彼はこれらの問題それぞれに対して、最適な時間で解くアルゴリズムを発見した（特に、これらのアルゴリズムはP=NPの場合に限り多項式時間で実行される）。

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

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

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

この証明は、 Garey & Johnson 1979 、pp. 38–44、セクション 2.6で示されたものに基づいています。 

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

SATはNPに属する。なぜなら、与えられた式を満たすと主張されるブール変数へのブール値の割り当ては、決定性チューリングマシンによって多項式時間で検証できるからである。（決定性チューリングマシンによって多項式時間で検証可能な命題と、非決定性チューリングマシンによって多項式時間で解ける命題は同等であり、その証明は多くの教科書、例えばSipserの『計算理論入門』第7.3節、およびWikipediaのNPに関する記事で見ることができる。）

ここで、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}$これは、変数への代入によって示される手順に従います。

がある${\displaystyle O(p(n)^{2})}$ブール変数、それぞれ空間に符号化可能${\displaystyle O(\log p(n))}$節の数は${\displaystyle O(p(n)^{3})}$^{[ 7 ]}なので、サイズは${\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)}$ステップ。

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

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

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

この証明は、NPに属するすべての問題を多項式時間（実際には対数空間で十分）でブール充足可能性問題のインスタンスに還元できることを示しています。これは、ブール充足可能性問題が決定性チューリングマシンによって多項式時間で解けるのであれば、NPに属するすべての問題も多項式時間で解けることを意味し、したがって複雑性クラスNPは複雑性クラスPと等しくなります。

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

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

ゲイリーとジョンソンは著書『コンピュータと難解性：NP完全性理論への手引き』^{[ 16 ]}で300以上のNP完全問題を紹介しており、その複雑性クラスに属する新たな問題が今も発見され続けている。

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