計算理論の基礎

概要
本
​計算理論の基礎 [原著第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 の定理