計算理論の基礎原著第2版

ブックオフで定価の半額以下で変えたのラッキーすぎる（絶版でamazonだとめちゃくちゃ高騰してた（改版発表前））

0 序論

集合（set）

「もの」の集まり
- どのような種類が含まれていても良い
- 集合も含められる
元（element）・要素（member）
- 集合に属する「もの」
重複した要素は保持できない
部分集合（subset）
- ある集合のすべての要素が別の集合の要素であること
  - $A\subseteq B$である場合、AはBの部分集合であると言える
- 真部分集合（proper subset）
  - $A\subset B$の場合
重複集合（multiset）
- 重複を許す集合
無限集合（infinite set）
- 要素が無限にある集合
集合演算
- 空集合（empty set）
  - 要素が1つもない集合
  - $\emptyset$ で表す
- 和集合（union）
  - 2つの集合の要素をすべてまとめた集合
  - $A\cup B$
- 積集合（intersection）
  - 2つの集合の内、共通する要素のみを含んだ集合
  - $A\cap B$
- 補集合（complement）
  - ある集合に含まれていない要素の集合
  - $\neg A$
- 直積（cross product）・Cartesian積（Cartesian product）
  - 2つの集合のすべての要素を組み合わせた組を持つ集合 $A \times B = {(a,b) \mid a \in A, b \in B} = {(A_1,B_1),(A_1,B_2),(A_2,B_1),(A_2,B_2)}$
べき集合（power set）
- ある集合のすべての部分集合を含む集合

列と組

列（sequence）

「もの」をある順序で並べたもの
- 順序が意味を持つ
要素の数に上限はないため、無限である

組（tuple）

有限の列
対（pair）
- 2個のタプル

関数と関係

関数（function）

$f(a) = b$

入力と出力の関係付け
同じ入力には必ず同じ出力を生成する
写像（mapping）
- 関数の別名
- 上記関数はf はa をb へ写すという
定義域（domain）
- 関数の入力になり得るものの集合
- 複数の集合に対して作用する場合、それらの直積となる
値域（range）
- 関数の出力の集合
関数は形式的に以下の様に表せる $f:D\rightarrow R$
- $D$ は定義域
- $R$ は値域
値域の上への（onto）関数
- 値域のすべての要素が出力となる関数
引数（argument）
- 関数に渡される要素
項数（arity）
- 引数の個数
- 直積となる集合の個数とも言える
関係（relation）
- 定義域が複数の集合の直積となっている特性を指す

同値関係（equivalence relation）

関係$R$ において、等しいかどうかという概念
同値である条件
- $R$ が反射律（reflexive）を満たす
  - すべての$x$ について$xRx$ （例: $x=x$）
- $R$ が対象律（symmetric）を満たす
  - すべての$x$ と$y$ について$xRy$ ならば$yRx$ （例: $x=y$ ならば$y=x$ ）
- $R$ が推移律（transitive）を満たす
  - すべての$x$, $y$, $z$ について、$xRy$ かつ$yRz$ ならば$xRz$ （例: $x=y$ かつ$y=z$ ならば$x=z$ ）

グラフ

グラフ（graph）・無向グラフ（undirected graph）

点とそれらを結ぶ線の集合
節点（node）・頂点（vertex）
- 点
辺（edge）
- 線
- 向きは無い
次数（degree）
- ある節点につながっている辺の個数
- 節点$A$ と節点$B$ の間に辺がある場合、どちらの次数も+1される
ラベル付けされたグラフ（labeled graph）
- 節点や辺に名前や記号を与えたグラフ
部分グラフ（subgraph）
- あるグラフの部分集合であるグラフ
パス（path）
- 辺によって結ばれている節点の列
- 単純パス（simple path）
  - パス中のどの節点も重複していない状態
連結（connected）
- すべての節点にパスが存在する状態
巡回（cycle）
- パスの始まりと終わりが同じ節点である状態
- 単純巡回（simple cycle）
  - 巡回の内、最低3つの節点があり、かつ両端の節点のみが重複している状態
木（tree）
- 連結かつ巡回を持たないグラフ
- 根（root）
  - 特定の節点
- 葉（leaf）
  - 木の節点の内、次数が1の節点

有向グラフ（directed graph）

辺に向きがあるグラフ
出次数（out-degree）
- 節点から出ていく向きの辺の個数
入次数（in-degree）
- 節点へ入っていく向きの辺の個数
有向パス（directed path）
- 方向を考慮したパス
強連結（strongly connected）
- 有向パス上に有向グラフのすべての節点がつながっている状態

Boole論理（Boolean logic）

Boole値（Boolean value）である$\text{TRUE}$ と$\text{FALSE}$ の2値で表現される数学の系
論理演算
- 演算子（operand）
  - 論理演算の命題
- 否定（negation）
  - 反対の値になる$\text{not}$ 演算である
  - $\neg$ で表される
  - $\neg\text{TRUE}=\text{FALSE}$
  - $\neg\text{FALSE}=\text{True}$
- 論理積（conjunction）
  - 両方の値が真である場合に真となる$\text{and}$ 演算である
  - $\wedge$ で表される
  - $\text{TRUE}\wedge\text{TRUE}=\text{TRUE}, \text{else FALSE}$
- 論理和（disjunction）
  - 片方の値が真である場合に真となる$\text{or}$ 演算である
  - $\vee$ で表される
  - $\text{TRUE}\wedge\text{TRUE}=\text{TRUE}$
  - $\text{TRUE}\vee\text{FALSE}=\text{TRUE}$
  - $\text{FALSE}\vee\text{TRUE}=\text{TRUE}, \text{else FALSE}$
- 排他的論理和（exclusive or）
  - 演算子の内、どちらか一方のみが真である場合に真となる$\text{xor}$ 演算である
  - $\oplus$ で表される
  - $\text{TRUE}\oplus\text{FALSE}=\text{TRUE}$
  - $\text{FALSE}\oplus\text{TRUE}=\text{TRUE}, \text{else FALSE}$
- 等価（equality）
  - 演算子がどちらも真である場合に真となる$=$ 演算である
  - $\leftrightarrow$ で表される
  - $\text{TRUE}\leftrightarrow\text{TRUE}=\text{TRUE}$
  - $\text{TRUE}\leftrightarrow\text{TRUE}=\text{TRUE}, \text{else FALSE}$
- 含意（implication）
  - 命題$P$ が真である場合に$Q$ 、それ以外は真となる$\text{if }P\text{ then }Q\text{ else TRUE}$ 演算である
  - $\rightarrow$ で表される
  - $\text{TRUE}\rightarrow\text{TRUE}=\text{TRUE}$
  - $\text{TRUE}\rightarrow\text{FALSE}=\text{FALSE}, \text{else TRUE}$
限定子・量化子（quantifier）
- 全称限定子（universal quantifier）
  - $\forall$ で表される
  - すべての要素において検証する
    - $\forall x$ はすべての$x$ において〜と読めば良い
- 存在限定子（existential quantifier）
  - $\exists$ で表される
  - ある要素が存在しそれ選択する
    - $\exists x$ はある要素$x$ を選択して〜と読めば良い

定義、証明、定理

定義（definition）

概念を規定したもの

証明（proof）

命題が真であることを示す論理的な議論
いかなる疑いも超えた証明が要求される

定理（theorem）

真と証明された命題
補題（lemma）
- ある命題の証明のために証明された命題
系（corollary）
- 証明することによって、他の関連した命題も証明できるような命題

証明のタイプ

構造的証明（proof by construction）
- 特定のものが存在することを証明するための方法
- その命題の主張しているものの構成法を見せる
背理法
- 命題が偽であると仮定し、その仮定から明らかな矛盾を導くことによって、命題を真であると証明する
帰納法
- 基底部（basis）と帰納部（induction step）に分け、基底部を真と示し、その基底部から帰納部が真であると導くことによって、それ以降の要素に対する証明を再帰的に行う

1 正規言語

計算モデル（computational model）
- 抽象的な計算機
  - 現実に存在しないかもしれない仮想的なやつ

有限オートマトン（finite automaton）・有限状態機械（finite state machine）

メモリ容量が著しく制限された計算機に対する良いモデル
状態（state）とその状態遷移図（state diagram）に対して、受け付けた入力を元に次の取るべき状態を計算する
Markov連鎖（Markov chain）
- 有限オートマトンと確率を組み合わせたモデル
- パターン認識などで有益
オートマトンの抽象的モデル
- 開始状態（start state）
  - オートマトンの初期状態
- 受理状態（accept state）
  - ある入力が受け入れられることを示す状態
- 遷移（transition）
  - 状態から状態への矢印
有限オートマトンの定義
- 有限オートマトン（finite automaton）は5個の組$(Q, \Sigma, \delta, q_0, F)$である
  - $Q$ は状態（state）と呼ばれる有限集合
  - $\Sigma$ はアルファベット（alphabet）と呼ばれる有限集合
  - $\delta : Q\times\Sigma\rightarrow Q$ は遷移関数（transition function）
  - $q_0\in Q$ は開始状態（start state）
  - $F\subseteq Q$ は受理状態の集合（set of accept state）
定義から、状態関数が状態と入力文字からただ一つの次の状態を示すことがわかる
$A$ を、機械$M$ が受理するすべての文字列の集合とするならば、$A$ は機械Mの言語（language og machine M）であると言う
- $L(M)=A$ と書ける
- または$M$ は$A$ を認識する（M recognizes A）とも言う
  - またはチューリング認識可能という

計算の正式な定義

$M = (Q, \Sigma, \delta, q_0, F)$ を有限オートマトンとし、$w = w_1w_2…w_n$ は文字列で、各$w_i$ はアルファベット$\Sigma$ の要素とする。以下の3条件を満たす状態の列$r_0,r_1,…,r_n\in Q$ が存在するならば、$M$ は$w$ を受理する（accept）という。
1. $r_0=q_0$
  1. 機械が開始状態から始動するということ
2. $i=0,…,n-1$ のとき、$\delta(r_i,w_{i+1})=r_{i+1}$
  1. 遷移関数によって必ずある状態から別の状態へ遷移するということ
3. $r_n\in F$
  1. 機械が受理状態で終わるということ
ある有限オートマトンで認識される言語を正規言語（regular language）という

正規演算（regular operation）

計算理論において、基本的な「もの」は言語であり、道具は言語を操作するために特別に設計された演算である
正規演算の定義
- 和集合演算
  - $A\cup B=x|x\in A\text{ または }x\in B$
    - $A$ と$B$ にあるすべての文字列を一緒にしたものを新しい言語の文字列とする、というもの
- 連結演算
  - $A\circ B=xy|x\in A\text{ かつ }y\in B$
    - $B$ の文字列の前に$A$ の文字列を連結するという操作をすべての組み合わせに対して行い、その結果得られる文字列を新しい言語の文字列とする、というもの
- スター演算
  - $A^*=x_1x_2…x_k|k\geq 0\text{ であり、かつ、各々の }x_i\text{ に対して }x_i\in A$
    - $A$ の文字列を任意個連結して、新しい言語の文字列とする、というもの
      - 正規表現の$*$ と同じで、0個以上の要素が対象となる

非決定性

決定性（deterministic）
- 次の状態が一意に定まっている状態
決定性有限オートマトン（DFA）
- 決定的な動作を行うオートマトン
非決定性（nondeterministic）
- 次の状態として複数の選択肢が存在する
- 決定性の一般化でもある

