第5章 計算複雑性理論

はじめに

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

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

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: ℕ → ℝ⁺ に対して：

1. Big-O記法：f(n) = O(g(n)) ⟺ ∃c > 0, ∃n₀, ∀n ≥ n₀, f(n) ≤ c·g(n)

2. Big-Ω記法：f(n) = Ω(g(n)) ⟺ ∃c > 0, ∃n₀, ∀n ≥ n₀, f(n) ≥ c·g(n)

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

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

5. 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)

5.1.3 時間複雑性クラス

定義 5.4 時間構成可能関数 t: ℕ → ℕ に対して、 TIME(t(n)) = {L | ある O(t(n)) 時間チューリング機械が L を決定}

定義 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 に対して、 g(n) = o(f(n)/log(f(n))) ならば TIME(g(n)) ⊊ TIME(f(n))

証明の概要：対角化論法を用いる。f(n) 時間で、g(n) 時間機械の動作をシミュレートし、 その結果を反転する機械を構成する。ログ因子はシミュレーションのオーバーヘッドから生じる。 ここで log は任意の底の対数（通常は底2または自然対数）を表す。□

系 5.1 P ⊊ EXPTIME

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

定理 5.2 k-テープチューリング機械が 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.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 を以下のように構成：

1. 長さ ≤ p(

   w

   ) の証明書 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

coNP は「すべての証明書に対して」という全称量化に対応する： L ∈ coNP ⟺ ∃多項式 p, V, w ∈ L ⟺ ∀c (|c| ≤ p(|w|) → V(w, c) = accept)

未解決問題：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）⟺ ∀A ∈ NP, A ≤_p L

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

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

直感的理解：

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

ベン図による可視化：

               +-------------------+
               |   全ての問題      |
               +-------------------+
                       |
       +---------------+---------------+
       |                               |
  +----v----+                  +-------v-------+
  | 決定可能 |                  |  決定不能     |
  +----+----+                  +---------------+
       |
  +----v----+
  |    NP    |-------------------+
  +----+----+                   |
       |                        |
  +----v----+             +-----v-----+
  |   P      |             | NP困難    |
  +---------+             +-----+-----+
       |                        |
  +----v----+             +-----v-----+
  | NP完全  |             | さらに難しい問題 |
  +---------+             +---------------+

具体例での比較：

NP完全問題の例：

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

NP困難だがNP完全でない問題の例：

• 停止問題:
  • NP困難：もし多項式時間で解けたら、NPの全ての問題も解ける
  • NPに属さない：決定不能問題なので
• 一般化された巡回セールスマン問題:
  • NP困難：制約されたバージョンがNP完全
  • 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 ∈ 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完全である。

証明の概要：任意の 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式 φ = (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

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.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

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 L ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

5.4.4 PSPACE完全性

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

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

量化ブール式の例：∀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 に対して：

1. Σₖᴾ ∪ Πₖᴾ ⊆ Σₖ₊₁ᴾ ∩ Πₖ₊₁ᴾ
2. Σₖᴾ = coΠₖᴾ

定理 5.11 以下は同値：

1. PH = PSPACE
2. ある k が存在して PH = Σₖᴾ
3. ある 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（計算論的ゼロ知識） （適切な暗号学的仮定の下で）

章末問題

基礎問題

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

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

3. 3-SAT から以下への多項式時間還元を構成せよ： (a) 3-彩色問題 (b) 頂点被覆問題

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

発展問題

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

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

3. 多項式階層が Σₖᴾ で崩壊したとき、実際にすべての上位レベルが Σₖᴾ と等しくなることを証明せよ。

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 アルゴリズムの比較