第5章計算複雑性理論

はじめに

計算複雑性理論は、計算可能な問題を解くのに必要な資源（時間や空間）を定量的に分析する分野です。すべての計算可能な問題が実用的に解けるわけではありません。本章では、問題の困難さを厳密に定義し、P、NP、PSPACE などの重要な複雑性クラスを学びます。

特に、コンピュータサイエンスにおける最も重要な未解決問題の一つである P vs NP 問題を中心に、計算複雑性の理論的枠組みを構築します。この理論は、暗号理論、最適化、人工知能など、多くの応用分野の基礎となっています。

学習目標

時間・空間複雑度の定義と主要な漸近記法（O/Ω/Θ）を正確に使える
複雑性クラス（P, NP, coNP, PSPACE, EXPTIME など）の関係を説明できる
検証可能性による NP の特徴付けと多項式時間還元を説明できる
NP完全性の定義を述べ、典型問題（SAT, 3-SAT, VERTEX-COVER 等）への還元を追える
空間複雑性（SPACE, PSPACE 完全）や多項式階層の直観を持つ

まとめ

TIME/SPACE クラスの枠組みで「実用的に解ける」問題を整理する
多項式時間還元は困難さ比較の標準手段で、NP完全性は転送により示す
P vs NP は未解決だが、既知の包含関係とバリア理論が探索の指針を与える

章末問題

代表演習と詳細解答は付録C（第5章）を参照: ../appendices/c/#ex-sol-ch5

5.1 時間複雑性

5.1.1 計算時間の定義

定義 5.1 チューリング機械 M の入力 w に対する実行時間（running time）を、 M が w で停止するまでのステップ数とする。M が停止しない場合は ∞ とする。

定義 5.2 チューリング機械 M の時間複雑度（time complexity）t_M: ℕ → ℕ を t_M(n) = max{M が長さ n の入力 w で実行するステップ数} と定義する。

5.1.2 漸近記法

計算量の解析では、定数倍や低次の項を無視した漸近的な振る舞いに注目します。

定義 5.3 関数 f, g: ℕ → ℝ⁺ に対して：

Big-O記法：f(n) = O(g(n)) ⟺ ∃c > 0, ∃n₀, ∀n ≥ n₀, f(n) ≤ c·g(n)
Big-Ω記法：f(n) = Ω(g(n)) ⟺ ∃c > 0, ∃n₀, ∀n ≥ n₀, f(n) ≥ c·g(n)
Θ記法：f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) かつ f(n) = Ω(g(n))
little-o記法：f(n) = o(g(n)) ⟺ lim_{n→∞} f(n)/g(n) = 0
little-ω記法：f(n) = ω(g(n)) ⟺ lim_{n→∞} f(n)/g(n) = ∞

性質：

推移性：f = O(g) かつ g = O(h) ⟹ f = O(h)
反射性：f = O(f)
対称性：f = Θ(g) ⟺ g = Θ(f)

直観図：代表的な計算量の増加の比較（O(1), O(log n), O(n), O(n log n), O(n²)）

Big-O 成長率の比較

5.1.3 時間複雑性クラス

計算複雑性の階層構造

定義 5.4 時間構成可能関数 t: ℕ → ℕ に対して、 TIME(t(n)) = {L | ある O(t(n)) 時間チューリング機械が L を決定} （多くの文献では DTIME(t(n)) と表記し、本書では TIME(t(n)) と同義に扱います）

定義 5.5 重要な時間複雑性クラス：

P = ⋃_{k≥0} TIME(n^k)（多項式時間）
EXPTIME = ⋃_{k≥0} TIME(2^{n^k})（指数時間）
2-EXPTIME = ⋃_{k≥0} TIME(2^{2^{n^k}})（二重指数時間）

定理 5.1（時間階層定理）時間構成可能関数 f, g に対して、 f(n)·log f(n) = o(g(n)) ならば DTIME(f(n)) ⊂ DTIME(g(n))