非決定性有限オートマトン（NFA）

遷移
- 文字を読み出した後、遷移先が複数存在する場合、機械はそれ自体のコピーを複数作成し、その後に取りうる選択肢すべてを並列にたどる
- もしそれ以上遷移できない場合はそのコピーのルートを消す
- 入力が終了した時点で、機械のコピーの内どれか一つでも受理状態にあれば、NFAは入力文字列を受理する
$\varepsilon$ ラベル付された遷移は、文字を読まずにコピーを作成し、一つはその状態にとどまり、残りは$\varepsilon$ ラベルに従って次の状態に進む
いくつかのプロセスが同時に動作できるような並列計算の一種とみなす事ができる
- 非決定性は一つのプロセスを、独立に動作するいくつかの子プロセスに分岐させることに対応する
すべてのNFAは等価なDFAに変換できる
非決定性有限オートマトンの定義
- $P$ は$Q$ のべき集合である
- $\Sigma_\varepsilon$ は$\Sigma\cup{\varepsilon}$ を指す
- 非決定性有限オートマトン（nondeterministic finite automaton）は5個の組$(Q, \Sigma, \delta, q_0, F)$である
  - $Q$ は状態（state）と呼ばれる有限集合
  - $\Sigma$ はアルファベット（alphabet）と呼ばれる有限集合
  - $\delta : Q\times\Sigma_\varepsilon\rightarrow P(Q)$ は遷移関数（transition function）
  - $q_0\in Q$ は開始状態（start state）
  - $F\subseteq Q$ は受理状態の集合（set of accept state）
非決定性オートマトンの計算の正式な定義
- $M=(Q,\Sigma,\delta,q_0,F)$ をNFAとし、$w$ を$\Sigma$ 上の文字列とする。各$y_i$ は$\Sigma_\varepsilon$ の要素であって、$y_i$ を用いて$w$ が$w=y_1y_2…y_m$ と表され、次の三条件を満たす$Q$ の要素である状態の列$r_0,r_1,…,r_m$ が存在するならば、$N$ は$w$ を受理する（accept）という。 1. $r_0=q_0$ 1. 機械が開始状態から始動するということ 2. $i=0,…,m-1$ のとき、$r_{i+1}\in\delta(r_i,y_{i+1})$ 1. $N$ が状態$r_i$ で$y_{i+1}$ を読み出したとき、状態$y_{i+1}$ は次に取り得る状態の集合を与えるので、$r_{i+1}$ はその集合の要素であるということ 3. $r_n\in F$ 1. 機械が受理状態で終わるということ
NFAとDFAは等価（equivalent）である
- 同じ言語クラスを認識するということ
- 等価である場合、NFAのほうが簡潔に記述できることが多い
- NFAが持つ（非決定性の遷移を含む）すべての遷移が取りうる状態の組（$Q$ のべき集合）をDFAの各状態とし、それに対してNFAの遷移をマッピングすれば良い
ある非決定性有限オートマトンが言語を認識するとき、かつそのときに限り、その言語は正規である

正規演算の閉包性

ある演算に対して閉じている（closed）とは、その集まりの要素への演算の結果が、またその集まりに含まれる「もの」となること
- 正規言語のクラスは、和集合演算に対して閉じている
  - $A_1$ と$A_2$ が正規言語であれば、$A_1\cup A_2$ も正規言語である
- 正規言語のクラスは、連結演算に対して閉じている
  - 正規言語$A_1$ と$A_2$ に対応するNFAを$N_1$ と$N_2$ とする
  - 開始状態を$N_1$ の開始状態、受理状態を$N_2$ の受理状態とし、$N_1$ の受理状態から$N_2$ の開始状態へ$\varepsilon$ 遷移を行うようなNFAである$N$ を作成する
  - このような$N$ は$A_1$ が受理された後に$A_2$ の受理を試みる連結演算を行うことができる
    - $A_1$ を受理するタイミングを非決定的に推測するとみなせる
- 正規言語のクラスは、スター演算に対して閉じている
  - 正規言語$A_1$ に対応するNFAを$N_1$ とする
  - 開始状態を受理状態、受理状態を$N_1$ の受理状態とし、開始状態から$N_1$ の開始状態へ、受理状態から$N_1$ の開始状態へ$\varepsilon$ 遷移を行うようなNFAである$N$ を作成する
  - このような$N$ は$A_1$ が無い、もしくは受理状態を繰り返すようなスター演算を行うことができる

正規表現（regular expression）

言語を記述する表現を作成するための正規演算
演算の優先度
- スター演算>連結>和集合

正規表現の正式な定義

$R$ が
1. アルファベット$\Sigma$ に属する
  - 正規表現$a$ が言語${a}$ を表す
2. $\varepsilon$
  - 正規表現$\varepsilon$ が言語${\varepsilon}$ を表す
3. $\emptyset$
  - 正規表現$\emptyset$ が空言語を表す
4. $R_1$ と$R_2$ を正規表現として$(R_1\cup R_2)$
  - 言語$R_1$ と$R_2$ の和集合によって得られる言語を表す
5. $R_1$ と$R_2$ を正規表現として$(R_1\circ R_2)$
  - 言語$R_1$ と$R_2$ の連結によって得られる言語を表す
6. $R_1$ を正規表現として$(R_1^*)$
  1. 言語$R_1$ のスター演算によって得られる言語を表す
のいずれかであるならば、$R$ は正規表現（regular expression）であるという
正規表現$R$ の表現する言語を$L(R)$ と書く
$\varepsilon$ は0文字の文字列"" 、$\emptyset$ は文字列が無いnull と理解する
- $\Sigma={1}$ とした場合、
  - $1\circ\varepsilon$ は$1$ を
  - $1\circ\emptyset$ は$\emptyset$ を表す
    - 任意の集合に空集合を連結することにより空集合が得られる

有限オートマトンとの等価性

正規表現と有限オートマトンは記述能力において等価である
DFAから正規表現を作成するには、以下のステップを行う
1. 開始状態に$q_{\text{start}}$ を追加し、元の開始状態へ$\varepsilon$ 矢印を追加する
2. 受理状態に$q_{\text{accept}}$ を追加し、元の受理状態から$q_{\text{accept}}$ への$\varepsilon$ 矢印を追加する
3. $q_{\text{start}}$ と$q_{\text{accept}}$ 間の状態を1つ選択する
4. 選択した状態$q_{\text{rip}}$ と他の状態との遷移を正規表現に置換する
  - $q_{\text{rip}}$ に対して遷移する状態を$q_i$
  - $q_{\text{rip}}$ から遷移する状態を$q_j$ とする
  - $\delta(q_i,q_j)=(R_1)(R_2)^*(R_3)\cup(R_4)$ として示せる
    - $R_1=\delta(q_i,q_{\text{rip}})$
    - $R_2=\delta(q_{\text{rip}},q_{\text{rip}})$
    - $R_3=\delta(q_{\text{rip}},q_j)$
    - $R_4=\delta(q_i,q_j)$
5. 状態が$q_{\text{start}}$ と$q_{\text{accept}}$ の2つになるまで繰り返す

非正規言語

ポンピング補題（pumping lemma）

すべての正規言語がある特別な性質を満たしていることを示す
- 満たしていなければ正規言語ではない！
定理
- $A$ が正規言語であるならば、ある数$p$（ポンピング長）が存在し、$s$ が少なくとも長さ$p$ である$A$ の任意の文字列であるときに、$s$ は条件 1. 各$i\geq 0$ について$xy^iz\in A$ 2. $|y|>0$ 3. $|xy|\leq p$
- を満足する3つの断片、$s=xyz$ に分割できる
  - 記法$|s|$ は文字列$s$ の長さ、$y^i$ は$y$ を$i$ 個連結したものを表す（$y^0$ は$\varepsilon$ とみなす）

2 文脈自由文法

文脈自由文法（context-free grammar）

再帰的な構造を記述できる言語記述手法
$$ A -> 0A1 \ A -> B \ B -> # $$
文法は上記のような生成規則（production）とも呼ばれる書き換え規則（substitution rule）からなる
各書き換え規則は矢印によって分離された文字と文字列からなる
- 文字は変数（variable）と呼ばれる
  - 多くの場合大文字
- 文字列は変数と終端記号（terminal）と呼ばれる別の文字からなる
  - 多くの場合小文字や数、記号など
開始変数（start variable）
- エントリーポイントとなる変数
導出（derivation）
- 文字列を得るために列を書き換えること
構文解析木（parse tree）
- 文字列を生成した規則を図式的に表現したもの
文脈自由言語（context-free language）（CFL）
- 文脈自由文法により生成できる言語

文脈自由文法の定義

文脈自由文法（context-free grammar）は、4個組$(V, \Sigma, R, S)$ である
1. $V$ は変数（variable）と呼ばれる有限集合
2. $\Sigma$ は終端記号（terminal）と呼ばれる、$V$ と共通部分を持たない有限集合
3. $R$ は、変数（左辺）および変数と終端記号からなる文字列（右辺）で構成される規則（rule）の有限集合
4. $S\in V$ は開始変数
$u$, $v$, $w$ が変数や終端記号からなる文字列で、$A\rightarrow w$ が文法規則であるならば、$uAv$ は$uwv$ を生成する（yield）といい、$uAv\Rightarrow^* uwv$ と書く
$u=v$ であるか、$k\geq 0$ に対して、列$u_1,u_2,…,u_k$ が存在し、$u\Rightarrow u_1\Rightarrow u_2\Rightarrow …\Rightarrow u_k\Rightarrow v$ であるならば、$u$ は$v$ を導出（derive）するといい、$u\Rightarrow v$ と書く
集合${w\in\Sigma^|S\Rightarrow^ w}$ をその文法の言語（language of the grammar）という
- 開始変数から導出できる文字列の内、終端記号に属するもの、つまりそれ以上生成が不可能であるもの

文脈自由文法の設計

DFAからCFGを構成する
1. DFAの各々の状態$q_i$ に対する変数$R_i$ を作る
2. $\delta(q_i,a)=q_j$ がDFAにおける遷移であるならば、規則$R_i\rightarrow aR_j$ をCFGに加える
3. $q_i$ がDFAにおける受理状態であるならば、規則$R_i\rightarrow\varepsilon$ を加える
4. $q_0$ が機械の開始状態であるような$R_0$ を文法の開始変数とする

曖昧（ambiguous）

解釈が複数あるような文字列を生成する文法
- 2つの異なる構文解析木を持つ
最左導出（leftmost derivation）
- すべてのステップで最も左に残っている変数が置き換えられる場合
  - $S\rightarrow AB \mid AC$ のような文法は
    - $S\rightarrow AB$
    - $S\rightarrow AC$
  - と解釈できるため、複数の最左導出が存在することになる
定義
- 文字列$w$ が2つ以上の異なる最左導出を持つならば、その文字列は文脈自由文法$G$ において曖昧に（ambiguously）導出される
- 文法$G$ がある文字列を曖昧に生成するならば、$G$ は曖昧（ambiguous）である

CHOMSKY標準形（Chomsky normal form）

