あらゆるNPはboolean 3-SATに還元され、ZKPで検証できる

「あらゆるNP問題は3-SATに還元できる」という命題は、コンピュータサイエンスの歴史においてクリティカルパスとなる発見の一つです。

1. 1971年：スティーブン・クックと「SAT」の登場

計算機で解を出すのが難しい問題（巡回セールスマン問題やグラフ彩色問題など）は、個別に「どう解くか」が議論されていました。しかし、1971年にスティーブン・クック（Stephen Cook）が発表した論文は、困難さを一般化しました。

クック・レビンの定理

クック（および独立してソビエトのレニド・レビン）は、すべてのNP問題がSATであることを示しました。

• 論理: どんなNP問題も、「その解が正しいかどうかを検証するプログラム」が存在します。
• 物理的根拠: プログラムの実行は、コンピュータ内の論理ゲート（ブール演算）の連鎖です。
• 還元: クックは、コンピュータの計算プロセスそのものを、巨大な一つのブール論理式（SAT）として記述できることを示しました。

これにより、「SATが解けること」と「あらゆるNP問題が解けること」が同値であることが歴史上初めて証明されたのです。

2. 1972年：リチャード・カープによる「21のNP完全問題」

クックの発見は「SAT」という一つの問題に関するものでした。しかし、翌1972年、リチャード・カープ（Richard Karp）がこの理論を爆発的に広めます。

カープは、SATを起点として、3-SATを含む21種類の多種多様な難問が、すべて互いに還元可能であることを証明しました。

なぜ「SAT」から「3-SAT」へ絞られたのか

一般的なSATは、一つの節にいくつの変数が入っていても良い自由な形式です。しかし、カープは以下のことを示しました。

• どんなに長い論理式の節も、補助変数を使うことで、「最大3つの変数のOR」という極めてシンプルな形（3-SAT）に分解・変換できる。
• この変換は多項式時間（現実的な時間）で完了する。

この歴史的成果により、「たった3つの変数の組み合わせ問題のシークエンス（3-SAT）」が、複雑な世界中のあらゆるNP問題を代表する標準形式とになリマした。

3. 1986年：GMW論文による「全NPへのZKP適用」

3-SATへの還元以降 Oded Goldreich, Silvio Micali, Avi Wigderson (GMW) によるゼロ知識証明（ZKP）が一般化されました。

彼らのロジックは歴史の集大成です。

1. クックとカープ: 「あらゆるNP問題は、3-SATに変換できる」ことを証明済み。
2. GMWの貢献: 「3-SAT（厳密にはそれと等価な3彩色問題）に対して、ゼロ知識証明ができる」ことを証明。
3. 結論: 「ならば、この世のすべてのNP問題に対してゼロ知識証明が構成できる」という壮大な結論を導き出しました。

「あらゆるNPは3-SATに還元できる」という命題は、「どんなに複雑に見える問題も、NPにさえ変換できれば0と1、そして3つの変数の組み合わせという、ブール代数の最小単位にまで分解できる」という、計算可能宇宙の秩序を示しています。