計算の理論 I －講義についてー

計算の理論 II
試験前の準備
月曜4校時
大月美佳
講義の前に
今日の講義内容
1. 評価方法確認
2. 計算量残り
3. レポート回収
本講義の評価方法
 出席 (MAX 20点)
– 出席率2/3以下は出席点なし
– 遅刻は20分まで
 レポート(MAX 40点)
– 大(20点)×1 、小(10点)×2
 定期試験 (MAX 40点)
– ミニテスト＋α(JABEE関連)
– 再試は基本的になし
カウンタ
作業用テープをカウンタとして使用
2進数x=b1…bm→$bm…b1BB…
1加える動作
(初期状態p, 終了状態q) →(p, add1, q)
1引く動作動作
(初期状態p, 終了状態q(x>0), r(x=0))
→(p, sub1, q, r)
(p, add1, q)
s1
X
s2
Y
D
p
$
p1
$
R
足す
p1
0/B
p2
1/1
L
p1
1
p1
0
R
戻る
p2
0/1
p2
0/1
L
p2
$
q
$
N
(p, sub1, q, r)
引けない
借りる
引けた
先頭探し中
戻れる
先頭発見
0削除
戻れる
終了
戻り中
終了
s1
X
s2
Y
D
p
$
p1
$
R
p1
B
r
B
L
p1
0
p1
1
R
p1
1
p2
0
R
p2
0
p2
0
R
p2
1
p4
1
L
p2
B
p3
B
L
p3
0
p3
B
L
p3
1
p4
1
L
p3
$
q
$
N
p4
0/1
p4
0/1
L
p4
$
q
$
N
カウンタ使用時の領域量
L={w#w| ∈{0, 1}*}の領域量はO(log2n)
入力テープx=￠x1…xn#y1…ym$とする
C1←1; C2←1;
1: 入力ヘッドをx1…xn#のC1番目に持っていき、そこ
の記号Aを記憶する;
入力ヘッドを#まで右に動かし、y1…ymのC2番目に
持っていき、そこの記号Bを記憶する;
if A=B then C1←C1+1; C2←C2+ 1; goto 1
else if A=# and B=$ then accept else reject
領域構成可能
関数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   DTIME (n )
k
k 1
p(n)  am n m  am 1n m 1  ...  a1n  a0
am  0のとき、
kを十分大きくとる
(m  k )と
p ( n)  O ( n )
k
 DTIME ( p(n))  DTIME (n )
k
NPの定義
NP   NTIME (n )
k
k 1
Pと同様に
p ( n)  O ( n )
k
 NTIME ( p (n))  NTIME (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)
最後に
開始
 小レポートを提出してから帰ること
– 前回出席＋今回出席
– +MAX10点

Download Report