証明の概要：Hartmanis–Stearns の対角化論法を用いて、あらゆる f(n) 時間決定手続きと異なる振る舞いをする g(n) 時間の機械を構成する。対角化対象となる機械をシミュレートし、その出力を反転する際に、g(n) のステップ数を管理するためのログ因子が必要になる（log の底は 2 を想定しても一般性を失わない）。□

系 5.1 P ⊂ EXPTIME

5.1.4 多テープ機械と時間複雑性

定理 5.2 k-テープチューリング機械が t(n) 時間で認識する言語は、 1-テープチューリング機械で O(t(n)²) 時間で認識できる（十分大きな n で t(n) ≥ n を仮定）。

注：この仮定は標準的であり、t(n) が時間構成可能である通常の枠組みで自然に満たされる。参考として、Hennie–Stearns (1966) は k-テープ機械が 2-テープ機械で O(t(n) log t(n)) 時間にシミュレートできること、さらに 1-テープ機械では O(t(n)²) の遅延が避けられないことを示している。

証明の概要：1-テープ機械は k 本のテープを順番にシミュレートする。各ステップで最大 O(t(n)) の距離を移動する必要があり、 t(n) ステップのシミュレーションに O(t(n)²) 時間かかる。□

5.2 非決定性と NP

5.2.1 非決定性時間複雑性

定義 5.6 非決定性チューリング機械 N の時間複雑度を t_N(n) = max{N が長さ n の入力 w を受理する最短計算パスの長さ}

定義 5.7 NTIME(t(n)) = {L

ある O(t(n)) 時間非決定性機械が L を認識}

定義 5.8 NP = ⋃_{k≥0} NTIME(n^k)（非決定性多項式時間）

5.2.2 検証による NP の特徴付け

定義 5.9 言語 L が検証可能（verifiable）であるとは、多項式 p と多項式時間チューリング機械 V（検証器）が存在して、 w ∈ L ⟺ ∃証明書 c (|c| ≤ p(|w|) かつ V(w, c) = accept)

定理 5.3 L ∈ NP ⟺ L は多項式時間検証可能

証明：（⟹）L を認識する非決定性多項式時間機械 N が存在。証明書を N の受理計算パスとし、V は計算パスの正当性を検証。

（⟸）検証器 V と多項式 p が存在。非決定性機械 N を以下のように構成：

長さ ≤ p( w ) の証明書 c を非決定的に推測
V(w, c) を実行
V が accept なら accept

両方向とも多項式時間で実行可能。□

5.2.3 NP の例

例 5.1 以下の問題はすべて NP に属する：

SAT（充足可能性問題）
- 入力：論理式 φ
- 問：φ を真にする変数割当は存在するか？
- 証明書：変数割当
HAMPATH（ハミルトン路問題）
- 入力：有向グラフ G と頂点 s, t
- 問：s から t へのハミルトン路は存在するか？
- 証明書：頂点の列
CLIQUE
- 入力：グラフ G と整数 k
- 問：サイズ k のクリークは存在するか？
- 証明書：k 個の頂点
SUBSET-SUM
- 入力：整数の集合 S と目標値 t
- 問：和が t となる部分集合は存在するか？
- 証明書：部分集合

5.2.4 coNP

定義 5.10 coNP = {L

L̄ ∈ NP}

coNP は NP の補クラスであり、存在量化（∃）による「検証可能性」に対して、全称量化（∀）の側から特徴付けられます。以下では補言語による形式的定義を起点に、証明系の観点から直観を補う等価な記述を示します。次のいずれかを採用できます。

（等価定義A）補言語のNP性：L ∈ coNP ⟺ L̄ ∈ NP。

（等価定義B）全称証明書に基づく完全性／健全性：多項式 p と多項式時間判定手続き V が存在して、

