第5章 計算複雑性理論

はじめに

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

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

通し例: 安全なメッセージ配送基盤 配送制約、レプリカ配置、メッセージ優先順位づけのような設計問題は、仕様としては自然でも計算量的には急激に難しくなることがあります。本章では、通し例のどの問いが多項式時間で扱え、どこからが困難になるかを判断する尺度を与えます。

学習目標

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

5.1 時間複雑性

5.1.1 計算時間の定義

定義 5.1 チューリング機械 M の入力 w に対する実行時間（running time）を、

M が w で停止するまでのステップ数とする。M が停止しない場合は ∞ とする。

定義 5.2 チューリング機械 M の時間複雑度（time complexity）\(t_M: \mathbb{N} \to \mathbb{N}\) を

\(t_M(n) = \max\{\text{M が長さ } n \text{ の入力 } w \text{ で実行するステップ数}\}\) と定義する。

5.1.2 漸近記法

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

定義 5.3 関数 \(f, g: \mathbb{N} \to \mathbb{R}_{>0}\) に対して：

1. Big-O記法：\(f(n) = O(g(n))\) ⟺ \(\exists c > 0,\ \exists n_0,\ \forall n \ge n_0,\ f(n) \le c\cdot g(n)\)

2. Big-Ω記法：\(f(n) = \Omega(g(n))\) ⟺ \(\exists c > 0,\ \exists n_0,\ \forall n \ge n_0,\ f(n) \ge c\cdot g(n)\)

3. Θ記法：\(f(n) = \Theta(g(n))\) ⟺ \(f(n) = O(g(n))\) かつ \(f(n) = \Omega(g(n))\)

4. little-o記法：\(f(n) = o(g(n))\) ⟺ \(\lim_{n\to\infty} f(n)/g(n) = 0\)

5. little-ω記法：\(f(n) = \omega(g(n))\) ⟺ \(\lim_{n\to\infty} f(n)/g(n) = \infty\)

性質：

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

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

5.1.3 時間複雑性クラス

定義 5.4 時間構成可能関数 \(t: \mathbb{N} \to \mathbb{N}\) に対して、

TIME(t(n)) = \(\{L \mid \text{ある } O(t(n)) \text{ 時間チューリング機械が } L \text{ を決定}\}\) （多くの文献では DTIME(t(n)) と表記し、本書では TIME(t(n)) と同義に扱います）

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

