Presentation is loading. Please wait.

Presentation is loading. Please wait.

計算量の理論 講義資料 ver.1 (2006.1.12).

Similar presentations


Presentation on theme: "計算量の理論 講義資料 ver.1 (2006.1.12)."— Presentation transcript:

1 計算量の理論 講義資料 ver.1 ( )

2 教科書 講義資料 オートマトン 言語理論 計算論 Ⅱ (第2版) J.ホップクロフト・R.モトワニ・J.ウルマン
オートマトン 言語理論 計算論 Ⅱ (第2版) J.ホップクロフト・R.モトワニ・J.ウルマン 講義資料

3 機械モデルと言語の階層 有限オートマトン ⇔ 正則言語(正規表現) (1年:形式言語とオートマトン)
有限オートマトン ⇔ 正則言語(正規表現) (1年:形式言語とオートマトン) プッシュダウンオートマトン⇔文脈自由言語                  (文脈自由文法) (3年:コンパイラ) テューリングマシン⇔ 帰納的可算言語

4 Turing機械の能力と使いみち 能力 使いみち コンピュータで認識できる言語を認識 計算可能なものはすべて計算できる 計算の限界
真偽を判定できるアルゴリズムの限界 計算量

5 Turing機械(TM)の概念図 B B X1 X2 Xi Xn B テープ セル 空白 有限制御部

6 有限オートマトンとの違い テープは左右無限に延びている。 入力記号以外にも記号がある。(全体でテープ記号)
空白を意味する記号B(テープ記号のひとつ)がある。 テープヘッドは左右どちらにも動ける。

7 数学的な定義 Turing機械Mは次の7つ組で定義される: M = (Q, Σ, Γ, δ, q0 , B, F) Q : 状態の有限集合
Σ : 入力記号 Γ : テープ記号の有限集合Γ ⊆Σ δ :  δ (q, X)=(p,Y,D) (p:次状態, Y:書込む記号,D:ヘッドの動く向き) q0 : 初期状態(∈ Q ) B : 空白記号(∈Γ- Σ ) F : 終状態(または受理状態)の集合( ⊆ Q )

8 Turing機械の時点表示 (Instantaneous Description, ID)
B B X1 X2 Xi Xn B テープ q X1X2 … Xi-1qXi … Xn テープヘッドが空白以外の記号の左端または右端を 超える場合はそこの空白文字をX1またはXnとする。

9 Turing機械の動作 q p δ(q,Xi ) = (p, Y, L)のとき
B B X1 X2 Xi Xn B δ(q,Xi ) = (p, Y, L)のとき q B B X1 X2 Xi-1 Y Xn B p X1X2 … Xi-1qXi … Xn |- X1X2 … pXi-1Y … Xn

10 遷移の例外 q δ(q,X1) = (p, Y, L)のとき δ(q,Xn) = (p, B, L)のとき B B X1 X2 Xi Xn

11 遷移グラフ X/Y→ q p δ(q,X1) = (p, Y, R) をあらわす有向辺

12 Turing機械が受理する言語 ID1 |- ID2 Turing機械がID1からID2まで1回の動作で到達する ID1 |-* ID2
Turing機械M =(Q, Σ, Γ, δ, q0 , B, F)が 受理する言語L(M)は L(M)={w∈S* | ∃a,b ∈ G*, ∃p∈ F, q0w|-*apb}

13 言語を受理するTMの設計 L={0n1n| n≧1} q0 方針: 0と1を1個ずつ交互に消していく。 最後にどちらもなくなれば受理。 B
1 1 B q0 方針: 0と1を1個ずつ交互に消していく。 最後にどちらもなくなれば受理。

14 工程の概略 0: 0をXに変えて右に動いて goto 1 1: 右にスキャンして1を探す 2: 左にスキャンしてXを探す
Yだったら goto 3     /* 0はもう無かった*/ 1: 右にスキャンして1を探す 1をみつけたらYに変えて左に goto 2  /*消した数同じ*/ Bをみつけたら停止(拒否) /* 1はもう無かった */ それ以外は読み飛ばす goto 1 2: 左にスキャンしてXを探す Xをみつけたら 右に動いて goto 0 3: 右にスキャンして1が残ってないか探す 1をみつけたら停止(拒否)   /* 1の方が多かった */ Bをみつけたら goto 4 (受理) /*どちらも残っていない*/ それ以外は読み飛ばす

15 0/X → q0 q1 B 1 1 B q0 B X 1 1 B q1 左端の0を「消す」

16 q0 q1 q2 q3 q4 0/0→ 0/0← Y/Y→ Y/Y← 1/Y← 0/X → X/X→ Y/Y→ B/B→ X/X→ Y/Y→
開始 Y/Y→ Y/Y← 1/Y← 0/X → q0 q1 q2 X/X→ Y/Y→ q3 q4 B/B→ X/X→ Y/Y→

17 計算可能な言語 TMで受理される言語は帰納的可算(recursively enumerable)である、という。
帰納的可算な言語Lはw∈ L でない語にたいするTMの停止性は保障しない。実際L を受理するどんなTMに対しても、TMが停止しない語が存在する。 帰納的可算言語はある語がその言語の語か否か(帰属判定)をTMができないような言語も含む。

18 帰納的集合 すべての入力に対して停止するTMで受理される言語を帰納的である、という。またそのような言語を帰納的集合(recursive set)という。 帰納的集合は帰属判定が可能

19 TMプログラミング技法:多重トラック 各セルには記号[X,Y]∈G が入る X ∈G1,Y∈G2ならば G=G1 ×G2のようにとる。 B
1 B X 各セルには記号[X,Y]∈G が入る X ∈G1,Y∈G2ならば G=G1 ×G2のようにとる。

20 TMの拡張: 多テープTM B 1 B B 1 1 1 B B X 1 B q1

21 多テープTMの能力 定理 多テープTMが受理する言語は帰納的可算 q1 右に何個Xがあるかも覚える B 1 B B 1 1 1 B B X
定理 多テープTMが受理する言語は帰納的可算 B 1 B X B 1 1 1 B X B X 1 B X 右に何個Xがあるかも覚える q1

22 制限されたTM X-1 X1 X2 X3 Xn X1 X2 X3 Xn X-1 半無限テープTMによるTMの模倣

23 TMと同等のモデル q p q p TM 2スタック機械による模倣 B X1 X2 X3 X4 X5 X6 B B X1 X2 Y X4

24 コンピュータとTM コンピュータのモデル 語(word)は任意長で番地(address)をもつ プログラムはメモリー上に格納される
命令は有限個の語から成り、語を書き換える 命令は語を直接書き換える(レジスタなし)

25 TMによるコンピュータの模倣 #10011*10100 x w $w I/O
記憶テープ $0*w0#1*w1#10*w2#11*w3#100*w … #10011*10100 x 番地*中身# データとプログラム 命令カウンタ 10011 w 次に実行される命令が格納された番地 記憶番地 10100 $w 番地または中身の一時置き場 命令 ジャンプ データ   I/O

26 決定不能性 ~計算の限界~

27 「問題」とは何か? 問題は、「未知の入力がある性質を持つか否か」を問うもの。 与えられた特定のものに関する真偽判断を求めるものではない。
問題の例: 「与えられた言語が正則か否か?」 「与えられたCプログラムがHello Worldを出力するか?」(HelloWorld問題) 問題ではない例: 「{w|w中の0と1の個数が同じ}は正則か?」 問題の実例(instance)

28 Hello World検査機は存在するか?
問題:「CプログラムPにデータIを入力したときにPがHello Worldを印字するかどうか?」 に答える機械である。 I Yes Hello World 検査機 H P No

