n
n
Sat
n
3Sat
Information
Science
11 Cook-Levin
(Sat)
φ
n
φ
n
φ
1
SAT={<φ> | φ
¬ (x∨y) ∨(z∧x∧¬z)
(satisfiable)
0 1
}
Sat
Sat
Sat
NP
SAT
n
Sat
V=“
1. c
Clique
V
Sat
<<φ>,c>
φ
IndVertSet
c
2.
Sat
3Sat
Cook-Levin
3DM
VertexCover
SubsetSum
φ
3.
SetCover
NP
Sat
Sat
A NP
n
n
N
nk
A
A
NTM
Sat
(k
A
Sat
N
w
)
φ
N
w
N
w
φ
φ
Sat
Sat
w
N
w
w
n
N
N
n
(nk+1)×(nk+4)
#
nk+1
$
q0
w1
□
w
N
□
□
N
□
#
#
#
#
#
#
#
#
1
nk+1
nk
$
q0
w1
#
#
#
#
#
#
#
nk+4
1
nk
nk+4
#
#
Sat
A
Sat
φ
Sat
n
C=Q
Γ {#}
n Q
i
n
φ
N
φ=φcell φstart φmove φaccept
j
cell[i, j]
C
cell[i, j]
xi,j,s
xi,j,s
φ
Sat
n
Γ
n
n
A
1
cell[i,j]=s
φstart
φmove
φaccept
xi,j,s (1≤i≤nk+1, 1≤j≤nk+4, s∈C)
1
φcell
1
w
1
N
N
Sat
A
Sat
φcell
Sat
n
φcell
1
A
1
φstart
n
N
%
%
(
%
(
'
ϕ cell = ∧ ' ' ∨ xi, j,s * ∧ '' ∧ (¬xi, j,s ∨¬xi, j,t ) **
)
' s,t∈C
*
1≤i≤n k +1 ' & s∈C
& s≠t
)
1≤ j≤n k +4 &
φstart
Sat
φstart=x1,1,#
(
*
*
*
)
1
w
x1,2,$ x1,3,q0
x1,4,w1 x1,5,w2
x1,n+4,□ …
…
x1,n+3,wn
x1,nk+3,□ x1,nk+4,#
1
C
s t
#$q0w1w2...wn□□...□#
Sat
A
Sat
φaccept
Sat
n
φaccept
A
φmove
Sat
φmove
n
2×3
n
ϕ accept =
∨
k
1≤i≤n +1
1≤ j≤n k +4
xi, j,qaccept
n
N
2×3
N
Sat
A
Sat
φmove
Sat
A
n
n
q1
q1
c de af g
c de af g
(q2, b, R)
c
c
δ(q1, a)
d
d
e q1 a
e b q2
f
f
g
g
(q2, b, L)
c de bf g
c de bf g
Sat
Sat
φmove
Sat
A
n
n {#}
#
#
$
$
d e q1 a
d q2 e b
f
f
$
$
a
a
a, b, c
Γ – {$} q1, q2 Q
δ(q1, a)={(q1, b, R)},
Q
a
a
φmove
Sat
n
n Γ
c
c
δ(q1, a)
q2
q2
A
φmove
Sat
δ(q1, b)={(q2, c, L), (q2, a, R)}
b
b
a, b, c
a
a
Γ−{$}
b
b
c
c
a
a
b
b
#
#
NTM
a
q1
b
a
q1
b
a
a
q1
q2
a
c
a
a
q2
a
a
b
#
$
a
a
b
a
b
b
b
#
$
a
a
b
q2
c
b
b
g
g
Sat
A
Sat
φmove
Sat
A
NTM
n
a
b
a
a
q1
b
b
q1
b
a
a
a
q1
a
a
q2
b
q2
Sat
φmove
Sat
n
1
n
Sat
A
φmove
Sat
A
φmove
Sat
N
φmove=
((i,j)
)
1<i≤nk+1
1<j<nk+4
φcell
a1 a2 a3
φstart
φmove
a4 a5 a6
(i,j)
(xi−1,j−1,a1
a1,...,a6
xi−1,j,a2
xi−1,j+1,a3
xi,j−1,a4
w
xi,j,a5 xi,j+1,a6)
w
N
N
φaccept
φ
φ = φcell φstart φmove φaccept
Sat
Sat
φ
φ
φ
(
|C|
n
(nk+1)×(nk+4)
n
|C|
C
n
|C|
n
φcell
n
φstart
O(n2k)
1
φmove
O(n2k)
O(n2k)
O(n2k)
φaccept
n
n
O(n2k)
N
φ
w
n
N
φ
φstart
O(nk)
w
)
3Sat
3Sat
Sat
3Sat
Cook-Levin
NP
Clique
IndVertSet
3DM
SubsetSum
VertexCover
)
SetCover
4
3Sat
3Sat
3Sat NP
CNF
n
3Sat NP
n
Sat
3CNF
n
3Sat
n
CNF
3-CNF
(a1
a2
m−3
m−2
Tseitin
CNF
(a1
3Sat
a2
z1)
(¬z1 a3 z2) (¬z2 a4 z3)
… (¬zm-3 am-1 am)
3Sat
CNF
3CNF
CNF
CNF
n
(a1
a2
a3
a2
x)
CNF
a4)
n (x1
(a1
am)
…
(¬x a3 a4)
(a1
a2
a3
a4
(a1
a2
x)
(¬x a3 y)
m=2
a5)
m=3
(¬y a4 a5)
y1)
…
(xm
ym)
(x1 y1)
(x2 y2)
(x1 x2)
(x1 y2)
(y1 x2)
(x1 y1)
(x2 y2)
(x3 y3)
2m
m
(y1
y2)
(x1 x2 x3)
(x1 x2 y3)
(x1 y2
x3)
(x1
y2
y3)
(y1 x2 x3)
(y1 x2 y3)
(y1 y2
x3)
(y1
y2
y3)
3Sat
3Sat
Tseitin
Tseitin
CNF
n
n
CNF
¬x ((y z)
a
¬
x
b
c
d
y
Sat
u
a
(a ⟷ b c)
(b ⟷ ¬x)
(c ⟷ d u)
(d ⟷ y z)
a
(¬ a b c) (a ¬ b) (a ¬ c)
(¬b ¬x) (b x)
(¬ c d) (¬ c u) (c ¬ d ¬ u)
(¬ d y z) (d ¬ y) (d ¬ z)
z
3Sat
Cook-Levin
NP
u)
Clique
IndVertSet
3DM
SubsetSum
VertexCover
SetCover
A, B
n
n x
⟷A
B
n x
⟷A
B
n x
⟷¬ A
(x → A B) (¬ x → ¬ (A B))
(¬ x A B) (x (¬ A ¬ B))
(¬ x A B) (x ¬ A) (x ¬ B)
(x → A B) (¬ x → ¬ (A B))
(¬ x (A B)) (x ¬ A ¬ B)
(¬ x A) (¬ x B) (x ¬ A ¬ B)
(x → ¬A) (¬ x → A)
(¬x ¬A) (x A)
© Copyright 2024 ExpyDoc
