計算理論の基礎

概要

本

• 計算理論の基礎 [原著第2版] 1.オートマトンと言語 | Michael Sipser, 太田 和夫, 田中 圭介, 阿部 正幸, 植田 広樹, 藤岡 淳, 渡辺 治

• 計算理論の基礎 [原著第2版] 2.計算可能性の理論 | Michael Sipser, 太田 和夫, 田中 圭介, 阿部 正幸, 植田 広樹, 藤岡 淳, 渡辺 治

• 計算理論の基礎 [原著第2版] 3.複雑さの理論 | Michael Sipser, 太田 和夫, 田中 圭介, 阿部 正幸, 植田 広樹, 藤岡 淳, 渡辺 治

かかった時間

• 7.9 時間 (1 巻)

• 12.6 時間 (2 巻)

• 14.1 時間 (3 巻)

読む前の状態

• 離散数学の基本中の基本は学んだ

• 計算理論については何も知らない状態

感想

1 巻

• 本のタイトル通り、オートマトンと言語を理解できた

  • 有限オートマトン、プッシュダウン・オートマトン、正規言語、文脈自由言語

• 定義をしっかり与えて、証明していくやり方を思い出した

• この後の計算可能性と複雑さが楽しみ

2 巻

• Turing Machine、判定可能性、帰着可能性について学んだ

• 計算可能性について理解した

• 帰着を利用した証明面白い

3 巻

• P vs NP 問題、NP 完全性について理解した

• 時間の複雑さ、領域の複雑さ、階層定理について学んだ

• 他にも近似アルゴリズム、確率的アルゴリズム、交替性、対話証明系などについて学んだ

• 2 巻までの計算可能性についての議論に加え、問題の複雑さについて学べた

読書メモ

0. 序論

• 本書は、計算理論の重要な柱をなす 3 つの分野「オートマトン」「計算可能性」「複雑さ」についての教科書である

  • これら 3 つの分野はすべて「計算機の本質的な能力とその限界は何か？」という疑問に関係している

• 複雑さの理論

  • 何が、問題の難しさ・やさしさを決めているだろうか？

• 計算可能性の理論

  • 複雑さの理論の目的は、問題をかんたんなものと難しいものに分類すること

  • 計算可能性の理論の目的は、解を求められる問題とそうでない問題とに分類すること

• 数学的概念や用語

  • 列

    • 集合は対象とするものの集まりだったのに対し、ものをある順序で並べたものを列(sequence)という

  • 組

    • 有限な列は組(tuple)とも呼ばれる

  • 定義域・値域

    • 関数の入力になりうるものの集合を定義域(domain)という

    • 関数の出力になりうるものの集合を値域(range)という

    • f の定義域が D で値域が R である時、f: D → R のように表す

• 定義・定理・証明

  • この 3 つは我々の計算の理論も含めて、すべての数学分野での中心となる

  • 定義(definition)

    • 我々が用いる「もの」や概念を規定する

  • 証明(proof)

    • 命題が真であることを納得させる論理的な議論のこと

  • 定理(theorem)

    • 真と証明された命題

  • 系(corollary)

    • 定理やその証明から、他の関連した命題も真であることが容易に示せる場合がある。そうした命題を、その定理の系という

• 証明を発見するための一般的な戦略

  • 最初に、証明したい命題を注意深く読もう

  • そして関連するすべての記法を理解しよう

  • その上で、命題を読者自身の言葉で書き直してみよう

  • さらに、命題をいくつかの部分に分けて、それぞれの部分を 1 つずつ考察するとよいだろう

• 証明を作成する時の秘訣

  • 忍耐強さ / 繰り返し / きれいさ / 簡潔さ

1: 正規言語

1.1: 有限オートマトン

• 「計算機とは何であるか？」計算の理論をこの問いから始める

• Markov 連鎖

  • 有限オートマトンに確率的要素を許したもの

• 有限オートマトンの定義

  • 有限オートマトンは 5 個組(Q, Σ, δ, q0, F)である

    • Q は状態(state)と呼ばれる有限集合

    • Σ はアルファベット(alphabet)と呼ばれる有限集合

    • δ: Q × Σ → Q は状態関数(transition function)

    • q0 ∈ Q は開始状態(start state)

    • F ⊆ Q は受理状態の集合(set of accept states)

• 機械の言語

  • A を機械 M が受理するすべての文字列の集合とするならば、A は機械 M の言語(language of machine M)であるといい、L(M) = A と書く

  • また M は A を認識する、あるいは受理するという

  • ある有限オートマトンで認識される言語を正規言語(regular language)という

• 正規演算

  • A と B を言語とする。正規演算とは以下のように定義された和集合演算(union)、連結演算(concatenation)、スター演算(star)のいずれかである。A = {good, bad} かつ B = {boy, girl} とする

    • 和集合演算: A ∪ B = {x | x ∈ A または x ∈ B}

      • A ∪ B = {good, bad, boy, girl}

    • 連結演算: A ❍ B = {xy | x ∈ A かつ y ∈ B}

      • A ❍ B = {goodboy, goodgirl, badboy, badgirl}

    • スター演算: A* = {x1x2...xk | k >= 0 であり、かつ各々の xi に対して xi ∈ A}

      • A* = {ε, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, ... }

• 閉じている

  • その集まりの要素への演算の結果が、またその集まりに含まれるものとなること

1.2: 非決定性

• 決定性

  • 機会がある与えられた状態にあって、次の入力文字を読み出すと、次の状態が何であるかが決まってる。このことを決定性(deterministic)計算と呼ぶ

  • これに対して、非決定性(nondeterministic)機会の場合には、どの時点においても次の状態として複数の選択肢が存在しうる

• 非決定性有限オートマトン(NFA)

  • NFA では、機会はそれ自体のコピーを複数個作成し、すべての可能性を並列にたどる

  • 機械のコピーのどれか 1 つでも受理状態にあれば、NFA は入力文字列を受理する

  • 決定性有限オートマトンは DFA という

• 非決定性有限オートマトンの正式な定義

  • 非決定性有限オートマトンは 5 個組(Q, Σ, δ, q0, F)である

    • Q は状態の有限集合

    • Σ は有限のアルファベット

    • δ: Q × Σε → P(Q) は遷移関数

      • Σεは Σ ∪ {ε} を表す

      • P(Q) は Q のすべての部分集合の集まりを表し、べき集合と呼ぶ

    • q0 ∈ Q は開始状態

    • F ⊆ Q は受理状態の集合

• 等価

  • 2 つの機械が同じ言語を認識する時、これらは等価(equivalent)であるという

• NFA と DFA の等価性

  • すべての非決定性有限オートマトンは、等価な決定性有限オートマトンを持つ

1.3: 正規表現

• 正規表現

  • 言語を記述する表現を作成するために、正規表現と呼ばれる正規演算を用いることができる

  • 正規表現とそれが記述する言語を区別したい時は、正規表現 R の表現する言語を L(R) と書く

• 正規表現の正式な定義

  • R が以下のいずれかであるならば、R は正規表現(regular expression)であるという

    • 1: アルファベット Σ に属する a

    • 2: ε

    • 3: Ø

    • 4: R1 と R2 を正規表現として (R1 ∪ R2)

    • 5: R1 と R2 を正規表現として (R1 ❍ R2)

    • 6: R1 を正規表現として (R1*)

  • 項目 1 と 2 は正規表現 a と ε が、それぞれ言語 {a} と {ε} を表すことを意味している

  • 項目 3 は正規表現 Ø が空言語を表すことを意味している

  • 項目 4・5・6 はそれぞれの表現が、それぞれ言語 R1 と R2 の和集合、連結、および言語 R1 のスターをとることで得られる言語を表すことを意味している

• 一般化非決定性有限オートマトン(GNFA: generalized nondeterministic finite automaton)

  • 遷移を表す矢印のラベルとして単にアルファベットの要素やεだけでなく、正規表現も許されるような非決定性有限オートマトン

  • GNFA は以下の条件に沿った形式を常に持つ

    • 開始状態は他のすべての状態へ遷移する矢印を持つ。しかし他の状態から、開始状態へ遷移する矢印はない

    • ただ 1 つの受理状態があって、他のすべての状態から受理状態への矢印がある。しかし、受理状態から出ていく矢印はない。さらに、受理状態は開始状態ではない

    • 開始状態と受理状態を除いて、どの 2 つの状態も互いに遷移する矢印を持つ

  • GNFA は遷移関数が δ: (Q - {q accept}) × (Q - {q start}) → R という形をしていることを除いて、非決定性有限オートマトンと同じである

    • ただし、R はアルファベット Σ 上のすべての正規表現の集まりを表す