• P = \(\bigcup_{k \ge 0} \mathrm{TIME}(n^k)\)（多項式時間）
• EXPTIME = \(\bigcup_{k \ge 0} \mathrm{TIME}(2^{n^k})\)（指数時間）
• 2-EXPTIME = \(\bigcup_{k \ge 0} \mathrm{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 \(\mathrm{P} \subsetneq \mathrm{EXPTIME}\)

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

定理 5.2 k-テープチューリング機械が \(t(n)\) 時間で認識する言語は、

1-テープチューリング機械で \(O(t(n)^2)\) 時間で認識できる（十分大きな n で \(t(n) \ge n\) を仮定）。

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

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

5.2 非決定性と NP

5.2.1 非決定性時間複雑性

定義 5.6 非決定性チューリング機械 N の時間複雑度を

\(t_N(n) = \max\{\text{N が長さ } n \text{ の入力 } w \text{ を受理する最短計算パスの長さ}\}\)

定義 5.7 NTIME(t(n)) = \(\{L \mid \text{ある } O(t(n)) \text{ 時間非決定性機械が } L \text{ を認識}\}\)

定義 5.8 \(\mathrm{NP} = \bigcup_{k\ge 0} \mathrm{NTIME}(n^k)\)（非決定性多項式時間）

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

定義 5.9 言語 L が検証可能（verifiable）であるとは、

多項式 p と多項式時間チューリング機械 V（検証器）が存在して、 w ∈ L ⟺ ∃証明書 c（\(\lvert c\rvert \le p(\lvert w\rvert)\) かつ \(V(w, c) = \mathrm{accept}\)）

定理 5.3 \(L \in \mathrm{NP}\) \(\Leftrightarrow\) L は多項式時間検証可能

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

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

1. \(\lvert c\rvert \le p(\lvert w\rvert)\) を満たす証明書 c を非決定的に推測
2. V(w, c) を実行
3. V が accept なら accept

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

5.2.3 NP の例

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

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

5.2.4 coNP

定義 5.10 \(\mathrm{coNP} = \{L \mid \overline{L} \in \mathrm{NP}\}\)

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

（等価定義A）補言語のNP性：L ∈ coNP ⟺ \(\overline{L}\) ∈ NP。

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

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

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

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

例 5.2 \(UNSAT = \{\varphi \mid \varphi \text{ は充足不可能}\}\) ∈ 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 = NP か？

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

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

現在の知見：

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

5.3.2 NP 完全性

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

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

定義 5.11 言語 \(L\) がNP困難（NP-hard）\(\Leftrightarrow\) \(\forall A \in \mathrm{NP},\ A \le_p L\)

定義 5.12 言語 \(L\) がNP完全（NP-complete）\(\Leftrightarrow\) \(L \in \mathrm{NP}\) かつ \(L\) は NP困難

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

直感的理解：

1. NP困難：「NPの全ての問題より少なくとも同じくらい難しい」
   • NPの任意の問題を多項式時間で還元できる
   • 但し、その問題自体がNPに含まれるかは問わない
   • 「少なくともNPと同じくらい難しい」問題
2. 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 困難になりうる点に注意してください。 一方で、複雑性理論では通常、P/NP などの議論は決定可能な決定問題（言語）を主対象にし、決定不能問題は「複雑性」の比較ではなく「計算不能性」の文脈で扱います。

重要な理論的含意：

1. NP完全問題の意義：

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

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

実用的な判断基準：

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

定理 5.4 \(L\) が NP完全で \(L \in \mathrm{P}\) ならば \(\mathrm{P} = \mathrm{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 への局所制約

符号化の主成分：

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

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

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

• インスタンスの包み直し: (w) → φ(w) を明確に定義する
• サイズ管理: \(\lvert \varphi(w)\rvert\) は \(\lvert w\rvert\) の多項式で抑える
• 受理/拒否の対応: 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 は以下の条件を表現：

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

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

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

還元の本質的なアイデア

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

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

還元の「気持ち」：

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

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

問題設定：

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

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

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

3-SAT式 \(\varphi = (x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor \lnot x_3)\) を考えます。

各変数 \(x_i\) について：

変数ガジェット：
x_i ────── ¬x_i

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

各節 \(C_j\) について：

節ガジェット（例：x1 ∨ ¬x2 ∨ x3）：
    a1
   / | \
  x1 ¬x2 x3

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

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

節ガジェット：
  a1        a2
 / \       / \
x  ¬y     ¬x  y

\(k = 2 + 2\times 2 = 6\)

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

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

SATからの還元チェーン

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

1. SAT → 3-SAT（定理 5.6で示した）：
   • 長い節を分解する技法
   • 補助変数による「連鎖」の作成
2. 3-SAT → 頂点被覆（上記で詳述）：
   • 論理的制約をグラフ構造に埋め込み
3. 頂点被覆 → ハミルトン路：
   • グラフの構造的性質を経路問題に変換
4. ハミルトン路 → 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 \mid \text{ある } O(s(n)) \text{ 空間機械が } L \text{ を決定}\}\)

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

• L = SPACE(log n)（対数空間）
• NL = NSPACE(log n)（非決定性対数空間）
• PSPACE = \(\bigcup_{k \ge 0} \mathrm{SPACE}(n^k)\)（多項式空間）

5.4.2 空間の基本的性質

定理 5.7（Savitchの定理）空間構成可能関数 \(s(n) \ge \log n\) に対して、

\(\mathrm{NSPACE}(s(n)) \subseteq \mathrm{SPACE}(s(n)^2)\)

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

系 5.2 \(\mathrm{PSPACE} = \mathrm{NPSPACE}\)

5.4.3 空間と時間の関係

定理 5.8

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

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

系 5.3 \(\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}\)

5.4.4 PSPACE完全性

定義 5.16 言語 \(L\) がPSPACE完全 \(\Leftrightarrow\) \(L \in \mathrm{PSPACE}\) かつ \(\forall A \in \mathrm{PSPACE},\ A \le_p L\)

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

TQBF = \(\{\varphi \mid \varphi \text{ は真な量化ブール式}\}\)

量化ブール式の例：\(\forall x_1\, \exists x_2\, \forall x_3\, [(x_1 \lor x_2) \land (\lnot x_2 \lor x_3)]\)

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

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

5.5 多項式階層

5.5.1 階層の定義

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

• \(\Sigma_0^{\mathrm{P}} = \Pi_0^{\mathrm{P}} = \mathrm{P}\)
• \(\Sigma_{k+1}^{\mathrm{P}} = \mathrm{NP}^{\Sigma_k^{\mathrm{P}}}\)（\(\Sigma_k^{\mathrm{P}}\) オラクル付き \(\mathrm{NP}\)）
• \(\Pi_{k+1}^{\mathrm{P}} = \mathrm{coNP}^{\Sigma_k^{\mathrm{P}}}\)
• \(\mathrm{PH} = \bigcup_{k\ge 0} \Sigma_k^{\mathrm{P}}\)

特徴付け：

• \(\Sigma_1^{\mathrm{P}} = \mathrm{NP}\)
• \(\Pi_1^{\mathrm{P}} = \mathrm{coNP}\)
• \(\Sigma_2^{\mathrm{P}} = \mathrm{NP}^{\mathrm{NP}}\)（\(\mathrm{NP}\) オラクル付き \(\mathrm{NP}\)）

5.5.2 階層の性質

定理 5.10 各 k に対して：

1. \(\Sigma_k^{\mathrm{P}} \cup \Pi_k^{\mathrm{P}} \subseteq \Sigma_{k+1}^{\mathrm{P}} \cap \Pi_{k+1}^{\mathrm{P}}\)
2. \(\Sigma_k^{\mathrm{P}} = \mathrm{co}\,\Pi_k^{\mathrm{P}}\)

定理 5.11 以下は同値：

1. \(PH = PSPACE\)
2. \(\exists k\, (\mathrm{PH} = \Sigma_k^{\mathrm{P}})\)
3. \(\exists k\, (\Sigma_k^{\mathrm{P}} = \Sigma_{k+1}^{\mathrm{P}})\)

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

5.5.3 完全問題

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

• \(\Sigma_1^{\mathrm{P}}\) 完全：SAT
• \(\Pi_1^{\mathrm{P}}\) 完全：UNSAT
• \(\Sigma_2^{\mathrm{P}}\) 完全：∃∀SAT = \(\{\varphi \mid \exists x\forall y\, \varphi(x,y) = 1\}\)
• \(\Pi_2^{\mathrm{P}}\) 完全：∀∃SAT = \(\{\varphi \mid \forall x\exists y\, \varphi(x,y) = 1\}\)

5.6 確率的計算クラス

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

定義 5.18 \(L \in \mathrm{BPP}\) \(\Leftrightarrow\) ある確率的多項式時間機械 M が存在して：

• \(w ∈ L ⟹ Pr[M(w) = accept] \ge 2/3\)
• \(w ∉ L ⟹ Pr[M(w) = accept] \le 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 \mid \text{ある多項式 } p, \text{ 各 } n \text{ に対してサイズ } \le p(n) \text{ の回路族が } L_n \text{ を計算}\}\)