完全性（completeness）：w ∈ L ⇒ ∀c ( c ≤ p( w )) について V(w, c) = 1
健全性（soundness）：w ∉ L ⇒ ∃c ( c ≤ p( w )) が存在して V(w, c) = 0

（等価定義C）反証の存在による特徴付け：多項式 q と多項式時間判定手続き U が存在して、 w ∉ L ⇔ ∃d (|d| ≤ q(|w|)) により U(w, d) = 1（反証）

これらは互いに同値で、coNP が「否定例（反証）が簡単に見つかる」クラスであることを示します。

例 5.2 UNSAT = {φ | φ は充足不可能} ∈ coNP：

φ が充足不可能であることは、あらゆる割当 a に対して φ(a) = 偽であることを意味する
等価定義Bにおいて、V(φ, a) = 1 を「a は φ を反証しない（＝φ(a)=偽ではない）」ではなく、 V を「a が φ を反証する（＝φ(a)=偽）」の判定に取れば、完全性／健全性を満たすように設計できる（または等価定義Cを用いる）

より明示的には、反証器 U を U(φ,a)=1 ⇔ φ(a)=偽と定義すれば、「w ∉ L ⇔ ∃d で U(w,d)=1」という等価定義Cの形を満たす（UNSAT の場合、w=φ）。

未解決問題：NP = coNP ?（未解決）。

5.3 P vs NP 問題

5.3.1 問題の定式化

P vs NP 問題の構造

P vs NP 問題：P = NP か？

この問題は以下のように言い換えられます：

解の検証が簡単な問題は、解の発見も簡単か？
非決定性は多項式時間計算に対して真の計算力の増加をもたらすか？

現在の知見：

P ⊆ NP（定義より明らか）
P ≠ NP と広く信じられているが、証明されていない
相対化、自然な証明、代数化などの障壁が知られている

5.3.2 NP 完全性

NP困難とNP完全の明確な区別

この2つの概念は似ているように見えますが、重要な違いがあります。

定義 5.11 言語 L がNP困難（NP-hard）⟺ ∀A ∈ NP, A ≤_p L

定義 5.12 言語 L がNP完全（NP-complete）⟺ L ∈ NP かつ L は NP困難

ここで ≤_p は多項式時間多対一還元を表す。

直感的理解：

NP困難：「NPの全ての問題より少なくとも同じくらい難しい」
- NPの任意の問題を多項式時間で還元できる
- 但し、その問題自体がNPに含まれるかは問わない
- 「少なくともNPと同じくらい難しい」問題
NP完全：「NPの中で最も難しい問題」
- NP困難である（NPの全ての問題より難しい）
- かつ、自分自身もNPに属する（非決定性多項式時間で解ける）
- 「NPの代表選手」とも言える

ベン図による可視化（概念図）： NP完全 = NP ∩ NP-hard、NP-hard は NP の外側にも内側にも存在しうる（NP⊆決定可能の範囲で）。以下は概念を伝えるための図示であり、厳密な包含関係を比例で示すものではありません。

        決定可能
   ┌────────────────────┐
   │        ┌─────── NP-hard ───────┐
   │   NP   │   （NPの外側にも延びる）│
   │ ┌────┐│  ┌───────────────┐   │
   │ │ P  ││  │  NP-complete  │   │
   │ └────┘│  └───────────────┘   │
   │        └──────────────────────┘
   └────────────────────────────────┘

具体例での比較：

NP完全問題の例：

3-SAT: 論理式の充足可能性問題
- NPに属する：非決定性アルゴリズムで多項式時間で検証可能
- NP困難：NPの全ての問題から還元可能
頂点被覆: グラフの頂点被覆問題
- NPに属する：与えられた解を多項式時間で検証可能
- NP困難：3-SATから還元可能

NP困難だがNP完全でない典型的な状況：