• 一般化非決定性有限オートマトンの正式な定義

  • 一般化非決定性有限オートマトンは 5 個組(Q, Σ, δ, q start, q accept)である

    • Q は状態の有限集合

    • Σ は入力アルファベット

    • δ: (Q - {q accept}) × (Q - {q start}) → R は遷移関数

    • q start は開始状態

    • q accept は受理状態

1.4: 非正規言語

• この節では、有限オートマトンによって認識不可能な言語について考え、有限オートマトンによる言語の認識不可能性の証明方法について説明する

• ポンピング補題(pumping lemma)

  • 非正規性の証明に用いられる技法は、従来からポンピング補題と呼ばれる、正規言語に関する定理をもとにしている

  • A が正規言語であるならば、ある数 p (ポンピング長)が存在して、s が少なくとも長さ p である A の任意の文字列である時に、s は以下の条件を満たす 3 つの断片 s = xyz に分割できる

    • 各 i >= 0 について xy^iz ∈ A

    • |y| > 0

    • |xy| <= p

  • 上記を満たさない場合、その言語は正規ではないことを証明できる

2: 文脈自由言語

• 第 1 章では有限オートマトンと正規表現という 2 種類の本質的に等価な言語の記述方法を紹介した

  • 多くの言語はこの方法で記述できるが、{0^n1^n1 | n >= 0} のようないくつかの単純な言語は記述できないことを示した

• 本章では、より強力な言語記述手法である文脈自由文法(context-free grammar)を与える

2.1: 文脈自由文法

• 文法

  • 文法は、生成規則(production)とも呼ばれる書き換え規則(substitution rule)の集まりからなる

  • A → 0A1 / A → B / B → # のような文法の各行が書き換え規則である

  • 文字列は変数と終端記号(terminal)と呼ばれる別の文字から成り立っている

  • 1 つの変数が開始変数(start variable)として指定され、本書では、それは先頭の規則の左辺に現れる変数を開始変数とみなすことにする

• 導出

  • 文字列を得るための書き換えの列は導出(parse tree)と呼ばれる

  • u ⇒ u1 ⇒ ... ⇒ uk ⇒ v ならば、u は v を導出するという

• 文脈自由文法(CFG: context-free grammer)の正式な定義

  • 文脈自由文法は、4 個組(V, Σ, R, S)である

    • V は変数(variable)と呼ばれる有限集合

    • Σ は終端記号(terminal)と呼ばれる、V と共通部分を持たない有限集合

    • R は変数(左辺)および変数と終端記号からなる文字列(右辺)で構成される規則(rule)の有限集合

    • S ∈ V は開始変数

• 曖昧

  • 2 つの異なる構文解析木を持つことを意味する

  • 正式な定義

    • 文字列 w が 2 つ以上の異なる最左導出を持つならば、その文字列は文脈自由文法 G において曖昧に(ambiguously)導出される。文法 G がある文字列を曖昧に生成するならば、G は曖昧(ambiguous)である

• Chomsky 標準形

  • 正式な定義

    • すべての規則が以下の形である文脈自由文法を Chomsky 標準形(Chomsky normal form)という

      • A → BC

      • A → a

    • ここで a は任意の終端記号、A は任意の変数、そして B と C は開始変数ではない任意の変数である

    • ただし、開始変数 S に対しては、規則 S → ε を加えてもよい

  • 少しわかりやすく書くと

    • ε規則がない

    • 読み換え規則(A → B)がない

    • 長文規則の除去

      • A → u1u2...un (n >= 3) が長文規則

    • 参考: 文脈自由文法のチョムスキー標準形への変換 - yo-kunの日記

2.2: プッシュダウン・オートマトン

• プッシュダウン・オートマトン(PDA: pushdown automaton)

  • プッシュダウン・オートマトンは、非決定性有限オートマトンに似ているが、スタックと呼ばれる構成要素が追加されている

  • プッシュダウン・オートマトンは、文脈自由文法と能力の点で等価である

• プッシュダウン・オートマトンの正式な定義

  • プッシュダウン・オートマトンは 6 個組(Q, Σ, Γ, δ, q0, F)である。ここで Q, Σ, Γ, F は全て有限集合である

    • Q は状態の集合

    • Σ は入力アルファベット

    • Γ はスタック・アルファベット

    • δ: Q × Σε × Γε → P(Q × Γε) は遷移関数

      • Σεは Σ ∪ {ε} を表す

      • Γεは Γ ∪ {ε} を表す

    • q0 ∈ Q は開始状態

    • F ⊆ Q は受理状態の集合

2.3: 非文脈自由言語

• 本節では、言語が文脈自由でないことを証明するための技法を与える

  • ここでは、文脈自由言語に対して同様のポンピング補題を与える

• 文脈自由言語に対するポンピング補題(pumping lemma for context-free languages)

  • 任意の文脈自由言語 A に対して、ある数 p (ポンピング長)が存在して、s が少なくとも長さ p である A の文字列である時に、s は以下の条件を満たす 5 個の断片 s = uvxyz に分割できる

    • 各 i >= 0 について uv^ixy^iz ∈ A

    • |vy| > 0

    • |vxy| <= p

  • 例えば D = {ww | w ∈ {0, 1}*} は CFL(文脈自由言語) ではない

3: CHURCH-TURING の提唱

3.1: TURING 機械

• TURING 機械

  • TURING 機械は、1936 年に Alan Turing により最初に提案された

  • 有限オートマトンと似ているが、量に関しても使い方に関しても制限がないメモリを持つ Turing 機械は、汎用計算機のはるかに正確なモデル

  • Turing 機械モデルは量に関して制限がないメモリとして無限長のテープを使うことができる

  • このテープに対して、テープ上を動きまわり、テープ上に文字を読み書きできるテープ・ヘッドを持つ

• Turing 機械の概要(有限オートマトンと Turing 機械の違い)

  • Turing 機械は、テープに対し書き込みと読み出しのどちらでもできる

  • 読み書きヘッドは、左右のどちらにも動くことができる

  • テープは無限長である

  • Turing 機械は拒否や受理に対応する特別な状態に入ると、すぐに停止する

• Turing 機械の正式な定義

  • Turing 機械は 7 個組(Q, Σ, Γ, δ, q0, q accept, q reject)である。ここで Q, Σ, Γ はすべて有限集合であり

    • Q は状態の集合

    • Σ は空白文字(blank symbol) _ を含まない入力アルファベット

    • Γ は _ ∈ Γ かつ Σ ⊆ Γ であるようなテープ・アルファベット

    • δ: Q × Γ → Q × Γ × {L, R} は遷移関数

    • q0 ∈ Q は開始状態

    • q accept ∈ Q は受理状態

    • q reject ∈ Q は q reject != q accept であるような拒否状態

• Turing 機械の計算状況(configuration)

  • Turing 機械が計算する時は、状態、テープの内容、ヘッドの位置に変化が生じる

  • これら 3 つの項目の設定値は、Turing 機械の計算状況と呼ばれる

  • 状態 q とテープ・アルファベット Γ 上の 2 つの文字列 u と v に対して、uqv と書いて、現在の状態が q、現在のテープ内容が uv、現在のヘッドの位置が v の最初の文字であるような計算状況を表す

• Turing 認識可能(Turing-recognizable)

  • 任意の言語に対して、それを認識する Turing 機械が存在する時、その言語を Turing 認識可能と呼ぶ

• ループ

  • Turing 機械を始動させる時、受理・拒否・ループの 3 つの結果が可能

  • ループとは、単に機械が停止しないことを意味する

  • すべての入力に対して、決してループしない Turing 機械が好ましい

• Turing 判定可能(Turing-decidable)

  • 任意の言語に対して、それを判定する Turing 機械が存在する時、その言語を Turing 判定可能、あるいは単に判定可能と呼ぶ