すべての規則が
- $A\rightarrow BC$
- $A\rightarrow a$
という形である文脈自由文法
- $a$ は任意の終端記号、$A$ は任意の変数、$B$ と$C$ は開始変数ではない任意の変数
- ただし、開始変数$S$ に対しては規則$S \rightarrow \varepsilon$ を加えても良い
任意の文脈自由文法はChomsly標準形の文脈自由文法により生成される
任意の文法$G$ からChomsky標準形への変換
1. 新しい開始変数を加える
  - 開始変数が右辺に来ないようにする
2. $A\rightarrow\varepsilon$ の形式である$\varepsilon$ 規則（$\varepsilon$ rule）を消去する
  - 消した後、規則の右辺に$A$ が出現するたび、$A$ を削除した新しい規則を加える
    - $R\rightarrow uAv$ においては、$R\rightarrow uv$ を加える
    - $R\rightarrow uAvAw$ においては、$R\rightarrow uvAw$, $R\rightarrow uAvw$, $R\rightarrow uvw$ を加える
    - $R\rightarrow A$ においては、以前に$R\rightarrow\varepsilon$ を除去してない限り$R\rightarrow\varepsilon$ を加える
3. $A\rightarrow B$ の形式である単位規則（unit rule）を消去する
  - 規則$B\rightarrow u$ が現れた際に$A\rightarrow u$ を加える
    - $A\rightarrow u$ を以前に除去していた場合は加えない
4. 残りの規則を適切な形式に変換する
  - $A\rightarrow u_1u_2$ の場合
    - 終端記号$u_i$ を新しい変数$U_i$ で置き換え、規則$U_i\rightarrow u_i$ を加える
  - $A\rightarrow u_1u_2u_3…u_k$ の場合
    - $A\rightarrow u_1A_1, A_1\rightarrow u_2A_2, …, A_{k-2}\rightarrow u_{k-1}u_k$ で置き換える
      - $A_i$ は新しい変数

プッシュダウン・オートマトン（PDA）

スタック（stack）を持つ非決定性オートマトン
- 有限ではない！
正規言語以外の言語を認識できる
文脈自由文法と能力が等価である
- 言語が文脈自由であることは、その言語を生成する文脈自由文法か、それを認識するプッシュダウン・オートマトンのどちらかを提示することによって示すことができる
決定性プッシュダウン・オートマトンと非決定性プッシュダウン・オートマトンは等価ではない！

プッシュダウン・オートマトンの定義

プッシュダウン・オートマトン（pushdown automaton）は6個組$(Q,\Sigma,\Gamma,\delta,q_0,F)$ である。ここで、$Q$, $\Sigma$, $\Gamma$, $F$ すべて有限集合であり以下のものとする
1. $Q$ は状態の集合
2. $\Sigma$ は入力アルファベット
3. $\Gamma$ はスタック・アルファベット
4. $\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\rightarrow P(Q\times\Gamma_\varepsilon)$ は遷移関数
  - オートマトンが与えられた状況のときに何をすべきかを指定する
    - スタックを操作する可能性もある
5. $q_0\in Q$ は開始状態
6. $F\subseteq Q$ は受理状態の集合
受理条件
- 入力$w$ が各々$w_i\in\Sigma_\varepsilon$ となる$w=w_1w_2…w_m$ と表される
- 以下の3条件を満たす状態の列$r_0,r_1,…,r_m\in Q$ とスタックの列$s_0,s_1,…,s_m\in\Gamma^*$ が存在する 1. $r_0=q_0$ かつ$s_0=\varepsilon$ - $M$ が正しく空のスタックで開始状態から指導することを意味する
  - $i=0,…,m-1$ に対し、$(r_{i+1},b)\in\delta(r_i,w_{i+1},a)$ となる。ここで、$a,b\in\Gamma_\varepsilon$ と$t\in\Gamma^*$ に対して、$s_i=at$ と$s_{i+1}=bt$ である
    - $M$ が状態、スタック、次の入力文字に従って正しく動作することを意味する
  - $r_m\in F$
    - 入力の最後で受理状態が生じることを意味する
- 上記の条件を満たすならば、$M$ は$w$ を受理する
読み出し
- $a,b\rightarrow c$ と書いて、機械が入力から$a$ を読み出すとき、スタックから$b$ をポップし、$c$ をプッシュする
  - $a$, $b$, $c$ のうちいずれも$\varepsilon$ であってよい
    - $a$ が$\varepsilon$ の場合、入力を読まずに遷移を行う
    - $b$ が$\varepsilon$ の場合、スタックからポップせずに遷移を行う
    - $c$ が$\varepsilon$ の場合、スタックにプッシュせずに遷移を行う

非文脈自由言語

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

任意の文脈自由言語$A$ に対して、ある数$p$ （ポンピング長）が存在して、$s$ が少なくとも長さ$p$ である$A$ の文字列であるときに、$s$ は条件
1. 任意の$i\geq 0$ に対して、$uv^ixy^i\in A$
2. $|vy|>0$
3. $|vxy|\leq p$
を満足する5個の断片$s=uvxyz$ に分割できる
- $s$ を$uvxyz$ に分割するとき、条件2は$v$ か$y$ のどちらか一方は空列ではないことを示している
- 条件3は断片$v$, $x$, $y$ をひとまとめにしても、長さが高々$p$ であることを示している

3 CHURCH-TURINGの提唱

チューリングマシン（Turing machine）

無限のメモリを持つ
現実の機械が行えるすべての計算を行うことができる
無限の長さを持つテープの上を動き回り、文字を読み書きすることできるヘッドを持つ
受理状態（accept）や拒否状態（reject）に入らなければ、機械は決して止まらず永久に動き続ける
チューリングマシンの概要
- 有限オートマトンとチューリングマシンの違い 1. チューリングマシンはテープに対し書き込みと読み出しのどちらもできる 2. 読み書きヘッドは左右どちらにも動くことができる 3. テープは無限長である 4. チューリングマシンは拒否や受理に対応する特別な状態に入ると、すぐに停止する

チューリングマシンの正式な定義

チューリングマシンは7個組$(Q,\Sigma,\Gamma,\delta,q_0,q_a,q_r)$ である。ここで$Q$, $\Sigma$, $\Gamma$ はすべて有限集合であり
1. $Q$ は状態の集合
2. $\Sigma$ は空白文字（blank symbol）$\sqcup$ を含まない入力アルファベット
  - 空白文字は入力に含まないので、入力の終わりを示す
3. $\Gamma$ は$\sqcup\in\Gamma$ かつ$\Sigma\subseteq\Gamma$ であるようなテープ・アルファベット
  - 入力は終わりを示すために空白文字を持つ
4. $\delta : Q\times\Gamma\rightarrow Q\times\Gamma\times{L,R}$ は遷移関数
  - ${L,R}$ は計算後どちらに動くかを示す
    - ただし、端を越えて移動することはできない（その場に留まる）
5. $q_0\in Q$ は開始状態
6. $q_a\in Q$ は受理状態
7. $q_r\in Q$ は拒否状態
  - ただし、$q_r\neq q_a$ である
計算状況（configuration）
- 状態、テープの内容、ヘッドの位置の3つの項目の設定値
- 状態$q$ とテープ・アルファベット$\Gamma$ 上の文字列$u$ と$v$ に対して、$uqv$ と書く
  - 現在の状態が$q$ 、現在のテープの内容が$uv$ 、現在のヘッドの位置が$v$ の最初の文字であるような計算状況を指す
    - $1011q_701111$ はヘッドの左に$1011$ があり、ヘッドは$0$ を指しており、ヘッドの右には$1111$ がある状況を指す
      - $|1|0|1|1|[q_7]0|1|1|1|1|\sqcup|\sqcup|…$
Turing計算可能（Turing-recognizable）
- 任意の言語に対して、それを認識するチューリングマシンが存在する場合、その言語をTuring計算可能と言う
判定装置（decider）
- すべての入力に対して、停止し、ループしない機械は常に受理か拒否の判定を行う
Turing判定可能（Turing-decidable）
- 任意の言語に対して、それを判定するチューリングマシンが存在する場合、その言語をTuring判定可能と言う
- すべての判定可能な言語はTuring認識可能である

チューリングマシンの種類

チューリングマシンに様々な（妥当な）変形を加えたとしてもチューリングマシンの能力は変わらない
- 定義の変形に対するモデルの不変性を頑健性（robutness）とよぶ
チューリングマシンの頑健性はすごい

アルゴリズム（algorithm）

問題を解くための単純な命令の集まり
Church-Turingの提唱（Church-Turing thesis）
- λ計算とチューリングマシンが計算能力において等価であることを示す
  - アルゴリズム（λ計算）がチューリングマシンにおいて実行し、結果を判定可能である
- アルゴリズムの厳密な定義と関連付けを行う
  - 計算の仕方が分かるものは計算可能であるということ

4 判定可能性

証明は本を読め！
決定性有限オートマトンが与えられた文字列を受理するかどうかは判定可能である
非決定性有限オートマトンが与えられた文字列を受理するかどうかは判定可能である
正規表現が与えられた文字列を生成するかどうかは判定可能である
- DFA, NFA, 正規表現を持つチューリングマシンはすべて等価である
  - チューリングマシンは一つの表現形式を他の表現形式に変換可能である
有限オートマトンに対する空性検査（emptiness testings）、つまり$E_{\text{dfa}}={\langle A\rangle|A\text{はDFAかつ}L(A)=\emptyset}$ は判定可能である
2つの有限オートマトンが同じ言語を認識するかどうかは判定可能である
文脈自由文法が特定の文字列を生成するかどうかは判定可能である
- Chomsky標準形に変換すれば、$w$ の長さ$n$ において、いかなる導出もちょうど$2n-1$ ステップかかるため、そのステップで導出できるかを判定すれば良い
文脈自由文法に対する空性検査も判定可能である
- 各変数に対して終端記号からなる文字列を生成できるか見る
  - 終端記号にマークを付ける
  - マークが付いているやつに置き換えられる規則を走査し、マークを付ける
  - 新しいマークがつかなくなるまで走査を繰り返す
  - 開始変数にマークが付いていたら生成できる、付いてなかったら生成できない
2つの文脈自由文法が同じ言語を生成するかどうかを決定することを判定するのは不可能である！
すべての文脈自由言語はチューリングマシンによって判定可能である
- 文脈自由文法が特定の文字列を生成するかを判定するチューリングマシンによって判定可能

受理問題（acceptance problem）

チューリングマシンが受理もしくは拒否するかどうかを判定する問題
チューリングマシンの受理可能性はチューリングマシンでは判定不可能である
- $A_{\text{tm}}={\langle M,w\rangle|M\text{はTMであり、}M\text{は}w\text{を受理する}}$

対角線論法

対角化（diagonalization）
- 一方の集合の要素がもう一方の集合の要素と対になることができるならば、2つの集合は同じサイズを持つ
- 定義
  - 集合$A$ と$B$ 、および$A$ から$B$ への関数$f$ があると仮定する
  - $f$ が2つの異なる要素を同じ値に決して写像しない、つまり、$a\neq b$ であれば$f(a)\neq f(b)$ であるならば、$f$ は一対一（one-to-one）であるとする
    - 単射ということ
  - また、$f$ が$B$ のすべての要素に当たる、つまり、すべての$b\in B$ に対して$f(a)=b$ となる$a\in A$ が存在するならば、$f$ は上への（onto）関数であるとする
    - 全射ということ
  - 一対一かつ上への関数$f:A\rightarrow B$ が存在するとき、$A$ と$B$ は同じサイズ（same size）であるという
    - 対応（correspondence）とも言う
    - 全単射ということ
  - 対応においては、$A$ のすべての要素は$B$ のすべての要素に一意に写され、$B$ の各々の要素はそれに写像される$A$ の要素をただ一つ持つ
