Proof Complexity｜証明複雑性
Proof Complexity（証明複雑性）とは、ある命題（論理式）が「正しい」ことを証明するために、最低限どれくらいの長さの証明が必要かを研究する分野です。計算量理論が「問題を解く時間」を測るのに対し、証明複雑性は「論理的な裏付けの短さ」を測ります。
1. 基本的な考え方
例えば、ある論理式 A 「常に真（トートロジー）」であるとします。このとき、誰かを納得させるための「最短の証明」は、入力である Aのサイズに対してどの程度の長さになるでしょうか？
- 短い証明が存在する: その問題は「効率的に検証可能」です。
- 非常に長い証明しか存在しない: その命題の正しさを確認するには、膨大な手間がかかります。
2. P vs NP問題
証明複雑性は、計算理論の核心である NP vs co-NP 問題と密接に結びついています。
- もし、すべてのトートロジー（常に真の式）に対して、多項式サイズの短さで終わる証明システムが存在するなら、NP = co-NP が成立します。
- 逆に、ある特定の論理式に対して「どんな証明手法を使っても指数関数的な長さの証明にしかならない」ことが示せれば、P ≠ NP の証明に一歩近づくことになります。
3. 主要な証明システム
「証明」のルール（体系）によって、必要となる長さは変わります。一般的に、強力なルールを持つシステムほど、証明は短くなります。
| 証明システム | 特徴 |
| 真理値表 (Truth Table) | 全パターンを網羅。常に指数関数的な長さが必要。 |
| 分解法 (Resolution) | 多くのSATソルバで使われる基本アルゴリズム。 pigeonhole principle（鳩の巣原理）の証明には非常に長いステップが必要なことが証明されている。 |
| フレーゲ体系 (Frege System) | 一般的な教科書に載っているような論理推論。非常に強力で、多くの命題を短く証明できる。 |
| 多項式計算 (Polynomial Calculus) | 代数的な手法を用いた証明体系。 |
4. なぜ「下界（Lower Bound）」が重要か
この分野の主な目的は、「この証明システムでは、この命題を証明するのに絶対にこれ以上のステップが必要だ」という限界（閾値）を示すことです。
例えば、「n個の巣に n+1 羽の鳩を入れると、必ずどこかの巣に2羽以上入る」という鳩の巣原理を、単純な「分解法」で証明しようとすると、入力サイズに対して指数関数的なステップが必要になることが数学的に証明されています。これは、アルゴリズムの限界を数学的に裏付ける重要な成果です。
Proof Complexityは、私たちが直感的に「難しい」と感じる問題に対し、「なぜ難しいのか」「物理的・論理的にどれほどのコストがかかるのか」という限界を解明しようとする学問です。