最適化版TSP（巡回セールスマン問題の最小コストを求める）：
- 最適化問題は決定問題ではないため「NPに属する/しない」という分類の対象外
- その決定版（総コスト ≤ K?）は NP 完全であり、最適化版は NP 困難
NPの外側にある決定可能問題（例：一部のEXPTIME完全問題）は NP 困難になりうるが、それでも「決定不能問題（停止問題など）」とは別領域である点に注意

注：停止問題のような決定不能問題は、通常の多項式時間多対一還元の枠組みで「NP 困難」と位置付けるのは不適切です（還元の種類が異なるため）。分類を混同しないよう明記しました。

重要な理論的含意：

NP完全問題の意義：

# もしNP完全問題Lが多項式時間で解けたら
if solve_NP_complete_L_in_polynomial_time():
    # NPの全ての問題が多項式時間で解ける
    P_equals_NP = True
    # 暗号学、最適化など多くの分野に革命的影響

NP困難問題の特徴：
- P ≠ NP なら多項式時間アルゴリズムは存在しない
- 近似アルゴリズムや発見的手法が必要
- 実用的には「諦めて効率的な近似を探す」

実用的な判断基準：

問題の性質	分類	実用的アプローチ
NPに属し、かつNPの最難問題	NP完全	近似・発見的・特殊ケース
NPより難しいが、決定可能	NP困難	より強力な近似・制限された入力
決定不能	NP困難	部分的解決・手動判断

この区別により、問題の「絶望度」を正確に測ることができます。

定理 5.4 L が NP完全で L ∈ P ならば P = NP

証明：任意の A ∈ NP に対して A ≤_p L。 L ∈ P なので、還元と L の決定を組み合わせて A を多項式時間で決定できる。したがって NP ⊆ P となり、P = NP。□

5.3.3 Cook–Levin の定理

定理 5.5（Cook–Levin）SAT は NP完全である。

【構成のスケッチ（直観）】任意の NP の言語 L と入力 w に対して、"w ∈ L" を満たす多項式長の証明書の存在を、充足可能なCNF論理式 φ に多項式時間で符号化する。

直観図：テープ×時間の格子から CNF への局所制約

Cook–Levin の直観図（テープ×時間とCNF）

符号化の主成分：

変数の用意
- 計算表（time × tape cell）上の各セルのテープ記号、ヘッド位置、状態を表すブール変数
- 多項式ステップ T、テープ範囲も多項式に抑える
制約（CNF）
- 初期条件：t=0 で入力wが書かれ、初期状態・ヘッド位置が成り立つ
- 局所遷移：任意の t から t+1 への近傍セルの変化は、TM の遷移関数に一致（窓制約のCNF化）
- 一意性：各時刻・各セルで取れる記号や状態は1つだけ（排他制約）
- 受理条件：ある時刻 t≤T に受理状態が現れる
大きさ
- 変数・節の総数は w の多項式で抑えられる

これにより、L ∈ NP の任意のインスタンス (w) が SAT のインスタンス φ(w) に多項式時間で写像され、w ∈ L ⇔ φ(w) は充足可能、を得る。□

還元の作法（チェックリスト）

インスタンスの包み直し: (w) → φ(w) を明確に定義する
サイズ管理: φ(w) は w の多項式で抑える
受理/拒否の対応: w ∈ L ⇔ φ(w) が充足可能となるよう構成する
局所性: TM の遷移は局所窓（定数サイズ）のCNFで表現する

証明の概要：任意の L ∈ NP に対して L ≤_p SAT を示す。 L を認識する非決定性多項式時間機械 N が存在。

入力 w に対して、以下を満たす論理式 φ_w を構成： φ_w が充足可能 ⟺ N は w を受理

φ_w は以下の変数を含む：

x_{i,j,s}：時刻 i にテープの位置 j に記号 s がある
q_{i,k}：時刻 i に状態 q_k にある
h_{i,j}：時刻 i にヘッドが位置 j にある