可算（countable）
- 集合$A$ が有限であるか、$\mathbb{N}$ と同じサイズを持つならば、$A$ は可算である
非可算（uncountable）
- 可算できない集合
  - $\mathbb{N}$ より大きい
非可算個の言語があるのに対し、チューリングマシンは可算個しかないため、言語の中には判定可能でないものや認識可能ですら無いものがある
- そのような言語はチューリング認識可能ではない
  - 同じサイズじゃないから

受理問題の判定不可能性

命題
- $A_{\text{tm}}={\langle M,w\rangle|M\text{はTMであり、}M\text{は}w\text{を受理する}}$ をチューリングマシンで判定することは可能か
証明
- $A_{\text{tm}}$ が判定可能であると仮定する
- $H$ を$A_{\text{tm}}$ の判定装置とする
- ここで、チューリングマシン$D$ を以下のように構成する
  - 入力$\langle M\rangle$ に対して 1. 入力$\langle M,\langle M\rangle\rangle$ に対して$H$ を動作させる 2. $H$ が出力するものの逆を出力する、すなわち、$H$ が受理するなら拒否し、$H$ が拒否するなら受理する
- この$D$ はチューリングマシンの記述に対して動作するため、自身の記述に対しても動作する
  - コンパイラがセルフコンパイルできるということ
- $D$ に対して、自身の記述$\langle D\rangle$ を入力として動作させると、$D$ が受理できる場合は$D$ が拒否し、拒否できる場合は受理される
- これは明らかな矛盾であり、従って$D$ と$H$ のどちらも存在できない
定理
- $A_{\text{tm}}$ をチューリングマシンで判定することは不可能である

TURING認識不可能な言語

ある言語とその補集合のどちらもTuring認識可能であるならば、その言語は判定可能である
- 逆説的に、Turing判定不可能である言語は、その言語もしくは補集合はTuring認識可能ではない
補Turing認識可能（co-Turing-recognition）
- 認識可能な言語の補集合
$\neg A_{\text{tm}}$ はTuring認識可能ではない
- $A_{\text{tm}}$ が認識可能かつ判定不可能であるため

5 帰着可能性

帰着（reduction）
- ある問題を解決するするための（より解決しやすい）別の問題に変換すること
- 計算可能性の文脈では…
  - もし$A$ が$B$ に帰着可能で、かつ、$B$ が判定可能なら$A$ もまた判定可能である
  - 逆説的に、$A$ が判定不可能であり$B$ に帰着可能ならば、$B$ もまた判定不可能となる

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

停止問題（halting problem）の判定不可能性

チューリングマシンが与えられた入力で停止するかどうかを判定する問題
命題
- $\text{HALT}_{\text{tm}}={\langle M,w\rangle|M\text{はTMであり、}M\text{は入力}w\text{に対して停止する}}$ が判定可能か
証明
- $\text{HALT}_{\text{tm}}$ が判定可能であると仮定する
- $\text{HALT}_{\text{tm}}$ を判定する$R$ を構成する
- $R$ を用いて$A_{\text{tm}}$ を判定する$S$ を構成する
  - ここで、$S$ は入力$\langle M,w\rangle$ に対して 1. $R$ を動作させる 2. $R$ が拒否（停止しないと判定）した場合、拒否する 3. $R$ が受理（停止すると判定）した場合、入力$w$ に対して$M$ を停止するまでシミュレートする 4. $M$ が受理するなら受理し、$M$ が拒否するなら拒否する
- 上記により、$\text{HALT}{\text{tm}}$ *が判定可能であれば$A{\text{tm}}$* が判定可能だが、実際は$A_{\text{tm}}$ は判定不可能であり、これは明らかな矛盾である
定理
- $\text{HALT}_{\text{tm}}$ は判定不可能である

空性の判定不可能性

チューリングマシンの言語が空であることを判定する問題
命題
- $E_{\text{tm}}={\langle M\rangle|M\text{はTMであり、}L(M)=\emptyset}$ が判定可能か
証明
- $E_{\text{tm}}$ を判定可能と仮定し、それを判定する$R$ を構成する
- 以下のような$M_1$ を構成する
  - 入力$x$ に対して 1. $x\neq w$ なら拒否する 2. $x=w$ なら、入力$w$ に対して$M$ を動作させ、$M$ が受理するならば受理する
- $A_{\text{tm}}$ を判定可能とし、それを判定する以下のような$S$ を構成する
  - 入力$\langle M,w\rangle$ に対して 1. $M$ と$w$ の記述を用いて上述の$M_1$ を構成する 2. $R$ を入力$\langle M_1\rangle$ に対して動作させる 3. $R$ が受理するならば拒否し、$R$ が拒否するならば受理する
- $S$ は$M$ と$w$ の記述から$M_1$ の記述を実際に計算できなければならない
  - 1は$x=w$ かどうかの判定が入った$M$ なので可能
- 仮定より、$R$ は判定可能であるため、受理もしくは拒否を必ず出力する
- $A_{\text{tm}}$ を判定する$S$ は$R$の出力を反転するのみなので判定可能であるが、$A_{\text{tm}}$ の判定装置は存在せず、これは明らかな矛盾であり、仮定は間違っている
定理
- $E_{\text{tm}}$ は判定不可能である

同値性の判定可能性

与えられたチューリングマシンが同値な有限オートマトンを持っているか決定する問題
- そのチューリングマシンが正規言語を認識するかどうかということ
命題
- $\text{REGULAR}_{\text{tm}}={\langle M\rangle|M\text{はTMであり、}L(M)\text{は正規言語}}$ が判定可能か
定理
- $\text{REGULAR}_{\text{tm}}$ は判定不可能である

Riceの定理

チューリングマシンによって認識される言語の任意の性質の検査は不可能である
- 空性や同値性など

2つのチューリングマシンの同値性の判定可能性

2つのチューリングマシンが同値であるかどうか
命題
- $\text{EQ}_{\text{tm}} = {\langle M_1,M_2\rangle|M_1\text{と}M_2\text{はTMであり、}L(M_1)=L(M_2)}$
証明
- $E_{\text{tm}}$ が判定不可能であることを利用する
- $L(M_1)=\emptyset$ とである場合、$L(M_2)$ が空であるかどうかを判定する問題に帰着できる
- これは判定できないので、判定不可能である
定理
- $\text{EQ}_{\text{tm}}$ は判定不可能である

計算履歴を用いた帰着

計算履歴
- その入力を処理するときにチューリングマシンが取る一連の計算状況の記録
- 定義
  - $M$ がチューリングマシンであり、$w$ を入力文字列とする
  - $M$ の$w$ に対する受理計算履歴（accepting computation history）とは、$C_1$ が$M$ の$w$ に対する開始状況であり、$C_l$ が$M$ の受理状況であり、それぞれの$C_i$ は$M$ の規則に従って$C_{i-1}$ から正当に導かれるような一連の計算状況の列$C_1,C_2,…,C_l$ である
  - $M$ の入力$w$ に対する拒否計算履歴（rejecting computation history）とは、$C_l$ が拒否状況であることを除いて同様に定義される
- 計算履歴は有限の列である
  - $M$ が$w$ に対して停止しないなら計算履歴は存在しない
    - その点で、計算完了後にはじめて履歴がわかると考えることができる
  - 履歴はたかだか1個だけ
    - 非決定性チューリングマシンではその限りではない

線形境界付きオートマトン（linear bounded automaton）

テープのヘッドがテープから離れられないように限定されたチューリングマシン
- 量に対して制限があると考える
長さ$n$ の入力に対して、使用可能なメモリ量は$n$ に関して線形となる
LBAが入力を受理するかどうかは判定できる
- 補題
  - 命題
    - $M$ を$q$ 個の状態とテープ・アルファベットとして$g$ 個の文字を持つLBAとする
    - 長さ$n$ のテープに対して、ちょうど$qng^n$ 個の$M$ の異なる計算状況が存在する
  - 証明
    - $M$ の計算状況は、計算途中の$M$ のスナップショットである
    - 計算状況は、制御部の状態、ヘッドの位置、及びテープの内容から構成されている
    - ここで、$M$ は$q$ 個の状態を持っていて、$M$ のテープの長さは$n$ なので、ヘッドは$n$ 個の位置のどれか一つにあり、$g^n$ 通りのテープ文字の列がテープ状に現れる
    - これら3種の値の積が、長さ$n$ のテープを用いた$M$ が取りうる計算状況の総数である
- 命題
  - $A_{\text{lba}}={\langle M,w\rangle|M\text{は文字列}w\text{を受理する}LBA}$ が判定可能か
- 証明
  - $M$ を入力$w$ に対して停止する、もしくは、$qng^n$ ステップ経過するまでシミュレートする
    - 補題より$M$ が取りうる計算状況は$qng^n$ 個であり、それ以上のステップを実行している場合、必ず重複した計算状況が存在する
      - 鳩ノ巣原理
    - ある計算状況から次の遷移は決定的であり、特定の計算状況に戻ってきてしまうような場合は再度実行しても同じパスを通る
      - ループしている
  - $M$ が停止し受理したなら受理し、拒否したなら拒否する
  - 停止しなかったら拒否する
- 定義
  - $A_{\text{lba}}$ は判定可能である
線形境界付きオートマトンで判定不可能であるもの
- 空性検査
- 文脈自由文法がすべての可能な文字列を生成するか
- など

単純な判定不可能問題

Postの対応問題（Post correspondence problem）
- $P={[\frac{t_1}{b_1}],[\frac{t_2}{b_2}],…,[\frac{t_k}{b_k}]}$ において、$t_{i1}t_{i2}…t_{il}=b_{i1}b_{i2}…b_{il}$ が成り立つような$i_1,i_2,…,i_l$ をマッチとしたとき
- $\text{PCP}={\langle P\rangle|P\text{はマッチをもつPost対応問題の入力例}}$
- は判定不可能である

写像帰着可能性（mapping reducibility）

問題Aの入力例を問題Bの入力例に変換できる計算可能な関数が存在する場合、そのような変換を利用して、Bの判定装置を用いてAを判定できる
- $f:A_{\text{input}}\rightarrow B_{\text{input}}$ かつ$B$ が判定可能であれば$A$ も判定可能になる
  - Bが判定不可能であれば、Aも判定可能である
  - Aが判定不可能であれば上記のような関数が存在するBについても判定不可能である
- 認識可能性にも同じ手法が使える

計算可能な関数（computable function）

任意の入力$w$ に対してチューリングマシン$M$ が$f(w)$ をテープ上に設定した場合に停止するような関数$f:\Sigma^\rightarrow\Sigma^$
- 必ず受理か拒否が分かるような関数であり、停止性が証明されている
例
- 整数に対する通常の算術演算

写像帰着可能性の定義

計算可能な関数$f:\Sigma^\rightarrow\Sigma^$ が、任意の$w$ に対して$w\in A\Leftrightarrow f(w)\in B$ を満たす場合、言語Aは言語Bへ写像帰着可能（mapping reducible）であるといい、$A\leq_m B$ と表す
この関数$f$ をAのBへの帰着（reduction）という

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