3.2: TURING 機械の変型

• Turing 機械の変型(variant)

  • Turing 機械の別定義は、複数のテープを持つものや非決定性を満たすものなどたくさんある。これらは Turing 機械モデルの変型と呼ばれる

  • 定義の変形に対するモデルの不変性を頑健性(robustness)と呼ぶ

• 列挙装置(enumerator)

  • Turing 認識可能な言語に対して、帰納的列挙可能な言語(recursively enumerable language)という用語を用いる人もいる

  • おおまかに定義すると、列挙装置はプリンタの接続された Turing 機械である

3.3: アルゴリズムの定義

• アルゴリズムの定義

  • 簡単に言えば、アルゴリズムはある課題を処理するための単純な命令の集まり

• Hilbert の問題

  • Hilbert の第 10 問題は、多項式が整数解を持つかどうかを検査するアルゴリズムを考案すること

• Turing 機械を記述するための用語

  • 3 つの可能性

    • Turing 機械の状態、遷移関数などを全部、順序を追って詳細に説明する正式な記述(formal description)

    • Turing 機械がヘッドを動かす方法やテープにデータを格納する方法まで記述するが、それを自然言語で記述する方法。より高いレベルの記述だが、実装まで考慮した記述(implementation description)

    • 実装の詳細を無視して、アルゴリズムを記述するために自然な言語を用いた高レベルの記述(high-level description)

4: 判定可能性

• 解決不可能性を研究すべき理由

  • 問題がアルゴリズム的にいつ解決不可能となるか知ることは有用

  • 教養上の理由

4.1: 判定可能な言語

• 正規言語に関連する判定可能問題

  • 受理問題(acceptance problem)

    • 特定の決定性有限オートマトンが与えられた文字列を受理するかどうかを検査するような DFA に対する受理問題は、言語 A DFA として表現できる

    • この言語は DFA とそれが受理する文字列の組を符号化したものの全体で A DFA = {<B, w> | B は入力文字列 w を受理する DFA}

    • DFA B が入力 w を受理するかどうかを検査する問題は が言語 A DFA の要素であるかどうかを検査する問題と同じ

    • 同様に非決定性有限オートマトンに対して、A NFA = {<B, w> | B は入力文字列 w を受理する NFA}

    • さらに正規表現について、A REX = {<R, w> | R は文字列 w を生成する正規表現}

  • 空性検査(emptiness testing)

    • 有限オートマトンの言語に対する空性検査は E DFA = {<A> | A は DFA、かつ L(A) = Ø} で表現される

    • 2 つの DFA が同じ言語を認識するかどうか EQ DFA = {<A, B> | A と B は DFA、かつ L(A) = L(B)} と表現する

• 文脈自由言語に関連する判定可能問題

  • CFG が特定の文字列を生成するかどうかを決定する問題 A CFG = {<G, w> | G は文字列 w を生成する CFG}

  • CFG の言語に対する空性検査問題 E CFG = {<G> | G は CFG、かつ L(G) = Ø}

  • 2 つの文脈自由文法が同じ言語を生成するか決定する問題 EQ CFG = {<G, H> | G と H は CFG、かつ L(G) = L(H)}

  • すべての文脈自由言語は Turing 機械により判定可能

    • よって、正規、文脈自由、判定可能、Turing 認識可能の間の関係図は、正規 < 文脈自由 < 判定可能 < Turing 認識可能、となる

4.2: 停止問題

• 本節では、計算の理論における哲学的に最も重要な定理の 1 つ「アルゴリズム的に解決不可能な問題がある」を証明する

• Turing 機械が与えられた入力文字列を受理するかどうかの問題(停止問題: halting problem)

  • A TM = {<M, w> | M は TM であり、M は w を受理する} として表現される

  • A DFA と A CFG が判定可能であるのに対して、A TM はそうではない

    • M が w に対してループするならば、この機械は A TM を判定しない(TM は有限オートマトンと異なり、無限の入力が与えられる)

  • 停止性をアルゴリズム的に決定する方法は存在しない

• 対角線論法

  • 定義

    • 集合 A と B、および A から B への関数 f があると仮定しよう。f が 2 つの異なる要素を同じ値に決して写像しない、つまり a != b である時はいつでも f(a) != f(b) であるならば、f は一対一(one-to-one)であるという

    • また、f が B のすべての要素に当たる、つまりすべての b ∈ B に対して、f(a) = b となる a ∈ A があるならば、f は上への(onto)関数であるという

    • 一対一かつ上への関数 f: A → B が存在する時、A と B は同じサイズであるという

    • 一対一かつ上への関数は、対応(correspondence)と呼ばれる

    • 対応においては、A のすべての要素は B の要素に一意的に写像され、B の各々の要素はそれに写像される A の要素をただの 1 つ持つ。対応は、A の要素と B の要素を対にする方法である

• 可算(countable)

  • 集合 A が有限であるか N(自然数の集合)と同じサイズを持つならば、A は可算である

  • N より大きい集合は非可算(uncountable)と呼ばれる

    • 実数の集合 R は非可算である

• Turing 認識可能でない言語が存在する

  • Turing 機械の集合は可算

  • すべての言語の集合は非可算

  • そのため、すべての言語の集合はすべての Turing 機械の集合と対応させられないことが示された。したがって、いくつかの言語はいかなる Turing 機械によっても認識されない

• 補 Turing 認識可能(co-Turing-recognizable)

  • ある言語が Turing 認識可能な言語の補集合であるならば、その言語は補 Turing 認識可能であるという

• 任意の言語に対して、それが Turing 認識可能かつ、補 Turing 認識可能である時、かつその時に限り、その言語は判定可能

  • そのため、A TM の補集合は認識可能ではない

5: 帰着可能性

• 帰着(reduction)

  • ある問題を他の問題に変換する方法で、しかも後者の問題の解を前者の問題を解くために利用できるように変換する方法

  • A を B に帰着できる時には、B に対する解が A に対する解を与える

  • A が B に帰着可能でかつ B が判定可能ならば、A もまた判定可能となる

  • 言い換えれば、A が判定不可能であり、B に帰着可能ならば B も判定不可能となる

5.1: 言語理論における判定不可能問題

• HALT TM

  • Turing 機械が与えられた入力で停止するかを決定する問題

  • HALT TM = {<M, w> | M は TM であり、M は入力 w に対して停止する}

  • HALT TM は判定不可能。A TM が HALT TM に帰着可能であるため

• E TM

  • E TM = {<M> | M は TM であり、L(M) = Ø}

  • E TM も判定不可能

• REGULAR TM

  • REGULAR TM = {<M> | M は TM であり、L(M) は正規言語}

  • REGULAR TM も判定不可能

• 同様にして、Turing 機械の受理する言語が文脈自由言語、判定可能言語、あるいは有限言語であるかどうかの検査までもが、判定不可能であることを示せる

• ここでは、A TM からの帰着を利用しているが、他の判定不可能な言語からの帰着のほうが都合が良いこともある

• 計算履歴

  • 定義

    • M が Turing 機械であり、w を入力文字列とする。M の w に対する受理計算履歴(accepting computation history)とは、C1 が M の w に対する開始状況であり、Cl が M の受理状況であり、それぞれの Ci が M の規則に従って Ci-1 から正当に導かれるような、一連の計算状況の列 C1, C2, ..., Cl である

    • M の入力 w に対する拒否計算履歴(rejecting computation history)とは、Cl が拒否状況であることを除いて、同様に定義される

  • 計算履歴は有限の列。M が w に対して停止しないならば、w に対する M には、受理計算履歴あるいは拒否計算履歴は存在しない

  • 決定性の機械は、1 つの入力に対して、高々 1 つの計算履歴を持つ。非決定性の機械は、1 つの入力に対して、いろいろな計算分岐に対応した多数の計算履歴を持つことがある

• 線形境界付きオートマトン(LBA: linear bounded automaton)

  • 線形境界付きオートマトンは、テープのヘッドがテープの入力を含む部分から離れることが許されないような、限定された Turing 機械である。通常の Turing 機械のテープの左端を離れないのと同じ原理で、ヘッドが入力のいずれかの端から離れようとしても、ヘッドがその場所にとどまるように機械が設計されている

  • つまり、長さが n の入力に対して、使用可能なメモリ量は n に対して線形となる