φ_w は以下の条件を表現：

初期構成が正しい
各ステップで正しい遷移が行われる
最終的に受理状態に達する
各時刻で一貫性が保たれる

構成は多項式時間で可能。□

5.3.4 NP完全問題の連鎖と還元の「気持ち」

NP完全性と還元の連鎖

還元の本質的なアイデア

還元（reduction）は「問題の翻訳」と考えることができます。問題Aから問題Bへの還元 A ≤_p B は：

「問題Aの任意のインスタンスを、問題Bのインスタンスに効率的に翻訳する方法」

還元の「気持ち」：

翻訳の保存性：元の問題の答え（Yes/No）が翻訳後も保たれる
効率性：翻訳は多項式時間で可能
困難さの転移：「Bが簡単ならAも簡単」「Aが難しいならBも難しい」

具体例：3-SATから頂点被覆への還元

問題設定：

3-SAT: 各節が最大3個のリテラルを持つ論理式が充足可能か？
頂点被覆: 与えられたグラフで、全ての辺に接続する頂点をk個以下選べるか？

還元の構成（3-SAT → 頂点被覆）：

Step 1: 論理式からグラフへの翻訳

3-SAT式 φ = (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) を考えます。

各変数xᵢについて：

変数ガジェット：
xᵢ ────── ¬xᵢ

2つの頂点を辺で結びます。これにより「xᵢか¬xᵢのどちらか一方を選ぶ」ことを強制します。

各節Cⱼについて：

節ガジェット（例：x₁ ∨ ¬x₂ ∨ x₃）：
    a₁
   / | \
  x₁ ¬x₂ x₃

節の各リテラルに対応する頂点を、新しい「節頂点」に接続します。

Step 2: パラメータの設定 k = (変数の個数) + 2×(節の個数)

Step 3: 還元の正当性

3-SAT式が充足可能 ⟹ 頂点被覆がk個以下で存在：

充足する割り当てでは、各変数について真なる方を選択
各節について、真になるリテラルが少なくとも1つあるので、それ以外の2つを選択
合計：n個（変数分）+ 2m個（節分）= k個

頂点被覆がk個以下で存在 ⟹ 3-SAT式が充足可能：

各変数ガジェットから1つずつ選ばれる（それが変数の割り当て）
各節ガジェットで節頂点が選ばれない場合、接続されたリテラル頂点の1つが選ばれない
これは対応するリテラルが真であることを意味

具体的な例：

3-SAT式: φ = (x ∨ ¬y) ∧ (¬x ∨ y)

変換されたグラフ：

変数ガジェット：
x ────── ¬x
y ────── ¬y

節ガジェット：
  a₁        a₂
 / \       / \
x  ¬y     ¬x  y

k = 2 + 2×2 = 6

充足する割り当て x=True, y=True の場合：

変数ガジェットから: {x, y}
節1から: {¬y, a₁} (xが真なので¬yとa₁を選ぶ)
節2から: {¬x, a₂} (yが真なので¬xとa₂を選ぶ)
合計6個で全ての辺を被覆

SATからの還元チェーン

SAT → 3-SAT → 頂点被覆 → ハミルトン路 → TSP

SAT → 3-SAT（定理 5.6で示した）：
- 長い節を分解する技法
- 補助変数による「連鎖」の作成
3-SAT → 頂点被覆（上記で詳述）：
- 論理的制約をグラフ構造に埋め込み
頂点被覆 → ハミルトン路：
- グラフの構造的性質を経路問題に変換
ハミルトン路 → TSP：
- 決定問題を最適化問題に拡張

還元の実用的意義：

# 還元の実用的応用例
def solve_vertex_cover_via_SAT(graph, k):
    """
    頂点被覆問題をSATソルバーで解く
    """
    # 逆方向の還元を利用
    sat_instance = reduce_vertex_cover_to_SAT(graph, k)
    solution = sat_solver(sat_instance)
    
    if solution:
        return extract_vertex_cover(solution)
    else:
        return None