再帰定理

自己参照可能性

命題
- 自分自身の記述のコピーを出力するチューリングマシン$\text{SELF}$を作れるか
補題
- 命題
  - $w$ を任意の文字列とすると、$q(w)$ が$w$ を出力して停止するチューリングマシン$P_w$ の記述であるような、計算可能な関数$q:\Sigma^\rightarrow\Sigma^$ が存在する
- 証明
  - 入力文字列$w$ に対して 1. 次のようなチューリングマシン$P_w$ を構成する - 任意の入力に対して 1. 入力を消去する 2. テープに$w$ を書き込む 3. 停止する 2. $\langle P_w\rangle$ を出力する
証明
- $A=P_{\langle B\rangle}$
- $B$ を入力に対して 1. $q(\langle M\rangle)$ を計算する 2. その結果と$\langle M\rangle$ を組み合わせてチューリングマシンの完全な記述を作る 3. この記述を印刷して停止する
  - を行うチューリングマシンとする
    - なんかセルフコンパイルするときのステップみたいやな
      - $A$ がコンパイラで$B$ がライブラリ
        違う言語で作ったコンパイラでその言語のライブラリ作る→ライブラリを用いてその言語でコンパイラを再実装→両者を合わせるとセルフコンパイルできるみたいな
定理
- 再帰定理（Recursion Theorem）
  - $T$ を関数$t:\Sigma^\times\Sigma^\rightarrow\Sigma^*$ を計算するチューリングマシンとする
  - このとき、すべての$w$ に対して$r(w)=t(\langle R\rangle,w)$ となる関数$r:\Sigma^\rightarrow\Sigma^$ を計算するチューリングマシン$R$ が存在する

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

不完全性定理（incompleteness theorem）
- 証明可能性の概念をどのように正式に記述しても、その証明体系において真であるにも関わらず証明不可能な命題が存在する

TURING帰着可能性（Turing reducibility）

帰着可能性の一般的な形
前提
- 言語$B$ に対するオラクル（oracle）は、任意の文字列$w$ が$B$ の要素であるかどうかを告げることができる外部装置である
- オラクルチューリングマシン（oracle Turing machine）はオラクルに質問する付加能力を持つよう変更されたチューリングマシンである
- $M^B$ を言語$B$ に対するオラクルを持つオラクルチューリングマシンとする
相対的に判定可能（decidable relative to）
- あるオラクルを用いることによって判定が可能になること
  - 所感：$A$ が判定可能であると仮定して〜という文脈を暗黙的に含んでいるから帰着できそう
定義
- 言語$A$ が言語$B$ に対して相対的に判定可能ならば、$A$ は$B$ にTuring帰着可能（Turing reducible）であると定義し、この関係を$A\leq_T B$ と書く
  - $B$ に対するオラクルに聞くことで$A$ が判定できるのであればTuring帰着可能ということ
定理
- $A\leq_T B$ であり$B$ が判定可能ならば、$A$ は判定可能である
  - 証明
    - $B$ が判定可能であれば、$B$ に対するオラクルを$B$ を判定する実際の手続きで置き換えられる
    - 従って$A$ を判定するオラクルチューリングマシンを$A$ を判定する通常のチューリングマシンで置き換えられる
通常のチューリングマシンでは解けない多くの問題を解くことができるが、すべての言語を判定できるわけではない

情報の定義

情報量
- 対象物の最小の表現のサイズ
最小記述（minimal description）
- その記述から対象物を再構成できる曖昧でない特徴づけ
- 定義
  - $x$ を二進文字列とし$x$ の最小記述を$d(x)$ と書く
  - これは、テープ上に$x$ を設定して停止するチューリングマシン$M$ と入力$w$ の対の内で、その記述$\langle M,w\rangle$ の長さが最短のものを指す
  - このような記述が複数存在するなら、その中で辞書式順序で最初のものを選ぶ
  - $x$ の記述の複雑さ（descriptive complexity）を$K(x)$ と書き、$K(x)=|d(x)|$ とする
- 定理
  - $\exists c\forall x[K(x)\leq|x|+c]$
    - 文字列の記述の複雑さが、その文字列の長さよりたかだか定数増しで抑えられるということ
      - 最小記述はその文字列より長くはならない
  - $\exists c\forall x[K(xx)\leq K(x)+c]$
    - 最小記述$d(_)$ は実際には$\langle N,w\rangle$ であるが、これに$x$ を渡したらそりゃ$xx$ でしょ
  - $\exists c\forall x,y[K(xy)\leq 2K(x)+K(y)+c]$
- 最小記述はアルゴリズムを用いた記述の複雑さを表す最適な尺度であることが証明されている
圧縮不可能な文字列は存在する
- 定義
  - $x$ を文字列とし、$K(X)\leq|x|-c$ であるとき、$x$ はc圧縮可能（c-compressible）であるという
  - $x$ がc圧縮可能でないとき、$x$ はc圧縮不可能（incompressible by c）という
  - $x$ が1で圧縮不可能なとき、$x$ は圧縮不可能（incompressible）であるという
- 圧縮不可能な文字列はランダムな文字列が持つと思われる多くの性質を持つ
- 長い圧縮不可能な文字列を生成する方法はない（Turing認識不可能）
- 文字列が圧縮不可能であるかを検査する方法もない（Turing判定不可能）

7 時間の複雑さ

複雑さの測定

最悪ケースの解析（worst-case analysis）
- ある特定の長さのすべての入力に対する最長の動作時間を調べる
  - そのアルゴリズムが取りうる一番長いやつでの時間
平均ケースの解析（average-case analysis）
- ある特定の長さのすべての入力に対する平均の動作時間を調べる
  - いろんなパターンを試して、その平均を取った時間
時間計算量（time complexity）
- $M$ をすべての入力で停止する決定性チューリングマシンとする
- $M$ の動作時間、すなわち時間計算量（time complexity）は関数$f:\mathbb{N}\rightarrow\mathbb{N}$ である
- ここで$f(n)$ は長さ$n$ の任意の入力に対して$M$ が必要とする最大ステップ量である
- $f(n)$ が$M$ の動作時間のとき、$M$ は時間$f(n)$ で動作し、$M$ は$f(n)$ 時間チューリングマシンであるという
漸近的解析（asymptotic analysis）
- あるアルゴリズムに対して大きい入力をしたときの所要時間を測る際、最高次の項だけを考え、それ以外を無視することでざっくりとした時間を出す方法
  - $n^3$ と$n^2$ なら前者のほうが所要時間の増加に占める割合が圧倒的にでかい
- 漸近的記法（asymptotic notation）・big-O記法（big-O notation）
  - 漸近的解析によって得られたざっくりとした所要時間を表す
    - $n^3$ かかるなら$f(n)=O(n^3)$
- 漸近的上界（asymptotic upper bound）
  - $f$ と$g$ を2つの関数$f,g:\mathbb{N}\rightarrow\mathbb{R}^+$ とする
  - すべての整数$n\geq n_0$ に対して、正の整数$c$ と$n_0$ が存在し、$f(n)\leq cg(n)$ であるならば$f(n)=O(g(n))$ という
  - $f(n)=O(g(n))$ のとき、定数係数を無視している
    - $g(n)$ は$f(n)$ の上界（upper bound）であり、より厳密には$g(n)$ は$f(n)$ の漸近的上界であるという
多項式境界（polynomial bound）
- $n^c$ となるような境界
指数境界（exponential bound）
- $2^n$ となる境界
small-o記法（small-o notation）
- ある関数が他の関数より漸近的に小さいことを示す
- 定義
  - $f$ と$g$ を2つの関数$f,g:\mathbb{N}\rightarrow\mathbb{R}^+$ とする
```
  $$
  \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
  $$
```
  - ならば、$f(n)=o(g(n))$ という
  - 言い換えると、$f(n)=o(g(n))$ は、任意の次数$c>0$ に対して$n_0$ が存在し、すべての$n\geq n_0$ に対して$f(n)<cg(n)$ であることを意味する
時間計算量のクラス（time complexity class）
- $t:\mathbb{N}\rightarrow\mathbb{R}^+$ を関数としたとき、$O(t(n))$ 時間チューリングマシンで判定されるすべての言語の集まりを、時間計算量のクラス$\mathsf{TIME}(t(n))$ とする

モデル間の複雑さの関係

$t(n)$ を$t(n)\geq n$ であるような関数とする
すべての$t(n)$ 時間複数テープチューリングマシンと等価な$O(t^2(n))$ 時間単一テープチューリングマシンが存在する
- 多項式時間でシミュレートできる
すべての$t(n)$ 時間非決定性単一テープチューリングマシンと等価な$2^{O(t(n))}$ 時間決定性単一テープチューリングマシンが存在する
- 木の頂点の数は高さを$n$ として$2^n$ 個の定数倍なので、計算木のすべてをシミュレートするとなるとそう
全探索（brute-force search）で問題を解こうとすると指数時間アルゴリズムになる場合が多い
すべての妥当な決定性計算モデルは多項式で等価（polynomially equivalent）である
- どのモデルでも、他のモデルを多項式の動作時間の増加でシミュレートできる

クラスP

クラスPの定義

$\mathsf{P}$ を決定性単一テープチューリングマシンによって多項式時間で判定できる言語のクラスとする（$k$ は定数）
$$ \mathsf{P} = \bigcup_{k} \mathsf{TIME}(n^k) $$
重要性
- $\mathsf{P}$ は、決定性単一テープチューリングマシンに多項式で等価なすべての計算モデルで不変である
- $\mathsf{P}$ は、計算機で現実的に解くことができる問題のクラスにほぼ対応している

Pに属する問題

グラフの連結を判定する問題
2つの数が互いに素か判定する問題
すべての文脈自由言語の判定
など

クラスNP

現在多項式時間で解けない問題のうち、どれか1つでも多項式時間のアルゴリズムが見つかれば、芋づる式で全部解ける
多項式検証可能（polynomial verifiability）
- その問題を多項式時間で解くことはできないが、検証はできるという性質
  - 検証すら多項式時間でできないものもある
- 多項式時間検証可能性の定義
  - アルゴリズム$V$ に対して、言語$A$ 次のように定義できるとき、$V$ を$A$ の検証装置（verifier）という
```
  $A=\{w|V\text{は、ある文字列}c\text{に対して}\langle w,c\rangle\text{を受理}\}$
```
    - $A$ は、アルゴリズム$V$ が$c$ を証拠として受理できるような問題$w$ の集合
      - $c$ は$w$ に対する解の1つ（証拠）と考えて良い
  - 検証装置の計算時間は$w$ の長さに関してのみ測る
  - よって、多項式時間検証装置（polynomial time verifier）とは、$w$ の長さに対して多項式時間で（証拠$c$ の）検証を行うアルゴリズムである
  - 言語$A$ が多項式時間検証装置をもつとき、$A$ を多項式検証可能（polynomial verifiable）という

クラスNPの定義