29 Hello World検査機の改造 I Yes P Hello World もしHelloWorld検査機が存在すれば…
[改造1] H1はNoの代わりにHello Worldを出力 I Yes H1 P Hello World

30 H1の改造 P Yes P Hello World [改造2] H2はIの代わりにPを入力とし入力を1つに統合 H1 H2
Yesは「PにPを入力するとHello Worldを出力する」ことを意味し Hello Worldは「PにPを入力するとHello Worldを出力しない」を意味する

31 Yes Hello World H2に自分を入力したらどうなるか? H2 H2
Yesだとすると、「H2にH2を入力するとHello Worldを出力する」ことを意味する Hello Worldだとすると「H2にH2を入力するとHello Worldを出力しない」ことを意味する

32 決定可能性 問題が決定可能(decidable)であるとは、入力が所望の性質を持つか否かを計算で判定(検査)することができること。
決定可能でないとき決定不能(undecidable)という。 例 HelloWorld問題は決定不能 (HelloWorld問題を解く計算法は存在しない)

33 厳密な議論のために H2はCで書けるのか?

34 2進列の番号付け w∈{0,1}* (2進列)をi=1w(2) (2進数)に対応させ, wはi番目の列である、などという。
i番目の列をwiとかく。 例 eは 1e=1 1(2) =1(10) 番 01は 101(2) =5(10)番    w5 =01

35 TMの符号化 Turing機械 M = (Q, Σ, Γ, δ, q0 , B, F) Q = {q1 , q2 , …, qr}
Γ = {X1, X2, X3, X4, …, Xs} (X1 =0, X2=1, X3=B) L=D1, R=D2 を符号(2進列)に変換する方法: 遷移規則δ(qi , Xj) = (qk, Xl , Dm) 0i10j10k10l10m TM全体: C111 C2… Cn (Ciは遷移規則の符号)

36 (M, w)の符号化 TM Mとそれへの入力語wの組はMの符号化を uとしてu111wと定義 (uの中に111は存在しないことに注意)
後に、 w∈L(M)⊆{0,1}*となる(M, w)の符号化全体が決定不能であることを示す。

37 TMの数え上げ q0 符号化がi番目の語wiとなるようなTM をMiと書き、i番目のTMと呼ぶ。
符号化とは逆にwiからMiを得ることを復号という。 wiがTMの符号化になっていないときは Miは右のようなTMであるものとする。 (右のTMはいかなる記号を入力しても 直ちに拒否して停止するので 受理言語は空集合φである。) 開始 q0

38 対角線言語Ld Ldの特徴ベクトル 言語Ldを次のように定義する。 Ld={wi|wi∈L(Mi)} w すなわち、Ldは自分自身を
復号して得られるTMに受 理されない語からなる集合。 w j → 1 2 3 4 5 6 1 1 2 3 4 5 i↓ L(Mi)の特徴ベクトル 6 M LdとL(Mi)の特徴ベクトルは i番目要素が異なる wj∈L(Mi)のとき1

39 Ldが帰納的可算でないことの証明 Ldが帰納的可算であるとすると、 あるiが存在してLd=L(Mi) …(1) wi∈Ldか否か調べよう。
wi∈Ldならば(1)によりwiはMiに受理される。 ところがこれはLdの要素の定義を満たさない。 wi∈Ldならば(1)によりwiはMiに受理されない。 ところがこれはLdの要素の定義を満たす。 いずれにせよ矛盾。(終わり)

40 言語Ldの位置づけ 帰納的可算(RE)言語 REだが帰納的でない Ld REでない 帰納的言語

41 帰納的言語の性質(1) [定理] Lが帰納的言語ならばその補集合 Lも 帰納的 (証明) L を受理する必ず停止するTM M w 受理 受理
非受理 M M 受理 w 非受理

42 帰納的言語の性質(2) [定理] Lとその補集合 LがともにREならば Lは帰納的 (証明) L を受理するTM M1,
非受理 M M1 受理 w M2 受理

43 万能言語Lu 万能言語と呼ぶ言語LuはTM Mとそれで受理される語wとの組(M, w)を符号化したもの全体からなる言語である。
Lu ={ψ(M, w)∈{0,1}* | w ∈L(M )}

44 Luは帰納的加算 (証明)Luを受理するTM Uの存在を示す。 (Universal Turing Machine) 入力 M w
Xiを0iで Mの状態 000 … 0BB … qiを0iで メモテープ

45 Luは帰納的でない (帰属問題が決定不能)
(証明)Luが帰納的であるとする。 するとLuも 帰納的。 Luを受理するTMをMとしてLdを受理するTMを構成する。 受理 Luを受理するM 受理 コピー w111w w 拒否 拒否

46 言語LuはREであるが帰納的でない 帰納的可算(RE) REだが帰納的でない Ld Lu REでない 帰納的言語

47 還元論法 P2 P1 ⇔ P1はP2より易しい 変換機ψは問題P1を問題P2に還元する、という。 受理 受理 変換機 M2 ψ 拒否 拒否
M2を仮定して、(存在しないことがわかっている) M1が構成できれば、背理法によりM2は存在しないと結論できる。 M2があればM1もある⇔ P2が解ければP1も解ける ⇔ P1はP2より易しい 変換機ψは問題P1を問題P2に還元する、という。

48 還元論法の主張 P1がP2に還元できるとき、次が成り立つ。 P1が決定不能ならP2も決定不能 P1が非REならP2も非RE

49 還元の条件 任意の入力に対してM1が正しく受理/拒否しなければならない。 拒否のときも同様 P2 P1
ψは、M1に受理されるはずの語w∈L1に対して M2に受理される語ψ(w)= u∈L2を出力する 拒否のときも同様 受理 M2 受理 変換機 ψ P2 P1 拒否 拒否 M1

50 ψの条件の図 w∈L1 ⇒ ψ(w) ∈L2 ψ yes yes No No P2 P1

51 還元の例(LeとLne ) wiはTM Miの符号化である。 以下でMiとwiを同一視し、語の文脈でMiと書けばwiを意味するものとする。
(Lが言語のときM∈LはM=Miの符号wi∈Lの意) LeとLneを以下で定義する。 Le={M|L(M)= φ} Lne={M|L(M)≠φ} Leは受理言語が空であるTMの符号の集合 Lneは受理言語が空でないTMの符号の集合

52 p1 q pn (証明で使うので追加) 非決定性TM 決定性TM (deterministic TM, DTM)
δ(q, X)=(p,Y,D) 非決定性TM (nondeterministic TM, NTM) δ(q, X)={(p1, Y1, D1), (p2, Y2, D2), …, (pn, Yn, Dn)} p1 X/Y1D1 q pn X/YnDn

53 NTMはDTMで模倣できる NTM MN を模倣するDTM MD
x IDの キュー ID1*ID2*ID3*ID4* …IDj *IDj+1 … * IDj+k *ID3 … * ID3 テープ 現在の状態と読み込み記号に対して遷移がk個あるとき、xとマークされた現在のIDを読み取り、受理状態なら終わり。そうでなければキューの後ろにk個コピーする。 コピーしたk個のIDをそれぞれk個の遷移にしたがって更新 xマークを次のIDに移す

54 NTMは推測をする NTMによる受理はDTMによる幅優先探索
ID1 ID2 ID3 ID4 IDj+k IDj+1 IDj+2 逆に、幅優先探索で見つかる解はNTMで受理される。このことをNTMが解を推測する、という

55 推測の例1 入力語wに対してw= wiとなるiは存在するか? exist i s.t. w=wi ? w=wi ? yes yes i w
DTMによる探索 NTMによる推測

