3-SATの4.26x threshold

3-SATをコンピュータで大量に走らせた場合、4.3倍付近で急激に解けなくなる相転移が起きると報告した論文です。

あらゆるNP完全問題（NP-complete）の本質とは、すべて『3-SATにおけるアルファ（α）4.26未満のトポロジー判定』に集約（還元）できる

• 論文名： Where the Really Hard Problems Are

• 著者： Peter Cheeseman, Bob Kanefsky, and William M. Taylor

• 発表年： 1991年（IJCAI）

• 趣旨： 3-SATだけでなくグラフ彩色問題なども含め、NP完全問題には特定の「臨界点」があり、そこで難易度が爆発することを示した伝説的な論文です。

さらに、この比率を「約4.3」とピンポイントで特定したのが以下の論文です。

• 論文名： Statistical Mechanics of SAT

• 著者： Scott Kirkpatrick and Bart Selman

• 発表年： 1994年（Science）

• 趣旨： 物理学の「スピングラス（磁性体の物理モデル）」の数理をそのまま3-SATに持ち込み、これが物理の相転移と完全に同じ現象であることをScience誌上で証明しました。

②【「4.26」を理論的に厳密に導出した原典】（2002年）

長年、実験的には「約4.3」と言われていましたが、これを統計物理学の「レプリカ対称性の破れ（Replica Symmetry Breaking）」という超高度な手法を用いて、「4.267」という正確な数値を理論計算によって叩き出した絶対的な原典論文がこちらです。

• 論文名： Analytic and Algorithmic Solution of Random Satisfiability Problems

• 著者： Marc Mézard, Giorgio Parisi, and Riccardo Zecchina

• 発表年： 2002年（Science）

• 趣旨： この論文により、3-SATの臨界値が \alpha_c \approx 4.267 であることが物理・数学的に導き出されました。共著者のジョルジョ・パリージ（Giorgio Parisi）氏はこのスピングラスや複雑系の研究により、後に2021年にノーベル物理学賞を受賞しています。