NPは多項式時間検証装置をもつ言語のクラスである
NPの意味
- 非決定性多項式時間（nondeterministic polynomial time）の略
非決定性の時間計算量のクラスの定義
- $\mathsf{NTIME}(t(n)) = {L \mid L \text{ は } O(t(n)) \text{ 時間の非決定性チューリングマシンで判定される言語}}$
```
$$
\mathsf{NP} = \bigcup_k \mathsf{NTIME}(n^k)
$$
```
NP中の言語の補言語からなる新しい複雑さのクラスをcoNPとしたとき、coNPがNPと異なるクラスであるかについてはまだわかっていない

P vs NP問題

PとNPが等しいか等しくないかはまだ証明されていない
- Pに属さないNPの言語はその存在すら証明されていない
NPの言語を決定性で解く場合、最良の方法でも指数時間がかかることは証明されている
$$ \mathsf{NP}\subseteq\mathsf{EXPTIME}=\bigcup_k\mathsf{TIME}(2^{n^k}) $$
- NPがより小さい決定制時間計算量のクラスに含まれているかはわかっていない

NP完全性

NP完全（NP-complete）
- NPに属する問題のいずれかに対して多項式時間アルゴリズムが存在するならば、NPに属するすべての問題が多項式時間で解けるという性質
充足可能性問題（satisfiability problem）
- 充足可能（satisfiable）
  - あるBoole論理式において、それを満たすことのできる組み合わせが存在する
- Boole論理式が充足可能であるかどうかを検査する問題
```
$$
SAT=\{\langle\phi\rangle|\phiは充足可能なBoole論理式\}
$$
```
- Cook-Levinの定理（Cook-Levin theorem）
  - $\mathsf{P}=\mathsf{NP}$ のとき、かつそのときに限り、$SAT\in\mathsf{P}$ である

多項式時間帰着可能性

問題$A$ が問題$B$ に効率的に帰着できるならば、$B$ に対する効率的な解放は$A$ を効率的に解くために使用できる
任意の入力$w$ で動作を開始し、テープに$f(w)$ だけを設定して停止するような多項式時間チューリングマシン$M$ が存在するとき、関数$f:\Sigma^\rarr\Sigma^$ を多項式時間可能関数（polynomial time computable function）という
多項式時間帰着可能（polynomial time reducible）の定義
- 言語$A$ と$B$ に対して、多項式時間計算可能関数$f:\Sigma^\rarr\Sigma^$ が存在し、すべての$w$ について
```
$$
w \in A \Leftrightarrow f(w) \in B
$$
```
- であるとき、$A \le_p B$ と書き、言語$A$ が言語$B$ に多項式時間写像帰着可能（polynomial time mapping reducible）、あるいは多項式時間帰着可能（polynomial time reducible）であるという
- 関数$f$ は$A$ から$B$ への多項式時間帰着（polynomial time reduction）と呼ばれる

NP完全性の定義

次の条件を満たす言語$B$ をNP完全（NP-complete）という
1. $B \in \mathsf {NP}$
2. $\mathsf {NP}$ に属するすべての$A$ が、$B$ に多項式時間帰着可能である
定理
- $B$ がNP完全であり、かつ$B \in \mathsf {P}$ ならば、$\mathsf {P} = \mathsf {NP}$ である
  - $B$ が$\mathsf {P}$ であるような何かに帰着できるなら成り立つよねそりゃ

8 領域の複雑さ

領域計算量（space complexity）
- $M$ をすべての入力に対して停止する決定性チューリングマシンとする
- 関数$f(n)$ を長さ$n$ の任意の入力に対して、$M$ が走査するテープのセル数の最大値とするとき、$M$ の領域計算量を$f : \mathbb{N} \rarr \mathbb{N}$ と定義する
- $M$ の領域計算量が$f(n)$ のとき、$M$ は領域$f(n)$ で動作するという
- $M$ をすべての入力に対してすべての枝が停止するような非決定性チューリングマシンとするとき、領域計算量$f(n)$ を、長さ$n$ の任意の入力に対する$M$ の計算の任意の枝上で$M$ が走査するテープのセル数の最大値と定義する
領域計算量のクラス（space complexity class）
- $f: \mathbb{N} \rarr \mathbb{R}^+$ を関数とする
- 領域計算量のクラス$SPACE(f(n))$ と$NSPACE(f(n))$ は以下のような定義である
  - $SPACE(f(n)) = {L|LはO(f(n))領域の決定性チューリングマシンによって判定される言語}$
  - $NSPACE(f(n)) = {L|LはO(f(n))領域の非決定性チューリングマシンによって判定される言語}$

SAVITCHの定理

非決定性チューリングマシンが$f(n)$ の領域を使ってある問題を解けるとき、決定性チューリングマシンは同じ問題を平方の領域を使って解ける
非決定性チューリングマシンを決定性チューリングマシンでシミュレートしても、使用する領域は多項式的にしか増えない
$f(n) \ge n$ を満たす任意の関数$f : \mathbb{N} \rarr \mathbb{R}^+$ に対して、$NSPACE(f(n)) \subseteq SPACE(f^2(n))$ である
- 非決定性チューリングマシンを決定性チューリングマシンでシミュレートするには高々関数を2回適用したくらいの領域で住む
- ただし、実行時間は指数時間

クラスPSPACE

PSPACEは決定性チューリングマシンによって多項式領域で判定可能な言語のクラス
$$ PSPACE = \bigcup_k SPACE (n^k) $$

PSPACE完全性

次の条件を満たす言語$B$ をPSPACE完全（PSPACE-complete）という
1. $B$ は$PSPACE$ に属する
2. $PSPACE$ に属するすべての$A$ が$B$ に多項式時間帰着可能
$B$ が条件2のみを満たすとき、PSPACE困難（PSPACE-hard）という

PSPACE完全である問題

TQBF問題
- 完全に限定されたBoole論理式が真か偽かを決定する問題
二人零和有限確定完全情報ゲーム
しりとり

クラスLとクラスNL

準線形（sublinear）領域計算量
- 線形モデルよりもさらに記憶容量が小さい
ここで考えるチューリングマシンは、読み出し専用と読み書き可能な2種類のテープを持つ
- 読み出し専用テープはROMとして使用
クラスLの定義
- $L$ を決定性チューリングマシン上で対数領域で判定可能な言語クラスとする
```
$$
L = SPACE(\log n)
$$
```
クラスNLの定義
- $NL$ を非決定性チューリングマシン上で対数領域で判定可能な言語のクラスとする
```
$$
NL = NSPACE(\log n)
$$
```
対数領域はポインタ等を使う計算に対応し、非常に小さいが必要かつ十分なサイズである
$L \ne NL$ と予想されているが、証明はされていない

NL完全性

対数領域帰着可能性（log space reducible）の定義
- 対数領域変換装置（log space transducer）は読み出し専用入力テープ、書き込み専用出力テープ、読み書き作業テープを持つチューリングマシンである
- 作業テープには$O(\log n)$ 個の文字を書き込むことができる
- 対数領域変換装置$M$ は関数$f:\Sigma^* \rarr \Sigma^*$ を計算する
- ここで、$f(w)$ は$M$ がその入力テープに$w$ を持って開始したとき、それが停止した後に出力テープ上に残っている文字列である
- このような$M$ をもつ$f$ を対数領域計算可能な関数（log space computable function）とよぶ
- 言語$A$ が対数領域計算可能な関数$f$ により言語$B$ に写像帰着可能なとき、$A$ は$B$ に対数領域帰着可能（log space reducible）といい、$A \leq_L B$ と書く
NL完全性の定義
- 次の条件を満たす言語$B$ をNL完全（NL-complete）という 1. $B \in NL$ 2. $NL$ に属するすべての$A$ が$B$ に対数領域帰着可能
ある言語が$L$ に属することが知られている他の言語に対数領域帰着可能ならば、その言語も$L$ に属する
$$ A \le_L B かつ B \in L ならば、A \in L である $$
- 入力$w$ を対数領域帰着$f$ を用いて写像し、それを$B$ に渡す場合、$f(w)$ を格納するのに対数領域で足りないかもしれない
- 発想を変え、$B$ を認識する$M_B$ を動作させながら、$f(w)$ の特定の値が必要になったタイミングで、$f(w)$ の計算を必要な部分までシミュレートしてその値を取得し、その時のヘッドの位置を見失わないようにさえすれば、$f(w)$ の全体を一時的にどこかに保存しておく必要なく計算できる
  - 必要な値は必要になったタイミングで計算することで、メモリ使用量を節約できるということ
    - 遅延評価的な
  - ただし時間はかかるので、時間と領域のトレードオフとなる
$NL \subseteq P$ である

NLとcoNLの等価性

NLとcoNLは等価である
- NPとcoNPの関係とは異なる

9 問題の扱いにくさ

扱いにくい（intractable）問題
- 膨大な計算時間や領域が必要になる問題

階層定理（hierarchy theorem）

より複雑性の高い問題のクラスには、より多くの言語を含むと言う理論
- 計算の複雑さには階層的な構造がある
  - $n^3$ 時間で判定できる問題は$n^2$ 時間で判定できる問題よりも多いはずである
領域構成可能（space constructible）
- $f(n)$ が少なくとも$O(\log n)$ である関数$f: \mathbb{N} \rarr \mathbb{N}$ に対して、$O(f(n))$ の領域計算量で入力文字列$1^n$ から$f(n)$ （の二進表現）を計算できるとき、$f$ を領域構成可能という
  - $n$ 個の$1$ に対して、それの二進表現を$O(f(n))$ の計算領域で計算できるチューリングマシン$M$ が存在するなら、そういう計算を行う関数$f$ は領域構成可能であるということ
領域階層定理（space hierarchy theorem）
- 領域構成可能な任意の関数$f: \mathbb{N} \rarr \mathbb{N}$ に対して、$O(f(n))$ 領域で判定可能であり、$o(f(n))$ 領域で判定不可能な言語$A$ が存在する
  - マジ！？
    - マジだった…
- $0 \leq \epsilon_1 \lt \epsilon_2$ となる任意の実数$\epsilon_1$ と$\epsilon_2$ に対して以下が成り立つ
```
$$
SPACE(n^{\epsilon_1}) \subsetneq SPACE(n^{\epsilon_2})
$$
```
時間構成可能（time constructible）
- $t(n)$ が少なくとも$O(n \log n)$ である関数$t: \mathbb{N} \rarr \mathbb{N}$ に対して、$O(t(n))$ の時間計算量で入力文字列$1^n$ から$t(n)$ の二進表現を計算できるとき、$t$ を時間構成可能という
  - $n$ 個の$1$ に対して、それの二進表現を計算する$O(t(n))$ 時間チューリングマシン$M$ が存在するなら、そういう計算を行う関数$f$ は時間構成可能であるということ
時間階層定理（time hierarchy theorem）
- 時間階層定理は領域階層定理より若干弱いらしい
- 時間構成可能な任意の関数$t: \mathbb{N} \rarr \mathbb{N}$ に対して、$O(t(n))$ 時間で判定可能であり、時間$o(t(n) / \log t(n))$ で判定不可能な言語$A$ が存在する
  - シミュレーション中はステップ数を記録して置かなければならない
    - $1 / \log t(n)$ はその分のオーバーヘッド
- $1 \leq \epsilon_1 \lt \epsilon_2$ となる任意の実数$\epsilon_1$ と$\epsilon_2$ に対して以下が成り立つ
```
$$
TIME(n^{\epsilon_1}) \subsetneq TIME(n^{\epsilon_2})
$$
```

指数領域完全性