56 推測の例2 TM Mに対してw∈ L(M)となるwは存在するか? exist w s.t. w∈ L(M)? w∈ L(M)? yes
DTMによる探索 NTMによる推測

57 LneはRE Lneを受理するTMを構成 非決定版のU(Universal TM)を使って
bool U(M, w){return (w∈L(M)) } 推測 受理 受理 w U Mi M

58 Lneは帰納的でない [証明] LuをLneに還元する。 M’ =ψ(M, w)とすると、
還元の条件:  (M, w)∈Lu ⇒ M’ ∈Lne (M, w)∈Lu ⇒ M’ ∈Lne この条件を満たすアルゴリズムψが存在すればOK U 受理 受理 w ψ Mne M M’ 拒否 拒否

59 (M, w) から M’(下)を構成するアルゴリズムをψとする。
[証明(つづき)] ψの仕様: (M, w) から M’(下)を構成するアルゴリズムをψとする。 受理 受理 w M x M’ ψが還元の条件を満たすこと: (M, w)∈Lu ⇒ w∈ L(M) ⇒ x∈L(M’) ⇒ M’∈Lne (M, w)∈Lu ⇒ w∈ L(M) ⇒ ∀x.x∈L(M’) ⇒ M’∈Lne

60 xiは(M,w)の符号i番目の記号, n=|(M,w)の符号|
[証明(つづき)] ψの存在: ψはM’ を次の手順で構成する。 xiは(M,w)の符号i番目の記号, n=|(M,w)の符号| */x0→ */x1→ */xn-1→ B以外/B→ q0 q1 q2 qn B/B← p0はUの開始状態 qn+1 B以外/ そのまま← B/B→ p0 U [証明おわり]

61 LeはREでない [証明] LeがREであると仮定する。 Lne = LeはREであったから、
Lneは自身とその補集合がREであることになり 帰納的言語の性質(2)によりLne(およびLe )は 帰納的となる。これはLneが帰納的でないことに反する。

62 RE言語の性質 RE言語の集合を(RE言語の)性質(property)
例:正則言語であるという性質は 正則言語全体の集合。空集合である という性質は{φ} (空集合1つだけ からなる集合)。 RE言語の性質は空{} であるか RE全体であるとき自明(trivial)、 そうでないとき自明でない(non-trivial) RE言語全体 (RE言語の) 性質P

63 性質を特徴付ける言語 P がRE言語の性質のとき、言語 RE言語の性質を問題(TMへの入力)にするため、 LP ={M|L(M)∈P }
という問題(の決定可能性)を、 Lを受理するTM M(の符号)を用いて、 「 MがLP に属するか否か」 という問題に置き換える。 (LはREだから常にM が存在することに注意)

64 性質に関する決定問題 Pは自明でないのでφでない言語Lを要素として持つ。 Lを受理するTMをMLとする。 Riceの定理
RE言語の自明でない性質は決定不能である。 [証明]P を自明でない性質とする。まず、φ∈P と仮定する。(そうでない場合は後で。) Pは自明でないのでφでない言語Lを要素として持つ。 Lを受理するTMをMLとする。 以下でLU がLP に還元できることを示す。 還元をψ(M, w) = M’ として、 還元の条件:  (M, w)∈Lu ⇒ M’∈LP (M, w)∈Lu ⇒ M’∈LP

65 L∈P であったからM’∈LP (証明つづき) (M, w)∈Luのとき M’はMLを模倣し、 Lを受理する。
開始 受理 受理 ML x M’ ψが還元の条件を満たすこと: (M, w)∈Luのとき M’はMLを模倣し、 Lを受理する。 L∈P であったからM’∈LP (M, w)∈Luのとき M’はどんなxも受理せず、したがって言語φを受理する。 φ∈P であったからM’∈LP 還元ψのTMによる構成はLneのときと同様。

66 (証明つづき)φ∈P の場合 性質P の補集合P について先ほどと同じ議論をすればP が決定不能であることがわかる。 ところで LP : P に属す言語を受理するTM(の符号)の集合 LP : P に属す言語を受理しないTMの集合 すべてのTMは何かを受理するのでこれらは等しい。 するともしLP が決定可能であるとするとLP = LP も決定可能となり上( P が決定不能)と矛盾 (証明おわり)

67 Postの対応問題 いままでTMの受理言語に関する決定不能性をみてきた。 TMとは関係ない普通の問題にも決定不能な問題が存在する。
 (Post’s Correspondence Problem, PCP)はこのような決定不能問題の例。

68 Postの対応問題の実例 S上の記号列の同じ長さの二つのリストを A, Bとする。 A=w1, w2, …, wk
B=x1, x2, …, xk とする。 このとき1個以上の数の並びi1, …, imが存在して wi1wi2…wim = xi1xi2…xim となるか? (Yes/No)   ←というのが実例 注: 入力(A, B)に対して上を問うのがPCP

69 例 w2w1w1w3 = x2x1x1x3 = 101111110 (2,1,1,3)をこの実例の解という。 A B i wi xi 1
w2w1w1w3 = x2x1x1x3 = (2,1,1,3)をこの実例の解という。

70 解を持たない実例 A B i wi xi 1 10 101 2 011 11 3

71 i1 wi1 xi1 1 10 101 2 011 11 3 i2 wi2 1xi2 1 10 1101 2 011 111 3 101 1011 i3 wi3 1xi3 1 2 3 i1, …, ikは部分解

72 PCPの決定不能性 Luを変形PCP(MPCP)に還元し, MPCPをPCPに還元する。
Luは決定不能であったから、MPCPもPCPも決定不能である。 Mu MPCP yes (M,w) PCP 還元ψ 還元φ no

73 変形PCP Luを直接PCPに還元するよりも次の変形PCP (MPCP)を経由したほうが容易である。 変形PCP(の実例):
二つの語のリストA=w1, w2, …, wk B=x1, x2, …, xk に対して0個以上の数の並びi1, …, imが存在して w1wi1wi2…wim = x1xi1xi2…xim となるか否か? 注: PCPと異なる点 先頭は1    解は(先頭以外の)0個以上の並びi1, …, im

74 MPCPをPCPに還元する MPCPの実例 A=w1, w2, …, wk B=x1, x2, …, xk をPCPの実例
C=y0, y1, y2, …, yk+1 D=z0, z1, z2, …, zk+1 に還元する。ここで 1≦i≦kで wi=a1a2…anならばyi= a1*a2*…*an* xi= b1b2…bmならばzi= *b1*b2*…*bm y0= *y1 , z0= z1 yk+1= $, zk+1 =*$ である。

75 MPCPの実例を還元 MPCPの実例(左)をPCPの実例(右)に還元 A B i wi xi 1 111 2 10111 10 3 C D
C D i yi zi *1* *1*1*1 1 1* 2 1*0*1*1*1* *1*0 3 1*0* *0 4 $ *$ *, $ ∈ S

76 還元の条件を満たすこと [証明] i1, …, im をMPCPの解とする。
すなわち、w1wi1wi2…wim = x1xi1xi2…xim このとき *y1yi1yi2…yim = z1zi1zi2…zim* y0= *y1 , z0= z1であったから y0yi1yi2…yim = z0zi1zi2…zim* 末尾に$をつけると yk+1= $, zk+1 =*$であったから y0yi1yi2…yimyk+1 = z0zi1zi2…zizk+1 ゆえにi0,i1, …, im,ik+1 はPCPの解 (逆) 示せ

77 LuをMPCPに還元する TM M = (Q, Σ, Γ, δ, q0 , B, F)と入力語wに対して次のMPCPを構成する。
(以下でM は空白を書かず、初期ヘッド位置より左には移動しないと仮定する。一般のMからこのようなMへの還元は容易) 最初の対 (コピー用) A B i wi xi 1 # #q0w# A B X # X∈G