定理 5.14 \(\mathrm{P} \subseteq \mathrm{P}/\mathrm{poly}\)

定理 5.15（Karp-Lipton）NP ⊆ P/poly ならば \(\mathrm{PH} = \Sigma_2^{\mathrm{P}}\)

5.7.3 下界

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

証明：計数論法による。n 変数関数は \(2^{2^{n}}\) 個、 サイズ 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 \(\mathrm{NP} \subseteq \mathrm{IP}\)

定理 5.18（Shamir）\(\mathrm{IP} = \mathrm{PSPACE}\)

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

5.8.3 ゼロ知識証明

定義 5.23 対話型証明系がゼロ知識であるとは、

検証者が証明から「w ∈ L」という事実以外の情報を得ないこと。

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

定理 5.19 \(\mathrm{NP} \subseteq \mathrm{CZK}\)（計算論的ゼロ知識）

（適切な暗号学的仮定の下で）

まとめ

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

次章への橋渡し

複雑性クラスで問題全体の難しさを見た後は、個々のアルゴリズムをどう解析するかが課題になります。次章では漸近解析・再帰式・償却解析を使って、設計手法と性能保証を具体的に結びつけます。

補助資料を併用するなら、手を動かす確認は 付録B の第5章節、現実の接続は 付録E の第5章節、理解確認は 付録F の第5章節を参照してください。

