計算論§プログラミング論(立命館2022春講義)
35341, 35342
キーワード
以下で計算可能な関数は等価である
ブール変数$ x_1 \cdots x_n
$ f(x)=(x_1 + x_2 + \cdots + x_n)\cdots(x_1 + x_2' + \cdots + x_n)
$ f(x)=1を満たす$ x_1 \cdots x_nはあるか？
ナイーヴな方法なら$ O(2^n)
2変数なら
3変数以上なら
クラスNP(Non-deterministic Polynomial) $ n枚のカードから$ k番目に大きい数を求めるアルゴリズムは$ O(n)でできることがわかっている
第2回
$ M = (Q,\Sigma,\delta,q_0,F)
$ Q: 有限の状態の集合
$ \delta: $ Q \times \Sigma \mapsto Q，状態遷移関数
$ q_0 \in Q: 初期状態
$ F \sube Q: 受理状態の集合
形式言語
アルファベット$ \Sigma
アルファベットの要素: 文字$ x,y,\cdots
任意の文字の列: 文字列$ w
文字$ x,yの連結を$ xyや$ x \circ y
文字$ xを$ k回繰り返した文字列$ x^k
文字列$ wの長さ: $ |w|
文字列の長さが0を空列$ \varepsilon
$ |\varepsilon|=0
文字列の集合:言語$ L
言語$ L_1,L_2の和集合$ L_1 \cap L_2 = \{ x \mid x \in L_1 \lor x \in L_2 \}
言語$ L_1, L_2の連結$ L_1 \circ L_2 = L_1L_2= \{x \circ y \mid x \in L_1 \land y \in L_2 \}
言語$ L_1の$ k回連結$ L_1^k
特に任意の$ 0 \leq kについての連結$ L_1^\star（スター演算）
オートマトン$ M_1が受理する言語を$ L(M_1)と書く
最後の入力が終わった時点の状態が受理状態に含まれているとき，そのオートマトンで受理したと言う．
同じ入力に対して，複数の遷移が可能な（遷移先が決定不能な）オートマトン
可能性のある遷移先で，一個でも受理できるものがあれば受理という
$ M = (Q,\Sigma,\delta',q_0,F)
$ Q: 有限の状態の集合
$ \delta': $ Q \times \Sigma \mapsto 2^Q，状態遷移関数
$ q_0 \in Q: 初期状態
$ F \sube Q: 受理状態の集合
証明:
3/4回目
アルファベット$ \Sigmaに対して正規表現があり，帰納的定義がある
空集合$ \emptyset
空列$ \varepsilonは正規表現で，集合$ \{ \varepsilon \}を表す
$ a \in \Sigmaに対して，$ aは正規表現で，集合$ \{ a\}を表す
$ r,sがそれぞれの言語$ R,Sで正規表現なら，次は正規表現である
$ r+s，集合$ R \cap Sを表す
$ r \circ s，集合$ R \circ S($ RS)を表す
$ r*，集合$ R^*を表す
演算子の優先順位を次のように定める
$ + < \circ < * < ()
状態遷移を表す際に正規表現を使っても良い，というNFA
ただし，次の制約を付ける
何らかの次状態として初期状態$ q_sを取らない．
受理状態$ q_aの次状態はない．
$ M = (Q,\Sigma,\delta',q_s,q_a)
$ Q: 有限の状態の集合
$ \delta': $ (Q - \{ q_s \}) \times (Q - \{ q_a\}) \mapsto \cal{R}，状態遷移関数
ただし$ \cal{R}は$ \Sigma上で可能な正規表現全ての集合（$ \Sigma上の正規言語） 現状態から次状態への状態遷移を，正規表現でパターンマッチする
$ q_0 \in Q: 初期状態
$ q_a \in Q: 受理状態（一つしかないということに注意）
あるモデル$ A,Bで表現可能な言語集合$ L_A,L_B
$ L_A \sube L_Bなら，モデル$ Bはモデル$ Aより表現能力が高いという．
あるいは表現力が低くはないと云う
$ A \to Bと書く．
次を示す
次の順で証明する
1, DFA$ \toNFA
2, NFA$ \toDFA
3, NFA$ \toGNFA
4, GNFA$ \toNFA
5, RE$ \toGNFA
6, GNFA$ \toRE
DFA$ \toNFA
任意のDFA$ D =(Q,\Sigma,\delta,q_0,F)について
$ Dと同じ言語を受理するNFA$ N=(Q',\Sigma,\delta',{q_0}',F') が構成できる
ただし
$ Q'=Q,{q_0}'=q_0,F'=F
任意の$ q_x,q_yに対して，$ \delta(q_x)=q_yなら$ \delta'(q_x)=\{q_y\}，と定義する
NFA$ \toDFA
DFAが$ n状態なら最悪でも$ 2^n状態のNFAを考えれば良い
NFA$ \toGNFA
GNFA$ \toNFA
RE$ \toGNFA
当然ながら任意の正規表現$ rについて初期状態と受理状態$ q_s,q_aを$ rで架橋すればGNFAが出来る，が…
GNFA$ G_1,G_2の受理状態$ q_a^1と初期状態$ q_s^2をうまく接続できるように空列$ \varepsilonで繋ぐ
正規表現の帰納的定義による
GNFA$ \toRE
GNFAの複数状態を2状態に纏めまくる
5回目
例えば$ 0^n1^nは正規表現で表現できない（状態が無いので） $ P = \lang Q,\Sigma,\Gamma,\delta,q_0,F \rang
$ Q: 有限の状態の集合
$ \Sigma: 有限の入力記号の集合
$ \Gamma:有限のスタックアルファベットの集合
$ \delta: $ Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \mapsto 2^{(Q \times \Gamma_\varepsilon )}，状態遷移関数
ただし
$ \Sigma_\varepsilon = \Sigma \cup \{\varepsilon\}
$ \Gamma_\varepsilon = \Gamma \cup \{\varepsilon\}
$ q_0 \in Q: 初期状態
$ F \sube Q: 受理状態の集合
スタックのpush,popの形式的な表現
$ \varepsilon \to t': push
$ t \to \varepsilon: pop: （dev/nullに突っ込むと考えればいい） $ t \to t': pop & push
https://gyazo.com/9aa7f026ffb933912ea65748383d780f
$ \Gamma = \{0, \$\}に注意
https://gyazo.com/4a947639e387ab17d42e24ed98a61ef3
状態$ q_2で，入力が$ 0，スタックトップが$ \varepsilon（任意のスタックトップで）なら
$ q_2へ遷移し，スタックに$ 0を積む
今，$ q_2 \to q_3間の$ 1, 0\to\varepsilonを$ \varepsilon, \varepsilon \to \varepsilonとしても良い
$ \varepsilon遷移はいつでも任意のタイミングで行えるを意味す
$ C = \lang V, \Sigma, R, S \rang
$ \Sigma: 終端記号の有限集合，アルファベットとも，$ V \cup \Sigma = \empty $ A \in V, \alpha \in (V + \Sigma)^*として$ A \to \alpha
簡単のために，任意回の同じ導出規則を適応することを$ \alpha \to^* \betaとする
5回目
ただし，簡単のためにスタックに任意長の文字列を突っ込めるとする
任意長の文字列スタックを1文字スタックに直すのは簡単なので
任意の文脈自由文法$ C=\lang V,\Sigma,R,S \rangに対応する $ \Sigma':=\Sigma
$ \Gamma':=V\cup\Sigma\cup\{\$\}
$ Q := \{q_s,q_l,q_e\} \cup E
ただし$ Eは任意長文字列スタックのための拡張（特に考える必要はない）
$ F := \{q_e\}
$ \deltaを（おさらい，$ \delta : Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \mapsto 2^{Q\times\Gamma_\varepsilon}）
$ \delta(q_s,\varepsilon,\varepsilon) = \{(q_l,S\$)\}
$ S\$という2文字をスタックに積む，の意味
$ A \in Vに対して$ \delta(q_l,\varepsilon,A) = \{(q_l,w) \mid (A \to w) \in R \}
全ての非終端記号$ Aに対して，$ Aに対応する導入規則の先$ w（任意長の文字列）をスタックに積む（ような遷移） $ a \in \Sigmaに対して$ \delta(q_l,a,a) = \{(q_l,\varepsilon)\}
終端記号をスタックから除去する遷移
$ \delta(q_l,\varepsilon,\$)=\{(q_e,\varepsilon)\}
スタックの底を除去して終了状態へ移行する遷移
6回目
プッシュダウンオートマトン$ P = \lang Q,\Sigma,\Gamma,\delta,q_s,\{q_e\} \rangに 対応する文脈自由文法$ C = \lang V,\Sigma',R,S \rangを構成する ただし，この$ Pには次の3制約がある
受理状態が唯一
元の受理状態に対して$ \varepsilon, \varepsilon \to \varepsilonで一つの受理状態に飛ばせば良い
受理したときにスタックが空
受理状態に行く前に絶対に$ \$ \to \varepsilonを通り，その後は$ \varepsilon \to \varepsilonのみ
pushかpopのみを考える：スタック操作$ a \to b \quad (a, b \neq \varepsilon)は考えない
適当にバラせばよい
$ a \to b: $ a \to \varepsilonと$ \varepsilon \to bへ
$ V = \{A_{pq} \mid p,q \in Q\}
ただし$ A_{p_i q_j}を$ A_{ij}と略記する．
$ \Sigma' = \Sigma
$ S = A_{se}=A_{q_s q_e}
$ Rは，次の3種類で取る
1,
$ p,q,r,s \in Q \quad a,b \in \Sigma_\varepsilon \quad t \in \Gamma
$ (r,t) \in \delta(p,a,\varepsilon): push
$ (q,\varepsilon) \in \delta(s,b,t): pop
なら，$ A_{pq} \to aA_{rs}b \in R
https://gyazo.com/343c09e13983bf801a9c73ab9355123d
push/popに対する規則がある，の気持ち
スタックが空になるためにはpushしたらpopが絶対対応する
2, 任意の$ p,q,r \in Qについて，$ A_{pq} \to A_{pr}A_{rq} \in R
3, $ p,qの遷移が$ a, \varepsilon \to \varepsilonの遷移の任意の$ p,qについて，$ A_{pq} \to a \in R
特に，$ aが$ \varepsilonのとき$ A_{pq} \to \varepsilon \in R
1,2,3のうち，最低でも，1で集めた$ Rについて，その$ Rに登場する$ A_{pq}に関連するものだけを2,3から抽出すればよい
7?
無限に，どこにでも，書き込める，テープを持つ
$ T = \lang Q,\Sigma,\Gamma,\delta,q_0,B,F \rang
$ Q: 有限の状態の集合
$ \Sigma: 有限の入力アルファベット
$ \Gamma: 有限のテープアルファベット
ただし$ \Sigma \sube \Gamma
$ \delta: 状態遷移関数$ Q\times\Gamma \mapsto Q\times\Gamma\times\{L,R\}
$ q_0 \in Q: 初期状態
$ B \in \Gamma: 空白記号
ただし$ B \notin \Sigma
$ F \sube Q: 受理状態
受理状態に辿り着けさえすればタイミングを無視して，受理とする
遷移が未定義なら非受理とする
延々に遷移してしまうことは決定不能と呼ぶ
状態，テープ内容，ヘッド位置の3組で記述される
$ a_1 \cdots a_m q_i b_1 \cdots b_n
テープが一個だと議論がしにくいので
複数のテープを直列に繋ぐように考える
$ \delta: Q \times \Gamma^k \mapsto Q \times \Gamma^k \times \{L,R\}^k
$ kはテープ数（有限個）
テープヘッドは$ \hat{a},\hat{b}みたいな感じで擬似的に再現する
毎回左から舐めてテープヘッドを決定する
一つの様相から$ n個の遷移を考えてOK
つまり
$ \delta: Q \times \Gamma \mapsto \mathcal{P}(Q \times \Gamma \times \{L,R\})
あらゆる可能性において，どれか一つでも受理状態に行けば受理
NTMの計算木を深さ優先探索で探索すると決定不能の場合で詰む
9?
Turingマシンは適当な入力記号の文字列にエンコード可能なので，それを入力に取るメタなチューリングマシンを構築できる チューリングマシンで認識不可能な言語が存在する
チューリングマシンの停止性問題は非可解（決定不能）である
チューリングマシン$ Tに入力$ \sigmaを与えると停止するか？
計算速度については異様に高速
非多項式時間の計算が出来る
今こういう関係だろうと思われている
DTM < QTM < PTM < NTM
NTMは作れない，それ以外3つは作れそう
11
グラフが合ったとき，2回同じ点を通らずに元の頂点に帰ってこれる閉路が存在するか？ 入力サイズ$ nに対して$ T(n)回（$ T(n)は$ nを変数に持つ式）の遷移で必ず停止する決定性チューリングマシン 例えば，$ O(n^2)決定性チューリングマシンとか表す
このとき，クラスPを$ \bigcup_k TIME(n^k)で定義する． 12
最も早く受理状態に辿り着くステップ（計算パス）の長さを計算時間とする
最短の受理状態への計算パスの長さ
計算時間が$ T(n)以上かかる計算パスは全部非受理と考える
このとき，クラスNPを$ \bigcup_k NTIME(n^k)と定義する ある和積形の論理式を充足する変数の割当が存在するか？
13
検証可能性
あるアルゴリズム$ Vに対して次の言語$ Aが定義出来るなら，$ Vは$ Aの検証装置(Verifier)と読ぶ
$ A = \{w \mid \text{$V$は文字列$c$に対して$\lang w,c\rang$を受理}\}
ただし，$ cは証拠(witness)と呼ばれる
2, 証拠の検証が多項式時間で判定出来る
1から2への証明
非決定性チューリングマシンで受理される計算パス = 証拠
この証拠と元のNTMの動作をエミュレート出来るDTMを構成すれば良い
2から1への証明
検証装置$ Vが$ n^kは動作するDTMであると仮定する
長さ$ n^kの文字列$ cを非決定的に選択する
入力$ \lang w,c \rangのときの$ Vの動作をNTMでエミュレートする
$ Vはある$ cで受理するなら受理し，$ Vがすべて拒否するなら拒否する
ある問題を別の問題に変換する
この変換が多項式時間で解けるなら…
問題（言語）$ A, Bについて
$ A \leq^P_M Bあるいは単に$ A \leq B
$ Bは$ Aより易しくない
$ Bが多項式時間で解けるなら$ Aも多項式時間で解ける
$ w \in A \iff f(w) \in B
$ f:\Sigma^* \mapsto \Sigma^*を多項式時間帰着関数
このとき$ Aは$ Bに多項式時間many-to-one帰着可能である
問題を解くより，問題を別の既知の問題に変換できないか？という発想
用語
リテラル：ブール変数の肯定あるいは否定，$ x, \bar{x}とか
節：リテラルの論理和
CNF：節を論理積で結んだ論理式
Conjunctive Normal Form
無向グラフ$ G=(V,E)
$ k点の完全部分グラフを$ kクリーク
ある無向グラフ$ Gに$ kクリークが存在するか？
3-SATはクリーク問題に帰着できる
ただし，3-SAT問題における論理式の節の数を$ pとしたときに，$ pクリークを探すような問題である
14
次の関係が成り立つとされる
$ \text{P} - (\text{NP} - \text{complete}) = \empty
適当なNP問題の際のチューリングマシンの動きを頑張って論理式(SAT)で表す 15
クラスBPP: Bounded-error Probablistic Polynomial クラスBQP: Bounded-error Quantum Polynomial