78 (遷移用)q∈Q-F (記号消去用)q∈F (一致用)q∈F A B qX Yp d(q,X)=(p,Y,R) ZqX pZY
d(q,X)=(p,Y,L) Z∈G q# Yp# d(q,B)=(p,Y,R) Zq# pZY# d(q,B)=(p,Y,L) Z∈G (一致用)q∈F A B XqY q Xq qY A B q## #

79 還元への入力例 w=10 B/0R M 0/1R 1/0L B/1L q2 q1 開始 0/0L 1/0R q3

80 還元された結果 規則 A B 1 # #q101# 2 3 q10 1q2 d(q1,0)=(q2,1,R) 0q11 q200
3 q10 1q2 d(q1,0)=(q2,1,R) 0q11 q200 d(q1,1)=(q2,0,L) 1q11 q210    同上 0q1# q201# d(q1,B)=(q2,1,L) 1q1# q211# 0q20 q300 d(q2,0)=(q3,0,L) 1q20 q310 q21 0q1 d(q2,1)=(q1,0,R) q2# 0q2# d(q2,B)=(q2,0,R) 還元された結果 規則 A B 4 0q30 q3 0q31 1q30 1q31 0q3 1q3 q30 q31 5 q3## #

81 TMの模倣 A, Bの欄にそれぞれw1,x1を書く。これは部分解。 次を繰り返す。 A # B #q101#
A, B欄が一致するwi,xiをそれぞれA, B欄の末尾に追加して終わる。 なければ部分解を延長するwi,xiをそれぞれA, B欄の末尾に追加する。

82 受理する場合 A …# B …#0…01q300…0# 0…0 1q30 0…0 # 0…0 q3 0…0 # …# …#q3# q3##

83 還元条件を満たすこと 受理されるとき、またそのときに限りMPCPは解を持つことがわかる。 (受理状態でない限り、AはBに追いつかない。
受理状態なら前ページのように解を持つ。)

84 文法に関する決定問題 文脈自由文法(CFG)があいまいか否かは決定不能 「文法があいまい」: 直観的な説明
その文法が定義する言語が、2種類(以上)の構成方法をもつ文を含む。

85 文脈自由文法(教科書上巻5章参照) 文脈自由文法(context free grammar, CFG)Gは 4つ組< V,T,P,S>で規定されるここで、 Vは変数(あるいは非終端記号)の集合: 変数は記号列の集合に対応する。(後述) Tは終端記号の集合 定義される言語に現れる記号の集合 S∈Vは開始記号 Pは生成規則の集合 生成規則は変数A∈Vと記号(∈V∪T)の列X1X1…Xnの組でA→X1X1…Xn のように書く。 通例文法といえば文脈自由文法を指す。

86 文法の例 G=<{P}, {0,1}, A, P> Aの要素は次の5つ P e 1 0P0 1P1

87 文法が生成する言語 文法G=< V,T,P,S>において
記号列aに現れる非終端記号A(∈V)1つをある規則A→X1X1…Xnを用いてX1X1…Xnに置き換えてbを得る操作を導出とよびa ⇒bと書く。 aから始めて、導出を繰り返してbが得られるとき a ⇒*bと書く。(0回含む) Sから始めて導出を繰り返して得られる終端記号の列w全体の集合を文法Gが生成する言語といい、L(G)で表す。すなわち L(G)={w∈T*|S ⇒*w} 必ずしも終端記号だけではない記号の列aについてS⇒*a のとき、aを文形式という。

88 文法が生成する言語の例 前述の文法G=<{P}, {0,1}, A, P>で
P⇒0P0⇒01P10⇒010P010⇒ により ∈L(G) L(G)は{0,1}上の回文全体

89 文法の略記法 規則の左辺(→記号の左側)が同じ規則が複数ある場合、たとえば、giを記号列として A → g1 A → g2 … A → gn
 … A → gn がある場合これらをまとめて A → g1 | g2 | … | gn のように書く。 問 回文の文法を上の略記法で書け。

90 最左(右)導出 導出の各書き換えステップで一番左(右)の非終端記号の書き換えのみをおこなう導出を最左(右)導出という。
最左導出でa1からのa2の導出ができるとき a1 ⇒*lm a2 などとかく。 S ⇒* lm aなるaを左文形式という。aは非終端記号を含んでもよい。

91 最左導出の例 1桁の数 0, 1と2種類の変数x, yのみの和および積でつくる式全体は次の文法で生成される。
E → I | E+E| E*E | (E) I → x | y | 0 | 1 E ⇒lm E+E⇒lm E*E+E ⇒lm I*E+E ⇒lm x*E+E ⇒lm x*I+E ⇒lm x*y+E ⇒lm x*y+I ⇒lm x*y+1

92 構文木 導出を、どの非終端記号を書き換えるかの順序を捨象して木であらわしたものを構文木という。
構文木の各節点は非終端記号、葉は終端記号または非終端記号、根は開始記号。 各節点の子の並びはその節の非終端記号の書き換えにもちいた生成規則の右辺。 E E E E E I * I I + 1 x y

93 曖昧さ 2つ以上の構文木をもつ文を生成する文法は曖昧であるという。 注 文が構文木を2つ持つことは最左(右)導出が2つあることと同じ。
注 文が構文木を2つ持つことは最左(右)導出が2つあることと同じ。 問 前述の式の文法でx*y+1の構文木をもう1つ作れ。

94 CFGの曖昧さに関する決定不能性(1) PCPをCFGの曖昧性問題に還元する。 PCPの実例で与えられるリストを
A=w1, w2, …, wk B=x1, x2, …, xk とする。これらの語に使われるアルファベットをSとする。アルファベットSとは別に添え字記号の集合    L={a1, a2, …, ak}を用意する。 文法GA=<{A}, S∪L, P, A> P: A→w1Aa1 | w2Aa2 | … | wkAak | w1a1 | w2a2 | … | wkak GAが生成する言語をLA書き、リストAの言語と呼ぶ。 LAの要素の一般形はwi1wi2…winain…ai2ai1 添え字記号列に対して導出の列がただ1つ決まるので、GAは曖昧でない。

95 CFGの曖昧さに関する決定不能性(2) GAと同様に GB=<{B}, S∪L, Q, B>
Q: B→x1Ba1 | x2Ba2 | … | xkBak | x1a1 | x2a2 | … | xkak GBが生成する言語をLB 次にこれらの文法を組み合わせた文法GAB を次のように定義する。 GAB=<{A, B,S}, S∪L, P∪Q∪{S→A | B}, S> このとき次が成り立つ。 PCPの実例(A, B)が解をもつ⇔GABが曖昧 すなわちPCPが文法の曖昧性問題に還元される。

96 CFGの曖昧さに関する決定不能性(3) (十分性)i1, …, imがPCPの解であるとする。このとき
S⇒A⇒wi1Aai1⇒wi1wi2Aai2ai1⇒…⇒wi1…wimai1…aim S⇒B⇒xi1Bai1⇒xi1xi2Bai2ai1⇒…⇒xi1…ximai1…aim wi1…wim=xi1…ximにより、上は同じ語の導出。 これらは最左導出であるからGABは曖昧。 (必要性)GAおよびGBは曖昧ではないので、 GABがある語の2つの導出を持つならば、それらは S⇒A⇒wiAai⇒…⇒ga  (g∈S*, a∈L*) S⇒B⇒xjBaj⇒…⇒cb  (c∈S*, b∈L*) S∩L=Φだからa=b, g=c そこでa=aim…ai1(=b)とするとg=wi1…wim, c=xi1…xim すなわち i1, …, imはPCPの解。   (証明終わり)