• A LBA(LBA が入力を受理するかどうかを決定する問題)

  • A LBA = {<M, w> | M は文字列 w を受理する LBA}

  • これは判定可能

  • 以下の補題のため

    • M を q 個の状態とテープ・アルファベットとして g 個の文字を持つ LBA とする。長さ n のテープに対して、ちょうど q * n * g^n 個の M の異なる計算状況が存在する

  • これが有限個なので、入力 w に対して、q * n * g^n ステップ以内で停止しなければループしているとわかる

• E LBA

  • E LBA = {<M> | M は L(M) = Ø}

  • これは判定不可能。E LBA が判定可能ならば A TM もそうなることを示せる

5.2: 単純な判定不可能問題

• Post の対応問題(PCP: Post correspondence problem)

  • PCP = {<P> | P はマッチを持つ Post 対応問題の入力例}

  • PCP は判定不可能

5.3: 写像帰着可能性

• 計算可能な関数(computablwe function)

  • 関数 f: Σ* → Σ* について、任意の入力 w に対して Turing 機械 M が f(w) をテープ上に設定して停止するならば、その f を計算可能な関数であるという

• 写像帰着可能性(mapping reducibility)

  • 計算可能な関数 f: Σ* → Σ* が、任意の w に対して、w ∈ A ⇔ f(w) ∈ B を満たす時、言語 A は言語 B へ写像帰着可能性であるといい、A <=m B と表す。この関数 f を A の B への帰着という

  • 写像帰着という用語は、帰着の手段を与えているのが関数、すなわち写像という点に由来する

6: 計算可能性の理論における先進的な話題

6.1: 再帰定理

• 自己参照

  • まずは入力を無視し、自分自身の記述のコピーを出力する Turing 機械を作ることから始める

  • w を任意の文字列とすると、q(w) が w を出力して停止する Turing 機械 Pw の記述であるような計算可能な関数 q: Σ* → Σ* が存在する

Q = 「入力文字列 w に対して:
    1. 次のような Turing 機械 Pw を構成する:
        Pw = 「任意の入力に対して:
            1. 入力を消去する
            2. テープに w を書き込む
            3. 停止する」
    2. <Pw> を出力する」

• 再帰定理(Recursion Theorem)

  • T を関数 t: Σ* × Σ* → Σ* を計算する Turing 機械とする。このとき、すべての w に対して r(w) = t(<R>, w) となる関数 r: Σ* → Σ* を計算する Turing 機械 R が存在する

  • ようは自分自身の記述 <R> を受け取り、それを使った計算を行える機械 T を作れる

  • これを使うことで、機械 M を設計しようとする時に、M のアルゴリズムの記述の中に「自分自身の記述 <M> を得る」という文章を含めることができる

    • ここで自分自身の記述を得るということは、その記述をそれ以降の計算で使えるということである

• MIN TM

  • Turing 機械 M に対して、M の記述の長さを文字列 <M> の文字数であるとする。M と等価な、より短い記述を持つ Turing 機械がないならば、M は最小(minimal)であるという

  • MIN TM = {<M> | M は最小 TM}

  • MIN TM は Turing 認識不可能である

6.2: 数理論理における判定可能性

• 真偽を判定できる領域と、判定不可能な領域がある

6.3: TURING 帰着可能性

• オラクル Turing 機械(oracle turing machine)

  • 言語 B に対するオラクル(oracle)は、任意の文字列 w が B の要素であるかどうかを告げることができる外部装置である。オラクル Turing 機械は、オラクルに質問する付加能力を持つように変更された Turing 機械である

  • M^B と書いて、言語 B に対するオラクルを持つオラクル Turing 機械を表す

• Turing 帰着可能(Turing reducible)

  • 言語 A が言語 B に対して相対的に判定可能ならば、A は B に Turing 帰着可能であると定義し、この関係を A <=T B と書く

6.4: 情報の定義

• アルゴリズムと情報という概念は計算機科学の基礎である

• 対象物に含まれる情報量の定義として、その対象物の最小の表現のサイズ、あるいは最小記述のサイズと定義する

  • その対象物よりも極端に短い記述は、含まれる情報が小さい量に圧縮できることを表している

• 最小記述(minimal description)

  • x を二進文字列とする。x の最小記述を d(x) と書く。これはテープ上に x を設定して停止する TM M と入力 w の対のうちで、その記述 の長さが最短のものを指す

  • このような記述が複数存在するならば、その中で辞書式順序で最初のものを選ぶ

  • x の記述の複雑さ(descriptive complexity)を K(x) と書き、K(x) = |d(x)| とする

  • 言い換えると K(x) は x の最小記述の長さ

• 関連する定理

  • ∃c∀x [K(x) <= |x| + c]

  • ∃c∀x [K(xx) <= |x| + c]

  • ∃c∀x,y [K(xy) <= 2 * K(x) + K(y) + c]

• 圧縮不可能(incompressible)

  • 定義

    • x を文字列とする。K(x) = |x| - c であるとき、x は c 圧縮可能(c-compressible)であるという

    • x が c 圧縮可能でない時、x は c で圧縮不可能(incompressible by c)であるという

    • x が 1 で圧縮不可能な時、x は圧縮不可能であるという

• あらゆる長さに対して、その長さの圧縮不可能な文字列が存在する

7: 時間の複雑さ

7.1: 複雑さの測定

• 多項式境界(polynomial bound)

  • 0 より大きい c に対して n^c という形の上界(一般には境界)を得る場合、このような境界は多項式境界と呼ばれる

• 指数境界(exponential bound)

  • 2^(n^δ) という形の境界で、δ が 0 より大きい実数の時、指数境界と呼ばれる

• 計算可能性の理論と複雑さの理論との違い

  • 計算可能性の理論では、Church-Turing の提唱により、すべての適切な計算モデルが等価である

  • 複雑さの理論では、計算モデルの違いにより、言語の難しさの評価が変わる

    • 解を求めるのに必要となる時間量に従って、計算問題を分類することが要求される

• モデル間の複雑さの関係

  • 単一テープ Turing 機械と複数テープ Turing 機械

    • t(n) を t(n) >= n であるような関数とする。この時、すべての t(n) 時間複数テープ Turing 機械に対して、それと等価な Ｏ(t^2(n)) 時間単一テープ Turing 機械が存在する

  • 単一テープ Turing 機械と非決定性 Turing 機械

    • t(n) を t(n) >= n であるような関数とする。この時、すべての t(n) 時間非決定性 Turing 機械に対して、それと等価な 2^Ｏ(t(n)) 時間単一テープ Turing 機械が存在する

7.2: クラス P

• 多項式の違いと指数の違い

  • 決定性の単一テープと複数テープの Turing 機械で測られた時間計算量の間には高々 2 乗、すなわち多項式の違いしかない

  • 一方、決定性と非決定性の Turing 機械の時間計算量の違いは高々指数である

  • 以下の議論では、動作時間の多項式の違いは小さいものと考え、指数の違いは大きいものと考える

• クラス P

  • 定義

    • P を決定性単一テープ Turing 機械によって多項式時間で測定できる言語のクラスとする

  • P は我々の理論の中で中心的な役割を果たす重要クラス

    • P は、決定性単一テープ Turing 機械に多項式で等価なすべての計算モデルで不変である

    • P は、計算機で現実的に解くことができる問題のクラスにほぼ対応している

• P に属する問題の記述

  • 多項式時間であることを示したい場合は、以下に述べる慣例に従ってアルゴリズムを記述する場合が多い

    • Turing 機械と同様、アルゴリズムは番号付きのステージで記述する

    • さらに以下の 2 つを行う

      • 長さ n の入力が与えられた時の、そのアルゴリズムで実行されるステージ数の多項式の上界を与える

      • 各々のステージが、妥当な決定性計算モデル上において多項式時間で実現できることを確認する

7.3: クラス NP

• 多項式検証可能性(polynomial verifiability)

  • 多項式時間で解を探すことは難しいが、解を検証することは多項式時間で計算可能という性質

  • 定義

    • アルゴリズム V に対して、言語 A を次のように定義できる時、V を A の検証装置(verifier)という

    • A = {w | V はある文字列 c に対して <w, c> を受理}

    • 検証装置の計算時間は w の長さに関してのみ測る

    • よって多項式時間検証装置(polynomial time verifier)とは、w の長さに対して多項式時間で(c の)検証を行うアルゴリズムである

    • A を多項式検証可能(polynomial verifiable)という

