3. クラス P 定義3.1 クラスP

3.1
3. 
P
P DTM (
P
Turing
)
P= DTIME(nk)
k
2
2
(
Turing
)
• 
• 
(
)
3
4
PATH
PATH
={<G,s,t>| G
PATH
s
s
t
}
t
?
<G,s,t>
s
3.  G
a
3.2
PATH
M=“
1. 
2. 
P
b
(a,b)
b
4.  t
PATH
M
5
6
RELPRIME
RELPRIME
={<x,y> | x y
1 4
1
RELPRIME
m
2
(m
3
O(nm)
G
)
x y
?
3.3
n
1+1+m
(relatively prime)}
RELPRIME P
G
M
PATH
Euclid
7
E
8
a=qb+r
(a b
gcd(a,b)=gcd(b,r)
r
0
)
R
r<b
E
<x,y>
<x,y>
x y 2
)
1.  <x,y> E
)
2. 
1. y=0
2.
x y 2
1
x:=x mod y
3. x y
4. x
9
10
3.4
a. 1274 10505
=gcd(740,629)
=gcd(22,5)
=gcd(629,111)
=gcd(5,2)
=gcd(111,74)
=gcd(2,1)
=gcd(74,37)
=gcd(1,0)=1
1274 10505
•  x/2 ≥ y
x
gcd(8029,7289)=gcd(7289,740)
=gcd(313,22)
x<y
3
b
a
gcd(10505,1274)=gcd(1274,313)
2
?
b. 7289 8029
2
x>y
x mod y < y ≤ x/2
x/2<y≤x
•  x/2 < y
x
x y
=gcd(37,0)=37
3
x y
7289 8029
11
x mod y = x-y < x/2
1
2
12
(Context-Free Language)
3.5
2 3
log x
x y
log y
P
(Context-Free Grammar)
O(n)
?
4
G=(N,Σ, P, S)
N:
Σ:
S: S N
P: P N×(N Σ)*
14
15
(Dynamic Programming)
Chomsky
1. 
Chomsky
A→BC
2. 
A→a
a:
1
, A:
, B,C:
S
3. 
S→ε
16
17
3.5
(
G
1)
3.5
(
w
w=w1…wn
1
n×n
(i,j)
i≤j
wiwi+1…wj
2)
2
18
3.5
(
19
3)
3.5
(
4)
A→BC
B 1
k
C 2
A
k+1
B C
A
2
k
(1,n)
20
S
21
3.6
1
w=baba
1
G:
3
R→TR|a
4
T→TR|b
3
4
T
S→RT
R→TR|a
T→TR|b
R
2
S→RT
2
T
R
T→w1
R→w2
T→w3
R→w4
w=w1w2w3w4
=baba
3.5
22
1
2
1
2
T
R,T
R
3
4
S
T
3
R,T
1
S→RT
R→TR|a
T→TR|b
2
w=w1w2w3w4
=baba
1
2
3
T
R,T
S
R
S
S
T
R,T
3
R
4
23
w=w1w2w3w4
=baba
24
S→RT
R→TR|a
T→TR|b
R
4
(R
T)→w1w2
S→w2w3
(R
T)→w3w4
4
S→w1w2w3
S→w2w3w4
25
1
1
2
3
T
R,T
S
S,R,T
R
S
S
T
R,T
2
3
4
1
v G
S→RT
R→TR|a
T→TR|b
O(n)
2
R
4
n
(S
w=w1w2w3w4
=baba
nv
n
R
n
r G
T)→w1w2w3w4
r
O(n3)
n
26
27
(satisfiability problem)
(satisfiability problem)
(
x=0, y=0, z=0
)
TRUE(=1) FALSE(=0)
φ
AND( ),OR( ),NOT(¬)
0
0=0
0
0=0
¬ 0=1
0
1=0
0
1=1
¬ 1=0
1
0=0
1
0=1
1
1=1
1
1=1
¬(x y)
1
SAT={<φ> | φ
28
(z
x ¬z)
0 1
(satisfiable)
}
29
(CNF)
3SAT
x ¬x
(x1
(x1
¬x2 ¬x3)
(x3
¬x5
x6)
(x3
¬x6
x4)
(x4
x5
x6)
x4)
¬x2 ¬x3
3
CNF
3CNF
(x1 ¬x2
x4)
¬x3
(x3 ¬x5 x6)
(x3
3SAT={<φ> | φ
¬x6)
3CNF
}
(Conjunctive Normal Form)
CNF
30
31
2SAT
(x1 ¬x2)
(x3
x6)
3.7
(x4 ¬x6)
(x5 x6)
2
1.
(x y)
(x ¬y)
(¬x y)
(x ¬y)
(¬x y)
(¬x ¬y)
(¬x ¬y)
CNF
2CNF
(x y)
2SAT={<φ> | φ
?
2CNF
}
=(x (y ¬y))
=(x 0)
(¬x (y ¬y))
(¬x 0)
=x ¬x
=0
32
33
3.7
3.8
2.
(x y)
(x y)
(z
→(x z)
→z
P
?
¬y)
(z
¬y)
(¬w y)
(¬w y)
(¬x ¬y)
L1,L2
(¬x ¬y)
(¬w ¬x)
P
L1 O(nc)
A1
L2 O(nd)
A2
¬w
A1,A2
A
A
L1
L2 O(nc+nd)=O(nmax{c,d})
34
35
5
A1
2SAT
A2
B
B L1∩L2 O(n(nc+nd))=O(nmax{c,d}+1)
A1
C L1 O(nc)
C
A1
36
37

Download Report