EXPSPACE完全（EXPSPACE-complete）
- 定義
  - 次の条件を満たす言語$B$ である 1. $B \in EXPSPACE$ 2. $EXPSPACE$ に属するすべての$A$ が$B$ に多項式時間帰着可能

相対化（relativization）

定義
- 言語$A$ に対するオラクル（oracle）は、任意の文字列$w$ が$A$ に所属するか否かを教えてくれる装置である
- オラクルチューリングマシン（oracle turing machine）$M^A$ は、オラクルに問い合わせる事ができるように変形されたチューリングマシンである
- $M^A$ は実行中にオラクルテープ（oracle tape）に文字列を書き込み、オラクル$A$ にその文字列が$A$ に含まれるかの判定を問い合わせることができ、その判定結果は1ステップで与えられる
- $P^A$ をオラクル$A$ を用いたオラクルチューリングマシンが多項式時間で判定可能な言語のクラスとする
- $NP^A$ も同様に定義する
あるチューリングマシンに充足問題を解くオラクルを付与する
- $NP \subseteq P^{SAT}$ なので、このチューリングマシンはすべての$NP$ 問題を1ステップで解ける
  - $coNP \subseteq P^{SAT}$ でもあるので、$coNP$ についても1ステップで解ける
- NONMIN-FORMULAを定義する
  - $NONMIN-FORMULA = { \langle \phi \rangle | \phi は最小のBoole論理式でない }$
  - $SAT$ オラクルを備えた非決定性チューリングマシンは、2つのBoole論理式の非透過性の判定を$NP$ で行うことができるため、等価性の判定は$coNP$ であり、これは$SAT$ オラクルを用いれば多項式時間で調べることができる
  - 従って、$NONMIN-FORMULA$ は$NP^{SAT}$ に属する

対角線論法の限界

定理
1. $P^A \ne NP^A$ となるオラクル$A$ が存在する
2. $P^B = NP^B$ となるオラクル$B$ が存在する
これら双方が成り立ってしまう
証明
- オラクル$A$
  - 任意のオラクルに対して、$L_A$ を$A$ に属する要素と同じ長さのすべての文字列の集まりとする
```
  $L_A = \{ w | \exists x \in A [|x| = |w|] \}$
```
    - 任意の$A$ に対して言語$L_A$ は$NP^A$ に属する
      - $NP^A$ は非決定性多項式時間でオラクル$A$ を用いて判定可能な言語のクラス
      - 入力$w$ が$L_A$ に属するかどうかの判定は以下のように実行できる 1. 入力$w$ と同じ長さの文字列$x$ を非決定的に選ぶ 2. オラクル$A$ に$x$ が属するか問い合わせる 3. 属していれば受理
      - 各ステップは多項式時間で実行可能なので、$L_A \in NP^A$
        オラクル$A$ を構築中であるため正しく判定できるかどうかは関係なく、実行可能であることを示せば良い
  - $L_A$ が$P^A$ に属さないように$A$ を設計する
    - 入力長$n$ に対して、インデックスが$n$ 以下のすべての多項式時間オラクルチューリングマシン$M_1, M_2, …, M_n$ を用意する
    - 長さ$n$ の文字列$x_n = 1^n$ （$n$ 個の1からなる文字列）について
      - もし$M_i(x_n)$ が$x_n \in L_A$ と判定されるなら$A$ に長さ$n$ の文字列を含めない
      - もし$M_i(x_n)$ が$x_n \notin L_A$ と判定されるなら$A$ に長さ$n$ の文字列を含める
    - とすると、すべての多項式時間オラクルチューリングマシン$M_i$ が正しく$L_A$ を判定できない
    - よって$L_A \notin P^A$ となる
- オラクル$B$
  - $B$ を$TQBF$ とする
  - 以下の包含関係が成り立つ
```
  $NP^{TQBF} \subseteq^1 NPSPACE \subseteq^2 PSPACE \subseteq^3 P^{TQBF}$

  1. 非決定性多項式時間オラクルチューリングマシンを$TQBF$ に対する問い合わせに対する答えを計算する非決定性多項式領域チューリングマシンに変換できることより
  2. Savitchの定理より
  3. $TQBF$ は$TSPACE$ 完全
```
  - 以上より$P^{TQBF} = NP^{TQBF}$ となる

回路の複雑さ

Boole回路（Boole circuit）
- 定義
  - ワイヤ（wire）で連結されたゲート（gate）と入力ゲート（input gate）の集まり
  - ゲートの依存関係が循環するような結線は許されない
  - ゲートの種類は$AND$ ゲート、$OR$ ゲート、$NOT$ ゲートを基本とする
- Boole回路の入出力を表現するための関数
  - 入力変数$n$ 個のBoole回路$C$ に対して、関数$fc:{0,1}^n\rarr{0,1}$ を対応させる
    - つまり入力$x_1,…,x_n$ が$a_1,…,a_n$ であるとき、$C$ が$b$ を出力することを$fc(a_1,…,a_n)=b$ と記述する
回路族（circuit family）
- $C_n$ を$n$ 個の入力変数を持つ1つの回路とすると、回路族$C$ は回路の無限リスト$(C_0, C_1, C_2, … )$ である
- すべての文字列$w$ に対して、$n$ を$w$ の長さとして
  - $C_n(w) = 1$ のとき、かつそのときに限り$w \in A$
- となるとき、$C$ は${0, 1}$ 上の言語$A$ を判定するという
回路のサイズ（size）
- ゲートの個数
回路族のサイズの複雑さ（size complexity）・サイズ計算量
- 回路族$(C_0,C_1,C_2,…)$ に対して、$f(n)=(C_nのサイズ)$ と定義される$f:\mathbb{N}\rarr\mathbb{N}$
回路の深さ（depth）
- 入力ゲートから出力ゲートまでの最長パスにおける長さ（ワイヤの数）
言語の回路サイズの複雑さ（circuit size complexity）
- その言語を判定する最小の回路族のサイズの複雑さ
言語の回路深さの複雑さ（circuit depth complexity）
- その言語を判定する最小の回路の深さ
定理
$$ t: \mathbb{N} \rarr \mathbb{N} をt(n) \geq n なる関数とする \ A \in TIME(t(n)) ならば、 A の回路計算量は O(t^2(n)) である $$
Boole回路がチューリングマシンをシミュレートする能力がある

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

近似アルゴリズム（approximation algorithm）

最適な（optimal）解に近い解を使用する
- 最良なものでなくても良い状況に適している

確率的アルゴリズム（probabilistic algorithm）

ランダムな処理の出力を利用する
確率的チューリングマシン（probabilistic turing machine）
- 確率的チューリングマシン$M$ は非決定性チューリングマシンの一種である
- 各々の非決定ステップはコイン投げステップ（coin-flip step）と呼ばれ、そのステップのああとにコイン投げの結果に応じた2種類の正しい動作を持つ
- 入力$w$ に対する$M$ の計算の各々の枝$b$ に確率を割り当て、枝$b$ の確率を$Pr[b] = w^{-k}$ と定義する
- $k$ は枝$b$ でのコイン投げの回数である
- $M$ が$w$ を受理する確率を以下のように定義する
```
$$
Pr[Mはwを受理] = \sum_{bは受理状態} Pr[b]
$$
```
小さな確率の誤りを$\epsilon$ とする
- $M$ は言語$A$ を誤り確率$\epsilon$ で認識すると定義できる
クラスBPP（bounded-error probabilistic polynomial time）
- 確率的アルゴリズムにおける複雑さのクラス
- 確率的多項式時間チューリングマシンによって誤り確率$\frac{1}{3}$ で認識される言語のクラスである
誤り確率$\epsilon (0 \le \epsilon \lt \frac{1}{2})$ の確率的多項式時間チューリングマシン$M_1$ を用いて、与えられた多項式$poly(n)$ に対して、誤り確率$2^{-poly(n)}$ の等価な確率的多項式時間チューリングマシン$M_2$ を構成できる
- $M_1$ を$2k$ 回シミュレートしたときの多数決で判定する
- 繰り返したら確度が高まるのは当然

分岐プログラム（branching problem）

入力変数の値を質問し、その質問に対する答えに基づいて進むべきについて判断を下す
- 有向非巡回グラフとして表現できる
coNP完全である
一回読み出し分岐プログラム（read-once branching program）
- 開始から終了までのどのパスにおいても、各変数を最大一回しか質問しない分岐プログラム
- 一回読み出し分岐プログラムの等価性の判定は$BPP$ に属する

交替性

交替性チューリングマシン（alternating turing machine）
- 処理2つの枝に分かれる
  - 全称状態（universal state）
    - 子のすべての処理が受理されたら受理する
  - 存在状態（existential state）
    - 子の枝の内、1個が受理されたら受理する
- どちらかの枝が受理条件を満たした場合受理とする
- 複雑さのクラスの定義
```
$$
ATIME(t(n)) = \{L|LはO(t(n))時間交替性チューリングマシンによって判定される\}\\
ASPACE(t(n)) = \{L|LはO(t(n))領域交替性チューリングマシンによって判定される\}
$$
```
  - $f(n) \ge n$ に対して、$ATIME(f(n)) \subseteq SPACE (f(n)) \subseteq ATIME(f^2(n))$
  - $f(n) \ge \log n$ に対して、$ASPACE(f(n)) = TIME(2^{O(f(n))})$

対話証明系