• クラス NP

  • NP は多項式時間検証装置を持つ言語のクラスである

  • NP という略称は非決定性多項式時間(nondeterministic polynomial time)に由来している

  • 言語が非決定性多項式時間 Turing 機械で判定される時、かつその時に限り、その言語は NP に属する

• 非決定性の時間計算量のクラス

  • NTIME(t(n)) = {L | L は Ｏ(t(n)) 時間の非決定性 Turing 機械で判定される言語}

• P vs NP 問題

  • P = 要素であるかどうかを速く判定できる言語のクラス

  • NP = 要素であることが(補助情報をもとに)速く検証できる言語のクラス

  • しかし、P と NP は等しいこともありうる。「P = NP は成り立つか」(P vs NP 問題と呼ばれる)という問いは理論計算機科学と現代科学の最も重要な未解決問題のうちの 1 つ

7.4: NP 完全性

• 充足可能性問題(satisfiability problem)

  • 例えば φ = (not x ∧ y) ∨ (x ∧ not z) という Boole 論理式があるとする。条件を満たす x, y, z が割り当てられる時、Boole 論理式は充足可能(satisfiable)であるという

  • 充足可能性問題は、Boole 論理式が充足可能であることを検査する問題

  • SAT = {<φ> | φ は充足可能な Boole 論理式}

• 多項式時間計算可能関数(polynomial time computable function)

  • 任意の入力 w で動作を開始し、テープに f(w) だけを設定して停止するような多項式時間 Turing 機械 M が存在する時、関数 f: Σ* → Σ* は多項式時間計算可能関数であるという

• 多項式時間帰着可能(polynomial time reducible)

  • 言語 A と B に対して、多項式時間計算可能関数 f: Σ* → Σ* が存在して、すべての w について、w ∈ A ⇔ f(w) ∈ B である時、A <=P B と書き、言語 A が言語 B に多項式時間写像帰着可能(polynomial time mapping reducible)、あるいは単に多項式時間帰着可能であるという。関数 f は A から B への多項式時間帰着(polynomial time reduction)と呼ばれる

  • A <=P B かつ B ∈ P ならば A ∈ P である

• これを利用して 3SAT は CLIQUE に多項式時間帰着可能であることを示せる

• NP 完全

  • 次の条件を満たす言語 B を NP 完全(NP-complete)という

    • B ∈ NP

    • NP に属するすべての A が、B に多項式時間帰着可能である

  • B が NP 完全であり、かつ B ∈ P ならば、P = NP である

• Cook-Levin の定理(Cook-Levin theorem)

  • P = NP の時、かつその時に限り SAT ∈ P である

  • SAT は NP 完全である

    • 証明は本文にわかりやすく書かれてる

  • また 3SAT も NP 完全である

• 他の NP 完全問題

  • クリーク問題

    • 無向グラフ中のクリークはすべての節点が辺によって連結されている部分グラフ。k クリークは k 個の節点を含むクリークである

    • クリーク問題はグラフがある特定のサイズのクリークを含むかを決定する

    • CLIQUE = {<G, k> | G は k クリークを持つ無向グラフ}

  • 頂点被覆問題

    • G が無向グラフの時、G の頂点被覆(vertex cover)は節点の部分集合であり、G のすべての辺がそれらの節点の 1 つに接触している。頂点被覆問題は最小の頂点被覆のサイズを求める問題

    • VERTEX-COVER = {<G, k> | G は k 個の節点からなる頂点被覆を持つような無向グラフ}

  • Hamilton パス問題

    • Hamilton パス問題は、すべての節点をちょうど 1 度通るような s から t へのパスを入力グラフが含むかどうかを判定する問題

    • Hamilton パス問題の無向グラフ版については UHAMPATH と呼ばれる。これも NP 完全である

  • 部分和問題

    • 数 x1, ..., xk の集まりと目標の数値 t が与えられる。その集まりの中からいくつかを取り出して、その和が t となるかを判定する

    • SUBSET-SUM = {<S, t> | S = {x1, ..., xk} で、ある {y1, ..., yl} ⊆ {x1, ..., xk} に対して Σyi = t}

8: 領域の複雑さ

• 領域計算量(space complexity)

  • M をすべての入力に対して停止する決定性 Turing 機械とする。関数 f(n) を長さ n の任意の入力に対して M が操作するテープのセル数の最大値とする時、M の領域計算量を f: N → N と定義する。M の領域計算量が f(n) の時、M は領域 f(n) で動作するとも言う

  • M をすべての入力に対してすべての枝が停止するような非決定性 Turing 機械とする時、領域計算量 f(n) を長さ n の任意の入力に対する M の計算の任意の枝上で M が操作するテープのセル数の最大値と定義する

• 領域計算量のクラス

  • f: N → R+ を関数とする。領域計算量のクラス(space complexity class) SPACE(f(n)) と NSPACE(f(n)) を次のように定義する

  • SPACE(f(n)) = {L | L は Ｏ(f(n)) 領域の決定性 Turing 機械によって判定される言語}

  • NSPACE(f(n)) = {L | L は Ｏ(f(n)) 領域の非決定性 Turing 機械によって判定される言語}

8.1: SAVITCH の定理

• Savitch の定理

  • f(n) >= n を満たす任意の関数 f: N → R+ に対して NSPACE(f(n)) ⊆ SPACE(f^2(n)) である

• 遷移可能性問題(yieldability problem)

  • NTM の 2 つの計算状況 c1 と c2 が数 t と共に与えられ、その NTM が c1 から c2 に t ステップで到達するかを判定する問題を考える

  • c1 から c2 という状況が起きるかを判定する問題なので、この問題を遷移可能性問題と呼ぶ

8.2: クラス PSPACE

• PSPACE

  • PSPACE は決定性 Turing 機械によって多項式領域で判定可能な言語のクラスである

  • PSPACE と P や NP との関係

    • P ⊆ PSPACE

    • NP ⊆ NPSPACE

  • ここまでに定義した複雑さのクラスに関して知られている包含関係

    • P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME

8.3: PSPACE 完全性

• PSPACE 完全(PSPACE-complete)

  • 次の条件を満たす言語 B を PSPACE 完全という

    • 1: B は PSPACE に属し

    • 2: PSPACE に属するすべての A が B に多項式時間帰着可能

  • B が条件 2 のみを満たす時、PSPACE 困難(PSPACE-hard)という

• 完全性を定義する時の一般的なルール

  • 複雑さのクラスに対する完全問題を定義する時、帰着の計算にはそのクラス自身を定義するために用いたモデルよりも、計算能力の弱い(と予想される)計算モデルを使わねばならない

• 限定子(quantifier)

  • ∀ は全称限定子(universal quantifier)、∃ は存在限定子(existential quantifier)と呼ばれる

  • 限定子の順序が重要で、∀x∃y[y > x] は真だが ∃y∀x[y > x] は偽となる

  • 論理式中のすべての変数がいずれかの限定子で束縛されている時、その論理式は完全に限定された(fully quantified)論理式であるという

• 冠頭標準形(prenex normal form)

  • すべての限定子が命題の最初に現れて、それぞれの限定子の範囲はそれ以降の文全体となるように記述を制限された命題

• TQBF(true quantified boolean formula)問題

  • TQBF 問題は、完全に限定された Boole 論理式が真か偽かを決定するものである

  • 言語 TQBF を TQBF = {<φ> | φ は値が真である完全に限定された Boole 論理式}

  • TQBF は PSPACE 完全である

• 論理式ゲーム(formula game)

  • φ = ∃x1 ∀x2 ∃x3 ... Qxk [ψ] を冠頭標準形の限定された Boole 論理式とする

  • この論理式に対して、プレーヤ A とプレーヤ E と呼ばれる 2 人が、変数 x1, ..., xk の値を順番に選択する

  • プレーヤ A は ∀ 限定子で束縛された変数に対する値を選択肢、プレーヤ E は ∃ 限定子で束縛された変数に対する値を選択する

  • 指し手の順番は、式 φ における限定子の順番と同じものとする

  • 全ての限定子に対応する指し手が決まった段階で、それまでにプレーヤたちが変数に対して選択してきた値を変数に代入して ψ を評価する

  • もし ψ が TRUE ならばプレーヤ E の勝ち、FALSE ならばプレーヤ A の勝ちというように勝敗を決める