97 PDA Pushdown Automaton(PDA) P=<Q,S,G,d,q0,Z0,F>: Q: 状態の集合
d : Q×S∪{e}×G→2Q×G*  遷移関数 (p, g)∈d(q, a, X)の意味 状態はpに遷移し、スタックの上端の記号Xをgに置き換えてよい。g=YZならZがYの下。 q0: 開始状態∈Q Z0: 開始記号(底記号) F: 受理状態の集合⊆Q

98 PDAとCFGは等価 定理 任意のPDAはCFGを受理する。 逆に任意のCFGはPDAに受理される。 証明 (教科書上巻 p.265~参照)

99 リスト言語の補集合 定理 リストAの言語LAの補集合はCFL (証明)LAの補集合を受理するPDA Pの動作を次のように定義する。
Sを読んでいる間はそれをpush Lを読んだらaiとwiの照合を開始。(テープからaiを読んだらpopしてwiRか否かをチェック) 否なら受理状態に入り以後そのまま進む 是で次が底記号でなければ受理状態に入り2を繰り返す。 是で次が底記号ならいったん非受理状態に入り、さらに入力があれば受理状態に遷移する。 2の後にSを読んだら受理状態のまま進む。

100 CFLに関する決定不能性(1) 定理 G1, G2をCFG, Rを正則表現とするとき、 L(G1)∩L(G2)=φか。
L(G1)=L(R)か。 あるアルファベットTに対してL(G1)=T*か。 L(G1)⊆L(G2)か。 L(R)=L(G2)か。

101 CFLに関する決定不能性(2) (証明) 還元: L(G1)=LA, L(G2)=LBとする。       還元の条件: PCP(A, B)が解を持つ⇔LA∩LB≠φ⇔L(G1)∩L(G2)≠φ 還元: L(G1)=LAC∪LBC, L(G2)=(S∪L)*とする。還元の条件:PCP(A, B)が解を持つ⇔LA∩LB≠φ⇔(S∪L)*ー(LA∩LB)C ≠φ ⇔(S∪L)*ー(LAC∪LBC) ≠φ         ⇔L(G1)≠L(G2) 残り (示せ)

102 実行可能性 入力のサイズに関する多項式で表される程度の時間で停止するTMで解けるか?
決定可能性における諸概念を下記のように置き換えることで実行可能性の議論を進める。 決定可能性 「実行可能性」 TM 停止 多項式時間で停止 論法 還元 多項式時間還元 出発点 Lu SAT 伝わる性質 決定不能性 NP完全性

103 時間計算量 入力wに対するTM Mの計算時間とは停止するまでのステップ数。(停止しないとき無限大)
TM Mは長さnの任意の語に対する計算時間が高々T(n)であるとき、Mの時間計算量(time complexity)はT(n)であるという。

104 多項式時間で解ける問題 重みつきグラフに対して、重みの和が最小となる極大木(minimum-weight spanning tree, MWST)を求めよ。 12 1 2 15 10 20 3 4 18

105 Kruskalのアルゴリズム はじめは各頂点にべつべつの連結成分が割り当てられる。 まだ取り上げていない辺に対して、
両端が異なる連結成分に属すとき、ふたつの連結成分を合併する。(片方に属する頂点に割り当てた連結成分をもう片方のものに書き換える。) 両端が同じ連結成分に属すとき、なにもしない。 処理済の辺が頂点の数より1つ少ないか、すべての辺を処理すれば終わり。

106 アルゴリズムの適用例 12 1 2 2 15 10 20 3 3 4 4 18

107 MWSTの時間計算量 各端点にははじめ別々の連結成分が割り当てられているものとする。 各辺eについて次を繰り返す(O(e))
選んだ辺の両端点が属する連結成分を見つける。(O(m)) 両端点の連結成分が異なるとき、一方の連結成分に属すノードについて所属する連結成分をもう一方の連結成分に書き換える。(O(m)) 以上を合わせるとO(e(e+m))

108 MWSTと決定問題 MWSTは木を答えとして要求するが決定問題に対するTMはyes/noしか返さない。 MWSTを改変して決定問題にする。
限界量Wを定め、答えの木の重みがW以下であるときyes、W以上であるときnoとする。 上の決定問題は元のMWSTよりもやさしい。 実行可能性の理論の主張の多くは、ある問題が「難しいこと」を示すものなので、上のような改変の結果やさしくなったものがなおも難しいことを示せば十分。

109 MWSTの符号化の例 記号: 0,1,(,),コンマ 各頂点に整数1~mを割り当てる。
記号: 0,1,(,),コンマ 各頂点に整数1~mを割り当てる。 コードの先頭にmと重み制限Wの2進数表示をコンマで分けて書く。 頂点i,jを結ぶ重みwの辺(いずれも2進数表示)を(i,j,w)と書く。 問題 前述のグラフ(再掲→) のコードを求めよ。 1 2 15 12 10 20 3 4 18

110 クラスP 決定性TMで多項式時間で解ける問題のクラスをP(polinomial)と書く。 (より形式的には、) 言語LがPに属すとは、
Lを受理する決定性TM Mと多項式T(n)が存在して、Mは長さnの任意の入力に対して高々T(n)ステップで停止することをいう。 問題PはPに属すとき、実行可能であるといい、そうでないとき実行不能であるという。

111 NP 非決定性TMで多項式時間で解ける問題のクラスをNP (nondeterministic polynomial)と書く。
(より形式的には、) 言語LがNPに属すとは、 Lを受理する非決定性TM Mと多項式T(n)が存在して、Mは長さnの任意の入力に対して動作系列の長さがT(n)を越えないことをいう。 クラスNPは明らかにクラスPを含むが、Pに含まれないNPの要素が存在するか否か、すなわち、P≠NPか否か、は未解決。

112 非決定性多項式時間で解ける問題 巡回セールスマン問題(traveling salesman problem, TSP)
重みつきのグラフについて、 重みの和がW以下のハミルトン閉路が存在するか? 12 1 2 15 10 20 3 4 18

113 TSPの計算量 頂点がm個とするとき、 決定性 非決定性
すべての順列(m!)にわたって検査する以外になさそう。(任意の定数cについて、m!>2cm) 非決定性 非決定性多テープTMを用いると、順列をO(m2)で推測することができる。限界値の検査も同程度。1テープで模倣するとO(m4)

114 多項式還元 P2がPに属さないこと(実行不能性)をいうには、
P2を受理するTM M2を仮定すれば、多項式時間では解けないはずの問題P1(の実例)をP2に多項式時間で変換(多項式時間還元)することでP1を多項式時間で解くTM M1が構成できること(矛盾)を示せばよい。 受理 M2 P2 受理 多項式時間 変換機 ψ P1 拒否 拒否 M1

115 NP完全問題 言語(問題)Lは次を満たすときNP完全(NP-complete)であるという。 LはNPに属す。
NPに属す任意のL’に対しL’からLへの多項式時間還元が存在する。 2を満たす場合NP困難(NP-hard)という。 注意:P≠NPは未解決なのでNP完全であることが必ずしも実行不能である(多項式時間で解けない)ことを意味しないが、仮説として実行不能であるとする文脈も。

116 NP完全問題の性質 定理 もしNP完全問題がどれか1つでもPに属すことがわかったら、P=NP NPに属す すべての問題 NP完全問題 ….
多項式時間還元