クラスNPの確率版
証明者（prover）
- メッセージを検証者に納得させる
- 量に関して制限の無い計算能力を持つ
- 2つの入力をとる関数$P$ とみなす 1. 入力文字列 2. メッセージ履歴の一部
- 出力は次に検証者へ送るメッセージである
検証者（verifier）
- メッセージを検証する者
- それまでに交換されたメッセージの履歴から、証明者へ次に送付するメッセージを計算する
- 3つの入力をとる関数$V$ とみなす 1. 入力文字列 - この文字列がある言語の要素かどうかを判定する目的 2. ランダム入力 - 確率的な動作を行うために付与 3. メッセージ履歴の一部
- 出力は次のメッセージか最終的な結論${ 受理, 拒否 }$ である
証明者と検証者の対話
- 特定の文字列$w$ および$r$ に対して、ある$k$ に対してのメッセージの列$m_1$ から$m_k$ が存在し、以下が成り立つ場合、$(V \leftrightarrow P)(w,r)=受理$ とする 1. $0 \le i \lt k$ かつ偶数の$i$ に対して、$V(w,r,m_1#…#m_i) = m_{i+1}$ 2. $0 \le i \lt k$ かつ奇数の$i$ に対して、$P(w,m_1#…#m_i) = M_{i+1}$ 3. メッセージ履歴中の最後のメッセージ$m_k$ が受理
対話証明系が入力文字列$w$ を受理する確率
- $p(n)$ を交換されるメッセージの個数かつその長さとする
- 長さ$n$ の任意の文字列$w$ に対して以下のように定義する
  - $Pr[V \leftrightarrow P はwを受理する]=[Pr(V \leftrightarrow P)(w,r)=受理]$
    - $r$ は長さ$p(n)$ のランダムに選択された文字列

クラスIP

定義
- 以下を満たす多項式時間関数$V$ および時間的に制約のない関数$P$ が存在するならば、言語$A$ は$\mathsf{IP}$ に属するという
- すべての関数$\tilde{P}$ 及び文字列に対して 1. $w \in A$ ならば、$Pr[V \leftrightarrow P はwを受理] \ge \frac{2}{3}$ 2. $w \notin A$ ならば、$Pr[V \leftrightarrow \tilde{P} はwを受理] \le \frac{1}{3}$
クラスIPはクラスNPやBPPの両方を含む

IPとPSPACEは等価

$$ \mathsf{IP} = \mathsf{PSPACE} $$

並列計算

並列計算機（parallel computer）
- 複数の演算を同時に実行することが可能な計算機
- 並列ランダムアクセスマシン（parallel random access machine）・PRAM
  - パターン化された単純な命令セットをもつ理想化された複数のプロセッサが、計算機上で共有メモリを介して交信する
    - おおよそ現代のコンピュータと同等なモデル

クラスNC

ある問題は、ある定数$k$ に対して$(O(n^k),O(\log^kn))$ のサイズ・深さ計算量を持つ
- このような問題は適度なプロセッサ数で高い並列化が可能である
定義
- $i \ge 1$ に対して$(\mathsf{NC^i})$ を多項式サイズで深さ$O(\log^in)$ の回路の一様な族によって決定される言語のクラスとする
- ある$i$ に対して$\mathsf{NC^i}$ に属するすべての言語クラスを$\mathsf{NC}$ とする
- このような回路族によって計算される関数をNC計算可能（NC computable）という
他の複雑性クラスとの比較
- $\mathsf{NC} \subseteq \mathsf{L}$
  - 対数領域で計算可能な決定性モデルで計算できるやつよりは大きくない
    - 並列計算が可能である問題はポインタなんかを使って計算できる問題である
- $\mathsf{NC} \subseteq \mathsf{P}$
  - 並列計算が可能である問題は多項式時間で解ける
    - そりゃそうやろ
    - 並列計算を逐次計算でシミュレートできるということでもある

P完全性

定義
- 次の条件を満たす言語$B$ をP完全（P-complete）という 1. $B \in P$ 2. $A$ が対数領域で$B$ に帰着可能 - 対数領域で帰着可能であるということは$A$ は必ず$P$ に属することになる（$L \subseteq P$ なので）
もしNCがP完全であるならば、すべてのPは並列化可能であることを意味する
- しかし、$\mathsf{NC} \neq \mathsf{P}$ と予想されている

暗号

秘密鍵（private-key）

秘密鍵暗号（private-key cryptosystem）
- 暗号化した鍵を共有することで、それを知っている者のみが復号化できるような仕組み
- 暗号化と復号化に使う鍵が一緒

公開鍵（public-key）

公開鍵で暗号化したものは対応する秘密鍵でないと復号できない
秘密鍵で暗号化したものは対応する公開鍵でないと復号できない
公開鍵暗号（public-key cryptosystem）
- 公開鍵で暗号化し、秘密鍵で復号化する 1. 受信側：公開鍵を公開 2. 送信側：公開鍵を用いてメッセージを暗号化し送信 3. 受信側：秘密鍵を用いてメッセージを復号
- 暗号化と復号化に使う鍵が別
  - 送信側が鍵を持つ必要がない
デジタル署名（digital signature）
- 秘密鍵で署名を作成し、公開鍵で検証する 1. 送信側：秘密鍵を用いてメッセージから署名を作成し、メッセージと共に送信 2. 受信側：公開鍵を用いて署名を検証し、メッセージとの整合性を確認することで以下を確認可能 - メッセージがペアとなる秘密鍵の持ち主に署名されているか - メッセージが改ざんされていないか

一方向性関数（one-way function）

一方向性（one-way）
- ある関数の計算は容易だが、その逆関数の計算がほとんど常に困難であること
長さ不変（length-preserving）
- 関数$f:\Sigma^* \rarr \Sigma^*$ がすべての$w$ に対して$f(w)$ の長さが等しい
置換（permutation）
- 長さ不変の関数で、$x \neq y$ のとき、常に$f(x) \neq f(y)$ であること
一方向性置換（one-way permutation）
- 以下の2つの性質を持つ長さ不変の置換$f$ である 1. 多項式時間で計算可能である 2. すべての確率的多項式時間チューリングマシン$M$ 、すべての$k$ 、及び十分大きな$n$ に対して、長さ$n$ のランダムな$w$ を選び、入力$w$ に対して$M$ を動作させた場合に、$Pr_{M,w}[M(f(w))=w] \le n^{-k}$ となる - $Pr_{M,w}$ は確率が$M$ によるランダムな選択および$w$ のランダムな選択の上で取られることを意味する
- どのような確率的多項式時間アルゴリズムも、小さな確率でしか$f$ の逆関数を計算できないような置換である
一方向性関数（one-way function）
- 以下の2つの性質を持つ長さ不変の置換$f$ である 1. 多項式時間で計算可能である 2. すべての確率的多項式時間チューリングマシン$M$ 、すべての$k$ 、及び十分大きな$n$ に対して、長さ$n$ のランダムな$w$ を選び、入力$w$ に対して$M$ を動作させた場合に、$Pr[M(f(w))=y, ただしf(y)=f(w)] \le n^{-k}$ となる
- どのような確率的多項式時間アルゴリズムも$f(w)$ に写像されるような$y$ を見つけることはできないような関数である
- 公開鍵暗号の構築のための十分条件かどうかはわかっていない

落し戸関数

特別な情報が手に入ると効率的に逆関数の演算が可能になる
インデックス関数
- 以下の条件を満たす$f$
  - $\Sigma^$ に入る$i$ に対して関数族${f_i}$ があるとしたとき、その族を1つの関数$f: \Sigma^ \times \Sigma^* \rarr \Sigma^*$ として表す
    - ただし、$f(i,w) = f_i(w)$ である
落し戸関数（trapdoor function）
- $f:\Sigma^* \times \Sigma^* \rarr \Sigma^$ は長さ不変のインデックス関数であり、補助として確率的多項式時間チューリングマシン$G$ および関数$h: \Sigma^ \times \Sigma^* \rarr \Sigma^*$ をもつ
- 3つ組$(f, G, h)$ は以下の3つの条件を満たす 1. 関数$f$ および$h$ は多項式時間で計算可能である 2. すべての確率的多項式時間チューリングマシン$E$ 、すべての$k$ 、及び十分大きな$n$ 二対して、$1^n$ に対する$G$ のランダムな出力$\langle i, t\rangle$ およびランダムな$w \in \Sigma^n$ をとるとき、以下が成り立つ
```
    $$
    Pr[E(i, f_i(w)) = y, ただしf_i(y)=f_i(w)] \le n^{-k}
    $$

3. すべての$n$ 、長さ$n$ のすべての$w$ 、ある入力に対して非ゼロの確率で生じる$G$ のすべての出力$\langle i, t \rangle$ に対していかが成り立つ

    $$
    h(t,f_i(w))=y,ただしf_i(y)=f_i(w)
    $$
```

0 序論#

集合（set）#

列と組#

列（sequence）#

組（tuple）#

関数と関係#

関数（function）#

同値関係（equivalence relation）#

グラフ#

グラフ（graph）・無向グラフ（undirected graph）#

有向グラフ（directed graph）#

Boole論理（Boolean logic）#

定義、証明、定理#

定義（definition）#

証明（proof）#

定理（theorem）#

証明のタイプ#

1 正規言語#

有限オートマトン（finite automaton）・有限状態機械（finite state machine）#

計算の正式な定義#

正規演算（regular operation）#

非決定性#

非決定性有限オートマトン（NFA）#

正規演算の閉包性#

正規表現（regular expression）#

正規表現の正式な定義#

有限オートマトンとの等価性#

非正規言語#

ポンピング補題（pumping lemma）#

2 文脈自由文法#

文脈自由文法（context-free grammar）#

文脈自由文法の定義#

文脈自由文法の設計#

曖昧（ambiguous）#

CHOMSKY標準形（Chomsky normal form）#

プッシュダウン・オートマトン（PDA）#

プッシュダウン・オートマトンの定義#

非文脈自由言語#

文脈自由言語に対するポンピング補題（pumping lemma for context-free languages）#

3 CHURCH-TURINGの提唱#

チューリングマシン（Turing machine）#

チューリングマシンの正式な定義#

チューリングマシンの種類#

アルゴリズム（algorithm）#

4 判定可能性#

受理問題（acceptance problem）#

対角線論法#

受理問題の判定不可能性#

TURING認識不可能な言語#

5 帰着可能性#

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

停止問題（halting problem）の判定不可能性#

空性の判定不可能性#

同値性の判定可能性#

Riceの定理#

2つのチューリングマシンの同値性の判定可能性#

計算履歴を用いた帰着#

線形境界付きオートマトン（linear bounded automaton）#

単純な判定不可能問題#

写像帰着可能性（mapping reducibility）#

計算可能な関数（computable function）#

写像帰着可能性の定義#

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

再帰定理#

自己参照可能性#

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

TURING帰着可能性（Turing reducibility）#

情報の定義#

7 時間の複雑さ#

複雑さの測定#

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

クラスP#

クラスPの定義#

Pに属する問題#

クラスNP#

クラスNPの定義#

P vs NP問題#

NP完全性#

多項式時間帰着可能性#

NP完全性の定義#

0 序論

集合（set）

列と組

列（sequence）

組（tuple）

関数と関係

関数（function）

同値関係（equivalence relation）

グラフ

グラフ（graph）・無向グラフ（undirected graph）

有向グラフ（directed graph）

Boole論理（Boolean logic）

定義、証明、定理

定義（definition）

証明（proof）

定理（theorem）

証明のタイプ

1 正規言語

有限オートマトン（finite automaton）・有限状態機械（finite state machine）

計算の正式な定義

正規演算（regular operation）

非決定性

非決定性有限オートマトン（NFA）

正規演算の閉包性

正規表現（regular expression）

正規表現の正式な定義

有限オートマトンとの等価性

非正規言語

ポンピング補題（pumping lemma）

2 文脈自由文法

文脈自由文法（context-free grammar）

文脈自由文法の定義

文脈自由文法の設計

曖昧（ambiguous）

CHOMSKY標準形（Chomsky normal form）

プッシュダウン・オートマトン（PDA）

プッシュダウン・オートマトンの定義

非文脈自由言語

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

3 CHURCH-TURINGの提唱

チューリングマシン（Turing machine）

チューリングマシンの正式な定義

チューリングマシンの種類

アルゴリズム（algorithm）

4 判定可能性

受理問題（acceptance problem）

対角線論法

受理問題の判定不可能性

TURING認識不可能な言語

5 帰着可能性

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

停止問題（halting problem）の判定不可能性

空性の判定不可能性

同値性の判定可能性

Riceの定理

2つのチューリングマシンの同値性の判定可能性

計算履歴を用いた帰着

線形境界付きオートマトン（linear bounded automaton）

単純な判定不可能問題

写像帰着可能性（mapping reducibility）

計算可能な関数（computable function）

写像帰着可能性の定義

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

再帰定理

自己参照可能性

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

TURING帰着可能性（Turing reducibility）

情報の定義

7 時間の複雑さ

複雑さの測定

モデル間の複雑さの関係

クラスP

クラスPの定義

Pに属する問題

クラスNP

クラスNPの定義

P vs NP問題

NP完全性

多項式時間帰着可能性

NP完全性の定義