• 必勝戦略(winning strategy)

  • 両方のプレーヤが最善手を取った時に、一方のプレーヤが勝つ時、そのプレーヤはゲームの必勝戦略を持つという

  • FORMULA-GAME = {<φ> | プレーヤ E が φ に対する論理式ゲームにおいて必勝戦略を持つ}

  • FORMULA-GAME は PSPACE 完全である

• 一般化しりとり(generalized geography)

  • 指定された開始節点を持った任意の有向グラフに対して、プレーヤ達はグラフ中での単純パスを形成する節点を交互に選んでいく

  • パスが単純であるという要求は、同じ節点を繰り返してはならないという要求に対応する

  • 最初にパスを延ばすことができなくなったプレーヤがそのゲームに負ける

  • GG = {<G, b> | プレーヤ 1 がグラフ G 上で節点 b で開始する一般化しりとりで必勝戦略を持つ}

  • GG は PSPACE 完全である

8.4: クラス L とクラス NL

• クラス L とクラス NL

  • クラス L

    • L を決定性 Turing 機械上で対数領域で判定可能な言語のクラスとする

    • すなわち L = SPACE(log n)

  • クラス NL

    • NL を非決定性 Turing 機械上で対数領域で判定可能な言語のクラスとする

    • すなわち NL = NSPACE(log n)

• 例えば PATH 問題は NL に属する

  • PATH = {<G, s, t> | G は s から t への有向パスを持つ有向グラフ}

8.5: NL 完全性

• 対数領域帰着可能性(log space reducibility)

  • 対数領域変換装置(log space transducer)は読み出し専用入力テープ、書き込み専用出力テープ、読み書き作業テープを持つ Turing 機械である

    • 作業テープには Ｏ(log n) 個の文字を書き込むことができる

  • 対数領域変換装置 M は関数 f: Σ* → Σ* を計算する

  • ここで f(w) は M がその入力テープに w を持って開始した時、それが停止した後に出力テープ上に残っている文字列である

  • このような M を持つ f を対数領域計算可能な関数(log space computable function)と呼ぶ

  • 言語 A が対数領域計算可能な関数 f により言語 B に写像帰着可能な時、A は B に対数領域帰着可能(log space reducible)といい、A <=L B と書く

• NL 完全(NL-complete)

  • 次の条件を満たす言語 B を NL 完全という

    • B ∈ NL

    • NL に属する全ての A が B に対数領域帰着可能

  • PATH は NL 完全となる

8.6: NL と coNL の等価性

• coNL

  • NL 中の言語の補言語からなる新しい複雑さのクラスを coNL とする

  • NL ではないことを検証する

• NL = coNL

  • 直観的には異なるように思えるが、この 2 つは等価である

• 様々な複雑さのクラス間の関係

  • L ⊆ NL = coNL ⊆ P ⊆ PSPACE

9: 問題の扱いにくさ

• 扱いにくい(intractable)問題

  • 計算問題の中には、原理的には解くことができるが、解こうとすると膨大な時間あるいは領域が必要となり、とても実際には解くことができないものがある

  • そのような問題は扱いにくい問題と呼ばれる

  • 第 7 章と第 8 章では、扱いにくいと思われるが扱いにくいことの証明が今のところ得られていない問題をいくつか紹介した。それに対し、本章では扱いにくいことが証明できる問題の例を紹介する

9.1: 階層定理

• 階層定理(hierarchy theorem)

  • 階層定理という用語を用いる理由は、時間や領域の複雑さのクラスが単一でないことから来ている

  • 計算の複雑さのクラスは、階層的な構造を持っている

• 領域構成可能(space contructible)

  • f(n) が少なくとも Ｏ(log n) である関数 f: N → N に対して、Ｏ(f(n)) の領域計算量で入力文字列 1^n から f(n) (の二進表現)を計算できる時、f を領域構成可能あるいは領域的に構成可能という

  • Ｏ(log n) 以上の関数、すなわち log2 n, n * log2 n, n^2 のような関数はすべて領域的に構成可能

  • 1^n は n 個の 1 からなる文字列

  • 例えば 1^n から log2 n の二進表現を求める計算を考える。まず、入力テープに沿って入力される 1 の個数を数え、作業テープ上で二進で表現する。この二進表現された n のビット数を数えることにより log2 n を計算できる。したがって log2 n は領域構成可能である

• 領域階層定理(space hierarchy theorem)

  • 領域構成可能な任意の関数 f: N → N に対して、Ｏ(f(n)) 領域で判定可能であり、o(f(n)) 領域で判定不可能な言語 A が存在する

  • ある領域を使用する機械は、他の漸近的に小さいいかなる領域を使用する場合よりも多くの言語を計算できる

• 任意の 2 つの空間構成可能な関数 f1, f2: N → N に対して、f1(n) が o(f2(n)) ならば、SPACE(f1(n)) ⊆≠ SPACE(f2(n)) が成り立つ(含まれるがイコールではない)

  • 同じように 0 <= ε1 < ε2 なる任意の実数 ε1 と ε2 に対して SPACE(n^ε1) ⊆≠ SPACE(n^ε2) が成り立つ

  • また NL ⊆≠ PSPACE であり、PSPACE ⊆≠ EXPSPACE

• 時間構成可能(time constructible)

  • t(n) が少なくとも Ｏ(n * log n) である関数 t: N → N に対して、Ｏ(t(n)) の時間計算量で入力文字列 1^n から t(n) の二進表現を計算できる時、t を時間構成可能あるいは時間的に構成可能という

  • Ｏ(n * log n) 以上の関数、すなわち n * log n, n * √n, n^2, 2^n のような関数はすべて時間的に構成可能

• 時間階層定理(time hierarchy theorem)

  • 時間構成可能な任意の関数 t: N → N に対して、Ｏ(t(n)) 時間で判定可能であり、o(t(n) / log t(n)) 領域で判定不可能な言語 A が存在する

• t1(n) が o(t2(n) / log t2(n)) であり、かつ t2 が時間的に構成可能である任意の 2 つの関数 t1, t2: N → N に対して、TIME(t1(n)) ⊆≠ TIME(t2(n)) が成り立つ(含まれるがイコールではない)

  • 同じように 1 <= ε1 < ε2 なる任意の実数 ε1 と ε2 に対して TIME(n^ε1) ⊆≠ TIME(n^ε2) が成り立つ

  • また P ⊆≠ EXPTIME

• EXPSPACE 完全(EXPSPACE-complete)

  • 次の条件を満たす言語 B を EXPSPACE 完全という

    • B ∈ EXPSPACE

    • EXPSPACE に属するすべての A が B に多項式時間帰着可能

• EQ REX↑

  • EQ REX↑ = {<Q, R> | Q と R は等価な一般化正規表現}

  • EQ REX↑は EXPSPACE 完全である

9.2: 相対化

• 相対化(relativization)

  • 相対化技法では、今までの計算モデルを修正し、TM がある種の情報を「無料」で得られるようにする

  • 充足問題を解く「ブラック・ボックス」が機械に取り付けられたと考える。これをオラクルと呼ぶ

  • すべての NP 問題は充足問題に多項式時間帰着可能なので、P が NP に等しいか否かに関わらず、そのオラクルを用いれば、任意の NP 問題に対して、それを多項式時間で解く TM を構成できる

  • そのような TM の計算は、充足問題と相対的な計算と呼ばれている

• オラクル Turing 機械

  • 言語 A に対するオラクル(Oracle) は、任意の文字列 w が A に所属するか否かを教えてくれる装置である

  • オラクル Turing 機械(Oracle Turing machine) M^A はオラクルに問い合わせることができるように変形された Turing 機械である

  • M^A は実行中にオラクル・テープ(oracle tape)に文字列を書き込み、オラクル A にその文字列が A に含まれるかどうかの判定を問い合わせることができる。しかも、その判定結果は 1 ステップで与えられる

  • P^A をオラクル A を用いたオラクル Turing 機械が多項式時間で判定可能な言語のクラスとする。NP^A も同様に定義する