117 多項式時間還元は推移的 定理 P1はNPに属すとする。P1がNP完全でP1からP2への多項式時間還元が存在するとき、P2もNP完全である。
(証明)任意の言語Lについて多項式時間還元ψ:L→P1が存在して長さnの語wをψ(w)に変換する。ψの時間計算量をp(n)とすると|ψ(w)|<p(n)。 P1からP2への多項式時間還元φの時間計算量をq(m)とすると、ψ(w)を変換するのに要する時間はq(|ψ(w)|)<q(p(n))。したがってψとφの合成の計算量はp(n)+q(p(n)) ψ φ L P1 P2 p(n) q(m)

118 NP完全問題の役割 NP完全問題が1つみつかれば、それからほかの問題への多項式時間還元をみつけることでそれらの問題のNP完全性がいえる。
(決定不能性におけるLuの役割と同じ) TSP SAT …. …. いろいろな問題 多項式時間還元

119 ブール式と充足可能性 ブール式(boolean expression)は次のものからなる 例 x∧¬(y∨z)はブール式
変数。変数の値は0(false)と1(true) 2項演算∧と∨。それぞれ論理積と論理和。 1項演算¬。否定。 括弧(、)。 例 x∧¬(y∨z)はブール式 ブール式に対する真理値割り当て(truth assignment)とはEの各変数に値を割り当てること。割り当てTのもとでの式Eの値をE(T)と書く。 真理値割り当てTが充足ブール式Eを充足するとは、E(T)=1となること。 ブール式Eを充足する真理値割り当てが存在するとき、Eは充足可能であるという。

120 充足可能性問題(SAT) 充足可能性問題(satisfiability problem, SAT)とは、
与えられたブール式に関して充足可能か否かを判定する問題 SATの入力例の表現: 充足可能性は変数の名前にはよらないので、まずx1, x2, …, xnに置き換える。 xiを(有限個の記号で表現するため)xj(i)とする。 ここでj(i)はiの2進数表示。変数以外はそのまま。 例 x∧¬(y∨z)の入力符号はx1∧¬(x10∨x11)

121 SATのNP完全性(1) (Cookの定理)SATはNP完全 [証明]NPに属すこと
(1)NTMで真理値割り当てTを推測。Eの長さをnとしてO(n)で可能。 (2)Tに対してブール式Eを評価し、E(T)=1なら受理。多テープNTMでO(n2)(式用テープ、真理値割り当て用テープ)

122 SATのNP完全性(2) 任意のL∈NPに対してLからSATへの多項式時間還元が存在すること。
1テープNTM MでL(M)=Lであって多項式p(n)の時間で必ず停止するが存在する。 すると、Mが長さnの入力wを受理するとき次の条件を満たす動作列a0⇒…⇒akが存在。 a0はwに対する初期ID k≦p(n) akは受理状態を持つID 各aiは末尾を除き空白以外の列。

123 SATのNP完全性(3) wに対するMの受理動作列が存在することをブール式EM,wの充足可能性で表現する。
(還元の条件:wが受理される⇔Eが充足可能) 各IDaiを記号の列Xi0Xi1…Xi,p(n)であらわす。どれかは状態。 テープ記号または状態Aに対して、Xij=Aをあらわす変数をyijAとする。Xij=A⇔yijA=1 動作列がwの受理を表すことをyijAのブール式で表現すればよい。

124 SATのNP完全性(4) wの受理であるためには、 0. 記号は場所あたり1つ。 はじめがq0w 遷移がd に従う 受理状態に到達する
0. 記号は場所あたり1つ。 はじめがq0w 遷移がd に従う 受理状態に到達する 以下これらをブール式で表現する。

125 SATのNP完全性(5) ブール式で表しやすいようにaiに便宜上の調整(変更)を施す。
末尾の空白部分をIDの長さp(n)+1まで含める。(すべてのIDの長さを同じに。) p(n)回目以前の動作で受理状態に到達したらそのままp(n)回目までその受理状態のまま動作を続ける。(常にp(n)回動作。)

126 SATのNP完全性(6) ID 1 … p(n) a0 X00 X01 X0,p(n) a1 X10 X11 X1,p(n) ai
1 p(n) a0 X00 X01 X0,p(n) a1 X10 X11 X1,p(n) ai Xi,j-1 Xi,j Xi,j+1 ai+1 Xi+1,j-1 Xi+1,j Xi+1,j+1 ap(n) Xp(n),0 Xp(n),1 Xp(n),p(n)

127 SATのNP完全性(7) S=y00q0∧y01a1∧y02a2∧…∧y0nan
0. 記号は場所あたり1つ U=∧ij[∨A yijA ∧¬(∨A≠C(yijA∧yijC))] はじめがq0w S=y00q0∧y01a1∧y02a2∧…∧y0nan ∧y0,n+1,B∧y0,n+2,B∧…∧y0,p(n),B

128 SATのNP完全性(8) 遷移がd に従う。 Ni :ID ai の次にID ai+1がこれる。 fij(W,X,Y,Z)=1
⇔Xi,j-1=W, Xi,j=X, Xi,j+1=Y, Xi+1,j=Z となりうる。 Ni=∧j(∨f(W,X,Y,Z)=1 yi,j-1W∧yijX∧yi,j+1Y∧yi+1,j,Z) N=∧iNi

129 SATのNP完全性(9) 受理状態に到達する。 Xp(n), j (j=1,…,p(n)) のいずれかが受理状態であればよい。
Fj: Xp(n), j が受理状態∈{a0,…,ak}=受理状態集合 Fj=yp(n), j, a0∨…∨yp(n), j, ak F=F1∨…∨Fp(n)

130 SATのNP完全性(10) 以上をまとめて、 EM,w=U∧S∧N∧F 多テープ決定性TMでO(n2) (証明終わり)

131 制限された形の充足可能性問題 CSAT : 乗法標準形、CNF 3SAT : 3-乗法標準形(項の長さ3) kSAT : k-乗法標準形
いずれもNP完全

132 乗法標準形 変数または否定を施した変数をリテラル(literal)という。
1つのリテラルまたは2つ以上のリテラルをORで結んだものを項(clause)という。 乗法標準形(CNF, conjunctive normal form, 和積標準形とも)であるとは、項をANDで結んだ形をしていることをいう。(項が1つだけの場合も。) k-乗法標準形(k-CNF)は項がちょうどk個のリテラル。 以下∨を和(+)、∧を積として書く場合もある。(短縮形) 結合は(論理)積のほうが強い。

133 乗法標準形の例 (x∨¬y)∧(¬x∨z)∧(¬z∨y)を短縮形で書くと、 (x+¬y)(¬x+z)(¬z+y) 2-CNF
xyzは1-CNF

134 ブール式のCNFへの変換 論理式としての同値性を保存したままの変換では多項式時間を越える場合も。
充足可能性は同値性よりも弱い!(充足可能性を保存するだけなら多項式時間で可能)

135 SATからCNFへの還元 次の2ステップからなる。 ¬を変数につくものだけにする。 リテラルの積の和をCNFに変換(あとで)
¬(E∧F) ⇒ ¬(E)∨¬(F) ¬(E∨F) ⇒ ¬(E)∧¬(F) ¬(¬(E)) ⇒ E リテラルの積の和をCNFに変換(あとで)

136 第1ステップの計算量 与えられるブール式Eに含まれる演算子の個数nに関する帰納法で次を示す。
得られるブール式Fに含まれる演算子の個数は2n-1を超えない

137 これらの演算子数は2a+2b-1<2(a+b+1)-1
基礎:演算子が1つのとき。 ¬x, x∧y, x∨yはいずれもそのままでOK。2n-1=1 帰納:演算子の個数n-1以下のブール式については成り立つと仮定する。E=E1∨E2またはE=E1∧E2の場合(一番外側の演算子が¬でないとき)、E1,E2の演算子数がa,bとし、E1がF1, E2がF2に変換されるとすると、それぞれF1∨F2または(F1)∧(F2)とする。 これらの演算子数は2a+2b-1<2(a+b+1)-1