# 実際に使われている：
# - プランニング問題のSAT還元
# - モデル検査のSAT還元  
# - ハードウェア設計検証のSAT還元

この還元チェーンにより、数千のNP完全問題が相互接続され、一つを解く効率的アルゴリズムが見つかれば、全てが解けることが保証されています。

5.4 空間複雑性

5.4.1 空間複雑性の定義

定義 5.13 チューリング機械 M の空間複雑度 s_M(n) を、長さ n の任意の入力に対して M が使用するテープマス数の最大値とする。

定義 5.14 SPACE(s(n)) = {L

ある O(s(n)) 空間機械が L を決定}

定義 5.15 主要な空間複雑性クラス：

L = SPACE(log n)（対数空間）
NL = NSPACE(log n)（非決定性対数空間）
PSPACE = ⋃_{k≥0} SPACE(n^k)（多項式空間）

5.4.2 空間の基本的性質

定理 5.7（Savitchの定理）空間構成可能関数 s(n) ≥ log n に対して、 NSPACE(s(n)) ⊆ SPACE(s(n)²)

証明の概要：到達可能性問題を再帰的に解く。構成 C₁ から C₂ への高々 2^{s(n)} ステップの計算パスの存在を、中間点を推測することで判定。再帰の深さは s(n)、各レベルで O(s(n)) 空間。□

系 5.2 PSPACE = NPSPACE

5.4.3 空間と時間の関係

定理 5.8

TIME(f(n)) ⊆ SPACE(f(n))
SPACE(f(n)) ⊆ TIME(2^{O(f(n))})

証明： (1) 時間 f(n) では高々 f(n) マスしか使えない。 (2) s(n) 空間の機械の可能な構成数は高々 2^{O(s(n))}。ループを避けて計算すれば、この時間内に終了。□

系 5.3 L ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

計算複雑性クラスの包含関係

5.4.4 PSPACE完全性

定義 5.16 言語 L がPSPACE完全 ⟺ L ∈ PSPACE かつ ∀A ∈ PSPACE, A ≤_p L

定理 5.9 TQBF（真量化ブール式）は PSPACE完全である。

TQBF = {φ

φ は真な量化ブール式}

量化ブール式の例：∀x₁∃x₂∀x₃ [(x₁ ∨ x₂) ∧ (¬x₂ ∨ x₃)]

証明の概要：（TQBF ∈ PSPACE）再帰的に真偽を判定。各量化子で変数に 0/1 を代入。

（PSPACE困難性）任意の PSPACE 言語 L に対して、多項式空間機械 M の受理計算の存在を量化ブール式で表現。□

5.5 多項式階層

5.5.1 階層の定義

定義 5.17 多項式階層（Polynomial Hierarchy）：

Σ₀ᴾ = Π₀ᴾ = P
Σₖ₊₁ᴾ = NPᴾᶦᵏ（Πₖᴾ オラクル付き NP）
Πₖ₊₁ᴾ = coNPᴾᶦᵏ
PH = ⋃_{k≥0} Σₖᴾ

特徴付け：

Σ₁ᴾ = NP
Π₁ᴾ = coNP
Σ₂ᴾ = NP^{NP}（NP オラクル付き NP）

5.5.2 階層の性質

定理 5.10 各 k に対して：

Σₖᴾ ∪ Πₖᴾ ⊆ Σₖ₊₁ᴾ ∩ Πₖ₊₁ᴾ
Σₖᴾ = coΠₖᴾ

定理 5.11 以下は同値：

PH = PSPACE
ある k が存在して PH = Σₖᴾ
ある k が存在して Σₖᴾ = Σₖ₊₁ᴾ

これは階層が「崩壊」する条件を示しています。

5.5.3 完全問題

例 5.3 各レベルの完全問題：