• 対角線論法の限界

  • P^A と NP^A が異なり、P^B と NP^B が等価となるようなオラクル A と B が存在する

  • このようなオラクルの存在によって、P vs NP 問題は対角線論法によっては解決できそうにないことが示される

  • P vs NP 問題を解くためには、単に計算をシミュレートするのではなく、解析しなければならない

9.3: 回路の複雑さ

• TM と Boole 回路の関連を調べていく 2 つの目的

  • 回路は P vs NP およびそれに関連する問題に挑戦するのに便利な計算モデルと期待されている

  • 回路を使うと、SAT が NP 完全であるという Cook-Levin の定理に別の証明を与えることができる

• パリティ関数(parity function)

  • n 入力パリティ関数 prity n: {0, 1}^n → {0, 1} は、入力変数に奇数個の 1 が含まれている場合に 1 を出力する関数

• 回路族(circuit family)

  • Cn を n 個の入力変数を持つ 1 つの回路とすると、回路族 C は回路の無限リスト(C0, C1, C2,...)である

  • すべての文字列 w に対して、n を w の長さとして Cn(w) = 1 の時、かつその時に限り w ∈ A となる時、C は {0, 1} 上の言語 A を判定するという

• 複雑さ

  • 言語の回路サイズの複雑さ(circuit size complexity)とは、その言語を判定する最小の回路族のサイズの複雑さである

  • 言語の回路深さの複雑さ(circuit depth complexity)も同様に定義される

• t: N → N を t(n) >= n なる関数とする。A ∈ TIME(t(n)) ならば、A の回路計算量は Ｏ(t^2(n)) である

  • この定理を利用すると、NP に入るある言語が多項式より大きな回路計算量を持つことを示すことで P != NP を証明できる。これは P != NP を証明するための対角線論法とは異なるアプローチである

10: 計算の複雑さの理論における先進的な話題

10.1: 近似アルゴリズム

• 最適化問題(optimization problems)

  • 取りうる解の集合から最もよい解を求める問題。最小の頂点被覆問題や最短パス問題など

  • ただ、実際には最適な解が必要でない場合もある

• 近似アルゴリズム(approximation algorithms)

  • 近似的に最適な解を探すために設計されたもの

• MIN-VERTEX-COVER

  • 入力グラフに対して取りうるすべての頂点被覆から最も小さい頂点被覆の 1 つを求める問題

• MIN-VERTEX-COVER の近似アルゴリズム A

  • 以下のアルゴリズムにより最小頂点被覆のサイズの 2 倍を超えない頂点被覆が得られる

  • 入力 G に対して(ただし G は無向グラフ):

    • G のすべての辺が印をつけた辺に隣り合うまで以下を繰り返す

      • 印のついたどの辺とも隣り合わない G 中の辺を探す

      • その辺に印をつける

    • 印付きの辺の両端であるすべての節点を出力する

10.2: 確率的アルゴリズム

• 確率的アルゴリズム(probabilistic algorithm)

  • ランダムな処理の出力を利用するように設計されたアルゴリズム

• 確率的 Turing 機械(probabilistic Turing machine)

  • 確率的 Turing 機械 M は非決定性 Turing 機械の一種である

  • 各々の非決定性ステップはコイン投げステップ(coin-flip step)と呼ばれ、そのステップの後にコイン投げの結果に応じた 2 種類の正しい動作を持つ

  • 入力 w に対する M の計算の各々の枝 b に確率を割り当てる。枝 b の確率を Pr[b] = 2^-k と定義する

    • ここで k は枝 b でのコイン投げの回数である

  • M が w を受理する確率を以下のように定義する

    • Pr[M は w を受理] = ΣPr[b] (b は受理枝)

• 誤り確率ε

  • 確率的 Turing 機械は小さな確率の誤りを許すことにする

  • 0 <= ε < 1/2 に対し

    • w ∈ A の時 Pr[M は w を受理] >= 1 - ε

    • w ∉ A の時 Pr[M は w を拒否] >= 1 - ε

  • ならば、M は言語 A を誤り確率 ε で認識する(M recognizes language A with error probability ε)と定義する

• BPP(Bounded-error Probabilistic Polynomial time)

  • BPP は確率的多項式時間 Turing 機械によって、誤り確率 1/3 で認識される言語のクラスである

• εを 0 より大きく 1/2 未満の固定された定数とする。誤り確率εの確率的多項式時間 Turing 機械 M1 を用いて、与えられた多項式 poly(n) に対して、誤り確率 2^-poly(n) の等価な確率的多項式時間 Turing 機械 M2 を構成できる