138 E=¬E1 E1=¬E2のときE=¬(¬E2)=E2 E1=E2∨E3のときE=¬(E2∨E3)=¬(E2)∧¬(E3)。ここで¬(E2)、¬(E3)に含まれる演算子数はEの演算子数よりも少ないので、それぞれリテラルだけに¬がつくブール式F2、F3に変換できる。このとき、F2∧F3とすればよい。E2, E3に含まれる変数の数をそれぞれa,bとすると、Fに含まれる変数の数は2(a+1)-1+2(b+1)-1+1=2(a+b+2)-1 E1=E2∧E3のとき、2と同様。

139 第2ステップ Eは(1ステップで得られた)変数以外には¬がつかないブール式であるとする。Eの長さに関する帰納法で次を示す。
ある定数cが存在して、長さnの任意のEに対して、次のFが存在する。 FはCNF FはEから高々c|E|2で構成できる。 Eに対する真理値割り当てTがEを真にするための必要十分条件はTの拡張SでFを真にするものが存在することである。 3により還元で充足可能性が保存されることを確かめよ。

140 真理値割り当ての拡張 Eの変数の集合をV,TをEの真理値割り当てとする。
S:W→{0,1}がTの拡張(extension)であるとは、V⊆Wであって、 S(v)=T(v) (v∈V) を満たすことをいう。 (同じことをTはSの制限であるといい、S|V=Tと書く。) Eの変数の集合をVar(E)と書くと、Var(E)⊆Var(F)のときFの真理値割り当てSのVar(E)への制限S|Var(E)のことを我々は簡単にS|Eと書く。

141 CNFの構成 基礎: Eがリテラル → F=E 帰納: E1, E2はそれぞれ F1=g1∧g2∧…∧gp F2=h1∧h2∧…∧hq
に変換されるとする(帰納法の仮定)。ただし、F1,F2に現れる変数はEに表れるものを除いて異なるものとする。このとき E=E1∧E2 ⇒ F=F1∧F2 E=E1∨E2 ⇒ F=(y+g1)(y+g2)…(y+gp) ∧(¬y+h1)(¬y+h2)…(¬y+hq)

142 第2ステップの3の証明(1/3) TがEを充足⇔Fを充足するS(Tの拡張)が存在 を|E|に関する帰納法で示す。
基礎:|E|,=1または2のとき。F=Eであるから明らか。 帰納: 場合1: E=E1∧E2 (⇒)TがEを充足すると仮定する。T1=T|E1,T2=T|E2とする。T1はE1、T2はE2を充足する。帰納法の仮定から、T1の拡張S1でF1を充足するもの、T2の拡張S2でF2を充足するものが存在する。S1∪S2(S1とS2それぞれの定義域の和集合上で定義され、S1の定義域上でS1と、S2の定義域上でS2と一致する関数。定義からF1とF2が共通に持つ変数はEのものに限るので定義域が重なる部分ではTに一致する。)をFの真理値割り当てSとする。SはF1とF2を充足するのでF=F1∧F2を充足する。 (<=)Tの拡張SがFを充足すると仮定する。S1=S|F1,S2=S|F2とする。 F=F1∧F2であるからS1はF1を、S2はF2を充足する。S1はT1の拡張でありS2はT2の拡張ゆえ、帰納法の仮定により、T1はE1、T2はE2を充足する。よってTはEを充足する。

143 第2ステップの3の証明(2/3) 場合2: E=E1∨E2
(⇒)TがEを充足すると仮定する。TはE1を充足するか、またはE2を充足する。E1を充足する場合、帰納法の仮定からT1の拡張S1でF1を充足するものが存在する。Tの拡張Sを次のように構成する。 x∈Var(F1)に対してS(x)=S1(x) (これによりF1=1) S(y)=0 x∈Var(F1)-Var(F2)に対しては1でも0でもよい。 F=(0+g1)(0+g2)…(0+gp)(1+h1)(1+h2)…(1+hq) =g1∧g2∧…∧gp=F1=1 ゆえにSはFを充足する。E2を充足する場合も同様。(S(y)=1)

144 第2ステップの3の証明(3/3) (<=)Tの拡張SがFを充足すると仮定する。 S(y)=0または1である。
S(y)=0の場合はF=g1∧g2∧…∧gp=F1ゆえSはF1を充足する。S1=S|F1と書くと、S1はF1を充足する。したがって帰納法の仮定によりT1=T|E1はE1を充足する。 E=E1∨E2であるからTはEを充足する。 S(y)=1の場合も同様。 (3の証明おわり)

145 第2ステップの2の証明 場合1および2のいずれにおいても、EからE1, E2をつくる手間とF1, F2からFをつくる手間は線型の時間。長さnのEからFを構成するのに要する時間T(n)は次の漸化式に従う。 T(1)=T(2)≦e   e:定数 T(n)≦dn + max(T(i) + T(n-i-1)) T(i)はE1からF1, T(n-i-1)はE2からF2 帰納法で∃c∀n.T(n)≦cn2を示す。 基礎:n=1,2のときc≧eのようにcを選ぶ。 帰納:n≧3のとき,帰納法の仮定から T(i)≦ci2,T(n-i-1)≦c(n-i-1)2ゆえ、 T(i)+T(n-i-1)≦c(n2-2i(n-i)-2(n-i)+1) n≧3, 0<i<nから、2i(n-i)>n, 2(n-i)>2となる。 このとき、 T(i)+T(n-i-1)≦c(n2-n-2+1)<c(n2-n) T(n)≦dn + c(n2-n)=cn2+(d-c)n d≦cのようにcをえらべばT(n)≦cn2となる。(証明おわり)

146 3SATはNP完全 [証明]SATがNPに属すゆえ3SATもNPに属す。 CSATから3SATへの還元を次で定義する。
CSATの式E=e1∧e2∧…∧ekが与えられたとき、 各eiに対して下で定義する置き換えを行うことでFを構成する。各々の場合について、Eに対する真理値割り当てがEを充足するための必要十分条件がその割り当ての拡張でFを充足するものが存在することであることを示す。 eiが一つのリテラルのとき。たとえば(x)の場合。二つの変数u,vを導入して、(x+u+v)(x+u+¬v)(x+¬u+v)(x+¬u+¬v)に置き換える。 これを充足するにはxが真であることが必要十分。 したがって、Eを充足する真理値割り当てはFを充足する拡張を持つ。また逆も成り立つ。

147 3SATのNP完全性の証明(つづき) eiが二つのリテラルのとき。たとえば(x+y)の場合。一つの変数zを導入して、(x+y+z)(x+y+¬z)で置き換える。これを充足するにはx+yが真であることが必要十分。 eiが三つのリテラルのとき。すでに3-CNFなのでそのまま。 m≧4に対して、ei=(x1+x2+…+xm)のとき、y1,y2,…, ym-3を導入して、(x1+x2+y1)(x3+¬y1+y2)(x4+¬y2+y3)… …(xm-2+¬ym-4+ym-3)(xm-1+xm+¬ym-3) で置き換える。Eを充足する真理値割り当てTがxjを充足するとする。このとき、y1,y2,…, yj-1をすべて真、yj,yj+1,…, ym-3をすべて偽にすれば、置き換えた項は充足される。Tがすべてのxiを偽にするとき、置き換えた項は充足できない。 変換に要する時間は明らかに線型。(証明おわり)

148 3SATから判るNP完全問題 独立集合問題(IS) 頂点被覆問題(NC) 有向ハミルトン閉路問題(DHC)
巡回セールスマン問題(TSP)