Σ₁ᴾ完全：SAT
Π₁ᴾ完全：UNSAT
Σ₂ᴾ完全：∃∀SAT = {φ ∃x∀y φ(x,y) = 1}
Π₂ᴾ完全：∀∃SAT = {φ ∀x∃y φ(x,y) = 1}

5.6 確率的計算クラス

5.6.1 BPP（有界誤り確率多項式時間）

定義 5.18 言語 L ∈ BPP ⟺ ある確率的多項式時間機械 M が存在して：

w ∈ L ⟹ Pr[M(w) = accept] ≥ 2/3
w ∉ L ⟹ Pr[M(w) = accept] ≤ 1/3

定理 5.12 誤り確率は増幅により任意に小さくできる。 k 回の独立実行と多数決により、誤り確率を 2^{-Ω(k)} に削減可能。

5.6.2 その他の確率的クラス

定義 5.19

RP（片側誤り）：w ∈ L ⟹ Pr[accept] ≥ 1/2、w ∉ L ⟹ Pr[accept] = 0
coRP：RP の補クラス
ZPP = RP ∩ coRP（ゼロ誤り確率多項式時間）

関係：P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PP ⊆ PSPACE

5.6.3 確率的計算の脱乱択化

定理 5.13（Impagliazzo-Wigderson）適切な困難性仮定の下で、BPP = P

これは、真の乱数の代わりに疑似乱数生成器を使用できることを示唆しています。

5.7 回路複雑性

5.7.1 ブール回路

定義 5.20 ブール回路は、AND、OR、NOT ゲートからなる有向非巡回グラフ。

回路の複雑性尺度：

サイズ：ゲート数
深さ：最長パスの長さ

5.7.2 回路複雑性クラス

定義 5.21

P/poly = {L ある多項式 p, 各 n に対してサイズ ≤ p(n) の回路族が L_n を計算}

定理 5.14 P ⊆ P/poly

定理 5.15（Karp-Lipton）NP ⊆ P/poly ならば PH = Σ₂ᴾ

5.7.3 下界

定理 5.16 ほとんどすべての n 変数ブール関数は、サイズ Ω(2ⁿ/n) の回路を要求する。

証明：計数論法による。n 変数関数は 2^{2ⁿ} 個、サイズ s の回路は高々 (cn)^s 個。□

しかし、明示的な関数に対する超多項式下界は未解決。

5.8 対話型証明系

5.8.1 対話型証明の定義

定義 5.22 対話型証明系は、全能力の証明者 P と多項式時間検証者 V の間のプロトコル。

言語 L ∈ IP ⟺ ある検証者 V が存在して：

完全性：w ∈ L ⟹ ∃P, Pr[V^P(w) = accept] ≥ 2/3
健全性：w ∉ L ⟹ ∀P, Pr[V^{P}(w) = accept] ≤ 1/3

5.8.2 IP の能力

定理 5.17 NP ⊆ IP

定理 5.18（Shamir）IP = PSPACE

これは対話型証明が予想外に強力であることを示しています。

5.8.3 ゼロ知識証明

定義 5.23 対話型証明系がゼロ知識であるとは、検証者が証明から「w ∈ L」という事実以外の情報を得ないこと。

形式的には、効率的なシミュレータの存在で定義される。

定理 5.19 NP ⊆ CZK（計算論的ゼロ知識）（適切な暗号学的仮定の下で）

章末問題

基礎問題

以下の包含関係を証明せよ： (a) TIME(n) ⊂ TIME(n²) (b) L ⊆ NL ⊆ P (c) NP ⊆ PSPACE
以下の問題が NP に属することを示せ： (a) グラフ同型問題 (b) 整数計画問題 (c) 最短ベクトル問題
3-SAT から以下への多項式時間還元を構成せよ： (a) 3-彩色問題 (b) 頂点被覆問題 (c) サイズ管理： (b) の還元で、頂点数・辺数・k の増加が元のインスタンス（変数数 n と節数 m）に対して高々線形（O(n+m)）であることを示せ (d) CLIQUE 問題（クリーク） (e) INDEPENDENT-SET（最大独立集合）
PSPACE = NPSPACE を Savitch の定理を用いて証明せよ。