• Fermat の小定理(Fermat's little theorem)

  • p が素数かつ a ∈ Zp+ ならば、a^p-1 ≡ 1 (mod p) である

    • ここで Zp+ = {1, ..., p-1}

• PRIMES

  • PRIMES = {n | n は二進表現の素数}

  • PRIMES ∈ BPP

• クラス RP

  • RP は、ある言語に属している入力を少なくとも確率 1/2 で受理し、その言語に属していない入力を確率 1 で拒否する確率的多項式時間 Turing 機械によって認識される言語のクラスである

• 分岐プログラム(branching program)

  • 分岐プログラムは、すべての節点が変数でラベル付けされた有向非巡回グラフである

  • ただし 2 つの出力節点(output node)は例外であり、0 と 1 でラベル付けされる。変数でラベル付けされた節点は問い合わせ節点(query nodes)と呼ばれる

  • すべての問い合わせ節点は 2 つの出ていく辺を持ち、一つは 0、もう一つは 1 とラベルが付いている。2 つの出力節点はいずれも出ていく辺を持たない

  • 分岐プログラムの 1 つの節点を開始節点とする

• 一回読み出し分岐プログラム(read-once branching program)

  • 開始節点から出力節点へ至るどの有向パス上においても、各変数を最大 1 回しか質問しない分岐プログラム

• EQ ROBP

  • EQ ROBP = {<B1, B2> | B1 と B2 は等価な一回読み出し分岐プログラム}

  • EQ ROBP は BPP に属する

10.3: 交替性

• 交替アルゴリズム

  • 非決定性の計算は、起動されたプロセスのうちどれか 1 つが受理するならば受理となる

  • 交替計算が複数のプロセスに別れる場合、受理の方法を次の 2 つのうちのいずれかに指定できる

    • いずれかの子プロセスが受理するならば現在のプロセスも受理する

    • または、すべての子プロセスが受理するならば現在のプロセスも受理する

• 交替性 Turing 機械(altering Turing machine)

  • 交替性 Turing 機械はある特性が加えられた非決定性 Turing 機械である

  • その状態とは q accept と q reject を除いて、全称状態(universal state)と存在状態(existential state)にわかれる

  • 与えられた入力に対する交替性 Turing 機械の計算は、非決定性計算木として表すことができ、計算結果もその計算木の上で定義できる

  • 計算木の各節点には、対応する計算状況での状態に応じて、全称状態ならば ∧ のラベルを、存在状態ならば ∨ のラベルを付ける

  • 各節点の値を次のように求める

    • もし、その節点が終了状況ならば節点の値はその状況に応じて受理か拒否になる

    • そうでない時には、節点のラベルが ∧ であってこの節点がすべて受理である時、あるいはその節点のラベルが ∨ であって子の節点のいずれかが受理である時、節点の値を受理とし、その他の場合には拒否とする

  • こうして各節点の値を定めた時の根にあたる節点の値が交替性 Turing 機械の計算結果である

• 複雑さのクラス

  • ATIME(t(n)) = {L | L は Ｏ(t(n)) 時間交替性 Turing 機械によって判定される}

  • ASPACE(f(n)) = {L | L は Ｏ(f(n)) 領域交替性 Turing 機械によって判定される}

• AP: 交替性多項式時間 Turing 機械で決定される言語のクラス

• APSPACE: 交替性多項式領域 Turing 機械で決定される言語のクラス

• AL: 交替性対数領域 Turing 機械で決定される言語のクラス

• 複雑さの関係

  • f(n) >= n に対して、ATIME(f(n)) ⊆ SPACE(f(n)) ⊆ ATIME(f^2(n))

  • f(n) >= log n に対して、ASPACE(f(n)) = TIME(2^Ｏ(f(n)))

  • したがって、AL = P、AP = PSPACE、APSPACE = EXPTIME が成り立つ

10.4: 対話証明系

• 確率的多項式時間アルゴリズムがクラス P の確率版と考えられるのと同様に、対話証明はクラス NP の確率版とみなすことができる

• 同型(ismorphic)

  • グラフ G と H は、G の節点を並べ替えて G と H が一致するならば同型であるという

  • ISO = {<G, H> | G と H は同型グラフ}

  • ISO は明らかに NP であるが、この問題に対する多項式時間アルゴリズムは発見されておらず、またこの問題が NP 完全であることも証明されていない

• 非同型

  • ISO の補言語

  • NONISO = {<G, H> | G と H は同型グラフでない}

• 対話証明系のモデル

  • 検証者(verifier)

    • それまでに交換されたメッセージの履歴から、証明者へ次に送付するメッセージを計算する関数 V とみなす

    • 関数 V は以下の 3 つを入力とする

      • 入力文字列

      • ランダム入力

      • メッセージ履歴の一部

        • これまでに交換されたメッセージ m1 から mi を表すため、m1#m2#...#mi を用いる

    • 検証者の出力は、一連のメッセージに続く次のメッセージ mi+1 か、もしくは対話の結論である受理または拒否のいずれかである

  • 証明者(prover)

    • 量に関して制限のない計算能力を持つ存在

    • 以下の 2 つの入力をとる関数 P であると定義する

      • 入力文字列

      • メッセージ履歴の一部

    • 証明者の出力は、次に検証者へ送るメッセージ

  • 証明者と検証者の対話

    • 特定の文字列 w および r に対して、ある k に対してメッセージの列 m1 から mk が存在し、以下が成り立つならば (V ↔ P)(w, r) = 受理 と書く

      • 0 <= i < k かつ偶数の i に対して、V(w, r, m1#...#mi) = mi+1

      • 0 < i < k かつ奇数の i に対して、P(w, m1#...#mi) = mi+1

      • メッセージ履歴中の最後のメッセージ mk が受理

• クラス IP

  • 以下を満たす多項式時間関数 V および時間的に制約のない関数 P が存在するならば、言語 A は IP に属するという

  • すべての関数 P~ および文字列 w に対して、

    • w ∈ A ならば Pr[V ↔ P は w を受理] >= 2/3

    • w ∉ A ならば Pr[V ↔ P~ は w を受理] <= 1/3

  • IP = PSPACE

10.5: 並列計算

• 並列計算機(parallel computer)

  • 複数の演算を同時に実行できる計算機

• 逐次計算機(sequential computer)

  • 1 度に 1 つの演算しか実行できない計算機

• 並列ランダム・アクセス機械(Parallel Random Access Machine)

  • 並列アルゴリズムの理論において最も広く受け入れられているモデルの 1 つで、PRAM と呼ばれるモデル

  • PRAM モデルでは、パターン化された単純な命令セットを持つ理想化された複数のプロセッサを考え、それらのプロセッサが計算機上で共有メモリを介して交信する

• 一様(uniform)

  • 回路族(C1, C2, ...)に対して、入力 1^n から <Cn> を出力するような対数領域の変換装置 T が存在する時、この回路族は一様であるという

• サイズ・深さ同時(simultaneous size-depth)

  • ここでは特定の並列時間計算量を達成するのにいくつのプロセッサが必要になるかを議論する目的で、あるいはその逆を調べる目的で、1 つの回路族のサイズと深さを同時に考慮する

  • ある言語に対してサイズ計算量 f(n) で深さ計算量 g(n) の一様な回路族が存在するならば、その言語は高々 (f(n), g(n)) のサイズ・深さ同時回路計算量を持つと定義する

• クラス NC

  • i >= 1 に対して (NC^i) を多項式サイズで深さ Ｏ(log^i n) の回路の一様な族によって決定される言語のクラスとする

  • ある i に対して NC^i に属するすべての言語のクラスを NC とする

  • このような回路族によって計算される関数を NC^i 計算可能(NC^i computable)、もしくは NC 計算可能(NC computable)という

• 複雑さの関係

  • NC^1 ⊆ L

  • NL ⊆ NC^2

  • NC ⊆ P

• P 完全(P-complete)

  • 次の条件を満たす言語 B を P 完全という

    • B ∈ P

    • P に属するすべての A が対数領域で B に帰着する

10.6: 暗号

• ある暗号がすぐに破られないことを保証するには、最低でも鍵がすぐには見つからないということの数学的な証明が必要

  • しかしそのような証明は難しい

  • 代わりに我々は状況証拠に頼っている。昔は熟練者を雇って破らせてみることで暗号についての品質についての証拠を得ていた。しかし、このアプローチには明らかに欠陥がある

• 複雑さの理論は、暗号の安全性についての証拠を得る別の方法を提供する

  • NP 完全問題を暗号破りの問題に帰着させることは、暗号破りの問題それ自体が NP 完全問題であることを示すことになる

    • しかし、これは安全性についての十分な証拠を与えるものではない。理由は NP 完全性が最悪ケースでの複雑さを扱っているため。ある問題が NP 完全であっても、ほとんどの場合で簡単に解けてしまっては意味がない

  • 暗号の場合は、最悪ケースでの複雑さよりも平均ケースでの複雑さを評価する必要がある

    • 平均ケースについて扱いにくいと思われている問題は、整数の素因数分解問題。数世紀にわたってトップの数学者達の興味の対象であるが、いまだに高速な手法は発見されていない

    • 現代的な暗号は素因数分解問題に関連しており、その暗号を破ることはある数を素因数分解することに相当するように作られている

• 一方向性置換(one-way permutation)

  • 一方向性置換は以下の 2 つの性質を持つ長さ不変の置換 f である

    • 多項式時間で計算可能である

    • すべての確率的多項式時間 TM M、すべての k および十分大きな n に対して、長さ n のランダムな w を選び、入力 w に対して M を動作させた場合に PrM,w[M(f(w)) = w] <= n^-k となる。ここで PrM,w は、確率が M によるランダムな選択および w のランダムな選択の上でとられることを意味する

• 一方向性関数(one-way function)

  • 一方向性関数は以下の 2 つの性質を持つ長さ不変の関数 f である

    • 多項式時間で計算可能である

    • すべての確率的多項式時間 TM M、すべての k および十分大きな n に対して、長さ n のランダムな w を選び、入力 w に対して M を動作させた場合に Pr[M(f(w)) = y, ただし f(y) = f(w)] <= n^-k となる

• 一方向性置換では、どのような確率的多項式時間アルゴリズムも、小さな確率でしか f の逆関数を計算できない

  • つまり f(w) から w を計算することはできない

• 一方向性関数では、どのような確率的多項式時間アルゴリズムも f(w) に写像されるような y を見つけることはできない

• 落し戸関数(trapdoor function)

  • 落し戸関数では、特別な情報が入手できると、効率的に逆方向の演算が可能になる

  • 落し戸関数 f: Σ* → Σ* は長さ不変のインデックス関数であり、補助として確率的多項式時間 TM G および関数 h: Σ*×Σ* → Σ* を持つ。3 つ組 f, G, h は以下の 3 つの条件を満たす

    • 1: 関数 f および h は多項式時間で計算可能である

    • 2: すべての確率的多項式時間 TM E、すべての k、および十分大きな n に対して 1^n に対する G のランダムな出力 <i, t> およびランダムな w ∈ Σ^n を取る時 Pr[E(i, fi(w)) = y, ただし fi(y) = fi(w)] <= n^-k が成り立つ

    • 3: すべての n、長さ n のすべての w、ある入力に対して非ゼロの確率で生じる G のすべての出力 <i, t> に対して h(t, fi(w)) = y, ただし fi(y) = fi(w) が成り立つ

  • 確率的 TM G は、インデックスの族での関数のインデックス i を生成し、同時に fi の素早い逆演算を可能とする値 t を生成する。条件 2 は t なしには fi の逆演算が困難であることを述べており、条件 3 は t が既知の場合には fi の逆演算が容易であることを述べている。関数 h は逆演算可能である