149 独立集合問題(IS) 定義: 無向グラフGの頂点集合の部分集合IはIに属すどの2点もGの辺で結ばれないとき独立集合という
問題:与えられた無向グラフGがサイズkの独立集合を持つか? 還元のもとになる問題:3SAT

150 3SATをISに還元 E = e1∧e2∧…∧em を3-CNFとし、ei=(ai1+ai2+ai3)とする。 これを下図のような無向グラフGに還元する。 図で列は項に、列中の頂点はリテラルに対応する。 列中の頂点はすべて互いにつなぎ、同じ変数からなるリテラルで正と負のものはつなぐ。(m2程度で可) [j,1] [m,1] [1,1] [i,1] aj1=¬xp [m,2] [1,2] [i,2] ai2=xp [m,3] [1,3] [i,3]

151 Gが頂点数mの独立集合をもつ ⇒Eが充足可能
IをGの独立集合としその頂点数がmであるとする。 Eに対する真理値割り当てTを次のように定める。 T(x)=1 ([i,j]∈I, aij=x) T(x)=0 ([i,j]∈I, aij=¬x) T(x)=なんでも ([i,j]∈I) このとき、Iの要素は各列に高々1個(同じ列の頂点はつながっているから。)したがってm個を選ぶにはすべての列に少なくとも1個なければならない。 Tは矛盾することはない。(aij=x かつakl=¬x ならば辺([i,j],[k,l])により、[i,j]と[k,l]の両方がIに属すことはない。)

152 Eが充足可能 ⇒Gが頂点数mの独立集合をもつ
Eを充足する真理値割り当てをTとする。Eの各項からTで真になるリテラルを1つずつ選び、それらに対応するm頂点を集めたものをIとする。 Iは独立集合。辺([i,j],[k,l])が存在すると仮定する。[i,j],[k,l]に対応するリテラルはx,¬x(順不同)。真になるリテラルだけを集めたことに反する。

153 頂点被覆問題(NC) 定義: 無向グラフGの頂点の集合で任意の辺の端点の少なくとも1つを含むものを頂点被覆という
問題:与えられた無向グラフGがサイズkの頂点被覆を持つか? 還元のもとになる問題:IS

154 独立集合と頂点被覆 グラフG=(N,E)の頂点集合の部分集合をIとする。Iの補集合N-IをCとする。このとき、 Iが独立集合⇔C頂点被覆
示せ

155 有向ハミルトン閉路問題(DHC) 問題: 有向グラフGのすべての頂点をただ一回だけ通る閉路が存在するか? 還元のもとになる問題: 3SAT

156 3SATをDHCに還元 F = e1∧e2∧…∧ek を3-CNFとする。
ej = (aj1+aj2+aj3) (j=1,…,k) ajlはリテラル  xi (i=1,…,n) Fに出現する変数

157 … … xi (i=1,…,n) に対して、 H1 ai bi0 ci0 H2 Hi bi1 ci1 Hi Hn bimi cimi di
miはxiの個数(出現回数)と¬xiの個数の多い方

158 ej (j=1,…,k) に対して、グラフIjを構成
rj sj tj Ij uj vj wj Ij

159 … … ej = (aj1+aj2+aj3) aj1が負 aj1が正 bik cik bip cip cik+1 bip+1 rj sj
tj rj sj tj uj vj wj uj vj wj

160 … … Hg ej = (aj1+aj2+aj3) aj1= ¬xi aj2= ¬xg aj3= xh Hh rj sj tj uj vj
変数の添字がiならHiに接続 ej = (aj1+aj2+aj3) aj1= ¬xi aj2= ¬xg aj3= xh Hh rj sj tj uj vj wj Hi

161 Hg I1 Hh すべてのIjを接続 Ij G Ik Hi

162 … … … F 充足可能⇒閉路存在 H1 ai ai bi0 ci0 bi0 ci0 H2 bi1 ci1 bi1 ci1 bimi
cimi bimi cimi Hn di di

163 Ijの性質 rjに入る道は6つの頂点を1回ずつ通ってujから出る。sj,tjも同様。 rj sj tj Ij uj vj wj

164 … F 充足可能⇒閉路存在 bip cip bip+1 rj sj tj uj vj wj すべてのjについて
aj1,aj2,aj3のいずれかは真。変数への真理値割り当てが1でリテラルが正であるか真理値割り当てが0で負のリテラルである。これは真になるリテラルの変数をxiとすると、Hiが赤でIjとの結合も赤であるか、Hiが青でIjとの結合も青であることを意味する。 このとき、辺cip→bip+1のかわりにcipからrjに行き、ujからbip+1にもどる道を通ってよい。 bip cip bip+1 rj sj tj uj vj wj

165 H1 I1 H2 Ij Ik Hn 接続先は同じ色

166 閉路存在⇒F 充足可能 ハミルトン閉路が存在すると仮定する。 Ij のすべての頂点を訪れることから
ci → rj → bi+1  または  bi → rj → ci+1 が存在。 ci → rj → bi+1 の場合 ciから出るためには bi → ci (そうでないとbiが到達不能)ゆえに Hpは赤すなわち、 ∀i. bi → ci いま T(xp)=1とする。まず、ci → rj としたのはaj1=xpが正のリテラルであったからであった. よってaj1=1 すなわちei=1 すべてのIj について同じことが言える。よって F=e1∧...∧ep=1

167 無向ハミルトン閉路問題(HC) 問題: 無向グラフGのすべての頂点をただ一回だけ通る閉路が存在するか? 還元のもとになる問題: DHC

168 DHCをHCに還元 有向グラフGdを無向グラフGuに変換する。 Gdに閉路があればGuに閉路があることは自明。
一方を選んで20の辺を有向辺とすればよい。 v(0) w(0) v w v(1) w(1) v(2) w(2)

169 巡回セールスマン問題(TSP) 問題: 辺に整数の重みをもつ無向グラフGが重みの和がk以下であるようなハミルトン閉路を持つか?
還元の元になる問題: HC 証明: (容易)

170 取り上げなかった話題 領域計算量 (11章) 帰納関数論 λ計算 渡辺治,米崎直樹 「計算論入門―計算の基本原理理解のために」(日本評論社)
領域計算量 (11章) 帰納関数論  渡辺治,米崎直樹 「計算論入門―計算の基本原理理解のために」(日本評論社) λ計算 高橋正子 「計算論―計算可能性とラムダ計算」(近代科学社)

171 これから勉強すべきこと 数理論理学 人工知能(特に推論システム) プログラミング言語
述語論理 (標準化定理, Gödelの完全性定理, Gödelの不完全性定理) 人工知能(特に推論システム) 融合法(resolution) プログラミング言語 Lisp, Prolog, ML

172 理論計算機科学の分野 型理論 (type theory) プログラム意味論 (model theory)
プログラム検証 (program verification) プログラム自動生成 (program synthesis) 計算機代数 (computer algebra) 定理自動証明 (automated reasoning)

173 理論計算機科学の応用 コンパイラ設計(型理論の応用) 言語設計(計算モデル、意味論) 認証技術、電子商取引(推論システム)
セキュアコンピューティング(推論、計算論) プログラム/システム検証 ハードウエア検証(モデル検査) CADシステム(計算機代数、定理自動証明) 自動化技術(推論システム) ゲームプログラム(人工知能)

174 (おまけ)推進中の研究 幾何定理自動証明 幾何学的プログラミング言語設計 記号的代数計算の高速化 プログラム仕様抽出の自動化 プログラム検索
計算幾何アルゴリズム検証 将棋の新手発見


Download ppt "計算量の理論 講義資料 ver.1 (2006.1.12)."

Similar presentations


Ads by Google