発展問題

時間階層定理の証明において、対角化言語が求める性質を持つことを詳細に証明せよ。
Cook-Levin の定理の証明で、チューリング機械の計算を論理式で符号化する際の具体的な構成を説明せよ。
多項式階層が Σₖᴾ で崩壊したとき、実際にすべての上位レベルが Σₖᴾ と等しくなることを証明せよ。
BPP における誤り確率の増幅技法（amplification）を詳細に解析せよ。

探究課題

P vs NP 問題に関する既知の障壁（相対化、自然な証明、代数化）について調査し、なぜこれらが問題解決を困難にするかを論ぜよ。
近似アルゴリズムと複雑性理論の関係を調査し、近似困難性結果（例：PCP定理）について説明せよ。
量子計算複雑性クラス（BQP、QMA等）について調査し、古典的な複雑性クラスとの関係を論ぜよ。
実用的な暗号システムが依拠する困難性仮定を調査し、複雑性理論との関連を説明せよ。

実装課題

NP完全問題のソルバーを実装せよ：

class SATSolver:
    def __init__(self, formula):
        """CNF式を入力として受け取る"""
        self.formula = formula
        
    def solve(self):
        """DPLLアルゴリズムまたはCDCLアルゴリズムで解く"""
        pass
        
    def verify_solution(self, assignment):
        """解の検証"""
        pass

計算複雑性の実験的解析を実装せよ：

class ComplexityAnalyzer:
    def measure_runtime(self, algorithm, input_generator, sizes):
        """異なる入力サイズでの実行時間測定"""
        pass
        
    def plot_complexity(self, data):
        """複雑性の可視化"""
        pass
        
    def estimate_asymptotic_behavior(self, data):
        """漸近的振る舞いの推定"""
        pass

確率的アルゴリズムのシミュレータを実装せよ：
- Miller-Rabin 素数判定法
- 誤り確率の増幅実験
- Monte Carlo vs Las Vegas アルゴリズムの比較直観図：変数/節ガジェットの最小例（3-SAT → 頂点被覆）

3-SAT → 頂点被覆ガジェット例

第5章 計算複雑性理論

はじめに

学習目標

まとめ

章末問題

5.1 時間複雑性

5.1.1 計算時間の定義

5.1.2 漸近記法

5.1.3 時間複雑性クラス

5.1.4 多テープ機械と時間複雑性

5.2 非決定性と NP

5.2.1 非決定性時間複雑性

5.2.2 検証による NP の特徴付け

5.2.3 NP の例

5.2.4 coNP

5.3 P vs NP 問題

5.3.1 問題の定式化

5.3.2 NP 完全性

5.3.3 Cook–Levin の定理

5.3.4 NP完全問題の連鎖と還元の「気持ち」

5.4 空間複雑性

5.4.1 空間複雑性の定義

5.4.2 空間の基本的性質

5.4.3 空間と時間の関係

5.4.4 PSPACE完全性

5.5 多項式階層

5.5.1 階層の定義

5.5.2 階層の性質

5.5.3 完全問題

5.6 確率的計算クラス

5.6.1 BPP（有界誤り確率多項式時間）

5.6.2 その他の確率的クラス

5.6.3 確率的計算の脱乱択化

5.7 回路複雑性

5.7.1 ブール回路

5.7.2 回路複雑性クラス

5.7.3 下界

5.8 対話型証明系

5.8.1 対話型証明の定義

5.8.2 IP の能力

5.8.3 ゼロ知識証明

章末問題

基礎問題

発展問題

探究課題

実装課題

第5章計算複雑性理論