計算の理論 II NP完全 月曜4校時 大月美佳
講義の前に 今後の予定 講義：1/30, 2/2 試験：2/9 レポート 回収：1/30までなので注意
今日の講義内容 予定 前回の復習 還元可能性 NP完全 時間があれば 決定問題の前振りくらい？
P, NP P NP P≠NP 決定性Turing機械によって多項式時間で 受理される言語 非決定性Turing機械によって多項式時間で まだ証明されていない
Pの定義
NPの定義
PSPACE, NSPACE
NLOG, DLOG 非常にわずかな領域しか使用しないTMによって受理される言語 包含関係 NLOG=NSPACE(log n) DLOG=DSPACE(log n) 包含関係 DLOG⊆NLOG⊆P⊆NP⊆PSPACE このうち証明されているのはNLOG⊆PSPACE のみ
問題 写像A: Σ*→{0, 1} 写像Aの複雑さ アルファベットΣで表現された 真偽問題(yes/no problem)、問題 Σ*の部分集合{x∈Σ*|A(x)=1} →AはΣ*上の言語 写像Aの複雑さ =言語{x∈Σ*|A(x)=1}を受理するTMの計算量
還元可能性 計算可能関数 f: Σ1*→Σ2* x∈L1 の判定 言語 L1⊆Σ1*, L2⊆Σ2* すべてのx∈Σ1*に対して それぞれTM M1 ,M2で受理 すべてのx∈Σ1*に対して x∈L1 ⇔ f(x)∈L2 となるとき、 L1をL2に還元(reduce)できるという。 x∈L1 の判定 M1 を走らせるかわりにf(x)がM2 で受理できるか調べる。
変換機 変換機(transducer) 対数領域計算可能(log space computable) 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 完全 NP, P, PSPACEに対して 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完全な問題 充足可能性問題(satisfiability problem) 和積標準形(conjunctive normal form) SAT={F|論理式Fは充足可能} 和積標準形(conjunctive normal form) CNF={F∈SAT | Fは和積標準形} 3和積標準形 3SAT={F∈SAT | Fは3和積標準形} 頂点被覆問題(vertex cover) VERTEX COVER={(G, k) | k≧0は整数でGは大きさが高々kの頂点被覆を持つ}
P完全な問題 and/orグラフの到達可能性問題(and/or graph accessibility problem) AGAP:特定のルールで石をand/orグラフの頂点におけるかどうか 可解な経路システム問題(solvable path system problem) SPS:ある経路システムが可解な有限経路システムであるかどうか 論理回路値問題(circuit value problem) CVP:論理回路の最終出力が1かどうか
最後に 開始 次回 来週1/30 14:20～15:50 決定問題まわり