計算の理論 II 言語とクラス月曜4校時大月美佳講義の前に  今後の予定講義：1/22, 1/30, 2/2 試験：2/9  レポート回収延期：1/30まで待つ今日の講義内容 1. 予定 1. 前回の復習 2. クラス P, NP, PSPACE, NSPACE, NLOG, DLOG 3. 問題 2. 時間があれば 1. 還元可能性 2. NP完全など T(n)時間限定 T(n)を関数とし、MをkテープNTMとする。言語Lに対して以下の(1)(2)が成り立つとき、 MはLを時間T(n)で受理するという。また、MはT(n)時間限定(T(n)-time bounded) であるという。 (1) L=L(M) (2) 有限個を除いてすべてのx∈Lに対して timeM(x)≦T(|x|) S(n)領域限定 S(n)を関数とし、MをkテープNTMとする。言語Lに対して以下の(1)(2)が成り立つとき、 MはLを領域S(n)で受理するという。また、MはS(n)領域限定(S(n)-space bounded) であるという。 (1) L=L(M) (2) 有限個を除いてすべてのx∈Lに対して spaceM(x)≦S(|x|) NTIME(T(n)), NSPACE(S(n)) NTIMEk(T(n)) ={L|LはあるkテープNTMによって時間T(n)によって受理される} NSPACEk(S(n)) ={L|LはあるkテープNTMによって領域S(n)によって受理される} NT IME(T (n))   NT IMEk (T (n)) k 1 NSP SCE ( S (n))   NSP ACEk ( S (n)) k 1 DTIME(T(n)), DSPACE(S(n)) DTIMEk(T(n)) ={L|LはあるkテープDTMによって時間T(n)によって受理される} DSPACEk(S(n)) ={L|LはあるkテープDTMによって領域S(n)によって受理される} DT IME(T (n))   DT IMEk (T (n)) k 1 DSP SCE ( S (n))   DSP ACEk ( S (n)) k 1 正規言語 Lを正規言語とする。このとき、以下の(1), (2)が成立する。 (1) L∈DTIME(n) (2) L∈DSPACE(1) 領域構成可能関数S(n)は、 L(M)={1}*かつ有限個を除いてすべてのx∈{1}*に対して spaceM(x)=|_S(x)_|となるDTM Mが存在するとき、領域構成可能(fully space constructible)である。このときMはS(n)を、領域構成する。時間構成可能関数T(n)は、 L(M)={1}*かつ有限個を除いてすべてのx∈{1}*に対して timeM(x)=|_T(x)_|≧xとを満たすDTM Mが存在するとき、時間構成可能(fully time constructible)である。このときMはT(n)を、時間構成する。 P, NP P 決定性Turing機械によって多項式時間で受理される言語  NP 非決定性Turing機械によって多項式時間で受理される言語  P≠NP まだ証明されていない Pの定義 P   DT IME(n ) k k 1 p(n)  am n  am 1n m m 1  ...  a1n  a0 am  0のとき、 kを十分大きくとる (m  k )と p ( n)  O ( n ) k  DT IME( p(n))  DT IME(n ) k NPの定義 NP   NT IME(n ) k k 1 Pと同様に p ( n)  O ( n ) k  NT IME( p (n))  NT IME(n ) k PSPACE, NSPACE PSPACE   DSPACE(n ) k k 1 Savitchの定理より NSPACE(n )  DSPACE(n ) (k  1) k k PSPACE   DSPACE(n ) k k 1   NSPACE(n ) k k 1 NLOG, DLOG  非常にわずかな領域しか使用しないTM によって受理される言語 NLOG=NSPACE(log n) DLOG=DSPACE(log n)  包含関係 DLOG⊆NLOG⊆P⊆NP⊆PSPACE このうち証明されているのはNLOG⊆PSPACE のみ問題  写像A: Σ*→{0, 1} アルファベットΣで表現された真偽問題(yes/no problem)、問題 Σ*の部分集合{x∈Σ*|A(x)=1} →AはΣ*上の言語  写像Aの複雑さ =言語{x∈Σ*|A(x)=1}を受理するTMの計算量問題の例1  COMPOSITE ={x∈{0, 1}*|xは合成数の2進数表現} ∈NP TMの動作入力wが与えられると、非決定的に動き、第1作業テープと第2作業テープにxとyを書き出す。 x, yが2以上の2進数であることを調べた後で xとyを掛け算したものを第3作業テープに書き出し、これが入力wと一致すればwを受理する。 wが受理される場合の時間量 |x|, |y|≦|w|であるので多項式時間問題の例2  GRAPH 有限な有向グラフの符号化のひとつ G=(V, E) 頂点集合V={w1, …, wn} 辺集合E={(u1, v1), …, (um, vm)}⊆V×V G⊆(Γ∪{#})*として符号化 w1#…#wn##u1#v1#…#um#vm## wi∈Γ+ (1≦i≦n), uj ,vj ∈V (1≦j≦m)  GRAPH∈DLOG ∴ GRAPH∈P 還元可能性  計算可能関数 f: Σ1*→Σ2* 言語 L1⊆Σ1*, L2⊆Σ2* それぞれTM M1 ,M2で受理すべてのx∈Σ1*に対して x∈L1 ⇔ f(x)∈L2 となるとき、 L1をL2に還元(reduce)できるという。  x∈L1 の判定 M1 を走らせるかわりにf(x)がM2 で受理できるか調べる。変換機変換機(transducer) 1本の入力テープ(読みとりのみ) k本の作業テープ(読み書き可) 1本の書き出し専用テープ(左方向に動けない) 対数領域計算可能(log space computable) fが領域log2 nで計算可能多項式時間計算可能(polynomial time computable) ある多項式p(n)とfが時間p(n)で計算可能還元可能対数領域還元可能 (log space reducible) L1≦log L2 (via f ) 多項式時間還元可能 (polynomial time reducible) L1≦p L2 (via f ) C≦log L0, C≦p L0 言語のクラスCがすべてのLについて L≦log L0, L≦p L0 NP完全、PSPACE完全、P完全 ≦log 完全、 ≦p 完全 1. 2. L0 ∈C すべてのL ∈Cに対してL≦log L0, L≦p L0 となる NP, P, PSPACEに対してそれぞれ≦log 完全(または≦p 完全)であるとき NP完全(NP-complete) PSPACE完全(PSPACE-complete) P完全(P-complete) NP完全な言語  充足可能性問題(SAT)  和積標準形(CNF)  3和積標準形(3SAT)  頂点被覆問題(VERTEX COVER) 最後に開始  次回 – 明日1/22 14:20～15:50 – NP完全まわり