参考文献と次の一歩

• 図版の再参照: 本章の図をまとめて見返したいときは 付録H: 図版ガイドと図一覧 を参照してください。
• 標準: Sanjeev Arora, Boaz Barak, 『Computational Complexity: A Modern Approach』. 現代的な複雑性理論の全体像をつかむための標準書です。
• 古典: Michael R. Garey, David S. Johnson, 『Computers and Intractability』. NP 完全問題の代表例と還元カタログを確認したいときの原点です。
• 補助: Christos H. Papadimitriou, 『Computational Complexity』. 複雑性クラスの見取り図と証明の手筋を、より理論寄りに追いたい読者向けです。
• 出典メモ: SAT の NP 完全性は Cook、問題族への展開は Karp の古典的結果に基づきます。本章の難しさ比較は、その後の複雑性理論で標準化された還元の枠組みを採用しています。
• 次の一歩: 個々のアルゴリズムの性能保証に降りるなら第6章へ、学習理論との接点を見たいなら 付録G を参照してください。

  章末問題

• 代表演習と詳細解答は 付録C（第5章） を参照。

取り組み方ガイド

迷ったら次の表の順で進め、詰まったら「主に戻る節」にあるクラス定義・還元テンプレート・代表例を先に見直してください。

基礎問題

1. 以下の包含関係を証明せよ： \((a) TIME(n) ⊂ TIME(n^2)\) \((b) L ⊆ NL ⊆ P\) \((c) NP ⊆ PSPACE\)

2. 以下の問題が NP に属することを示せ： (a) グラフ同型問題 (b) 整数計画問題 (c) 最短ベクトル問題

3. 3-SAT から以下への多項式時間還元を構成せよ： (a) 3-彩色問題 (b) 頂点被覆問題 (c) サイズ管理： (b) の還元で、頂点数・辺数・k の増加が元のインスタンス（変数数 n と節数 m）に対して高々線形（O(n+m)）であることを示せ (d) CLIQUE 問題（クリーク） (e) INDEPENDENT-SET（最大独立集合） (f) CLIQUE → VERTEX-COVER：補グラフと独立集合/頂点被覆の関係を用いて還元を構成し、k の変換（\(\lvert V\rvert - k\)）とサイズ増加が多項式であることを示せ

4. PSPACE = NPSPACE を Savitch の定理を用いて証明せよ。

発展問題

1. 時間階層定理の証明において、対角化言語が求める性質を持つことを詳細に証明せよ。

2. Cook-Levin の定理の証明で、チューリング機械の計算を論理式で符号化する際の具体的な構成を説明せよ。

3. 多項式階層が \(\Sigma_k^{\mathrm{P}}\) で崩壊したとき、実際にすべての上位レベルが \(\Sigma_k^{\mathrm{P}}\) と等しくなることを証明せよ。

4. BPP における誤り確率の増幅技法（amplification）を詳細に解析せよ。

探究課題

1. P vs NP 問題に関する既知の障壁（相対化、自然な証明、代数化）について調査し、なぜこれらが問題解決を困難にするかを論ぜよ。

2. 近似アルゴリズムと複雑性理論の関係を調査し、近似困難性結果（例：PCP定理）について説明せよ。

3. 量子計算複雑性クラス（BQP、QMA等）について調査し、古典的な複雑性クラスとの関係を論ぜよ。

4. 実用的な暗号システムが依拠する困難性仮定を調査し、複雑性理論との関連を説明せよ。

実装課題

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

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

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

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

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