C
n
n
n
n
10
NP
2
N
(V, E*)
n
G = (V, E)
E* = {{u,v} | u,v V, u ≠ v}
Gc = (V, E* − E) G
G
N
Gc
1
2
3
4
1
2
5
3
4
(Gc)c = G
5
N
N
vs
n
G = (V, E)
V’
G
V’
G
G’ = (V’, E’)
E’ = { {u, v} | u,v V’ ,{u, v} E }
V
V’
G
G
Gc V’
u,v V’ (u ≠ v )
{u, v}
Gc
u,v V’ (u ≠ v )
{u, v}
1
1
G
G’
2
4
44
5
7
5
7
V’ = {2,4,6,7,9}
4
3
4
7
2
2
3
3
1
2
5
7
8
8
9
6
9
8
9
6
9
6
N
N
G=(V, E)
V’
2
(a) V’
G
(b) Gc
V’
V
n
n
n
IndVerSet
Gc
G
IndVerSet NP
9.8
Clique
NP
Clique ≤P IndVerSet
n
Clique
10.1 IndVerSet
NP
6
N
N
G
G=(V, E)
G
1
2
2
4
3
4
3
5
7
8
V
5
7
(a) V’
G
(b) Gc
V’
(c) V − V’
G
8
9
6
9
e={u,v}
V’
V’
3
1
V−V’
u, v
<G, 4>
Ind erSet
6
e={u,v}
u, v
<G, 5>
IndVerSet, Clique,
VertexCover
VertexCover
N
G=(V, E)
I V={1,…,n}
i V
Si = { e E | e
(a) I
(b) {Si}i
N
i}
G
I
E
{Si}i
V
N
N
(1,2)
(2,3)
G
S1
1
2
4
3
5
7
8
9
6
(1,2)
(2,3)
G
(2,4)
S2
(3,7)
S3
(3,8)
S4
(4,5)
S5
(4,7)
S6
(4,9)
S7
(5,6)
S8
(5,7)
S9
E
1
2
4
3
8
9
6
e={u,v} E
(5,9)
I
(7,8)
(7,9)
5
7
I
G
u, v
⟺ {Si}i
n
n
SetCover
9.9
I
VertexCover NP
VertexCover ≤P SetCover
n
NP
S2
(3,7)
S3
(3,8)
S4
(4,5)
S5
(4,7)
S6
(4,9)
S7
(5,6)
S8
(5,7)
S9
(5,9)
(7,9)
NP
10.2 SetCover
(2,4)
(7,8)
E
N
n
S1
N
E
N
3Sat
N
3DM
10.3 3Sat
3Sat
3DM
3DM
n 3Sat
3CNF
φ = c1∧…∧cm
n φ
x1,…, xn
n
n
n
n
1
N
X, Y, Z
N
W
xi
n
2m
m
3
m
¬xi[1]
m=4
xi[1]
ai[2]
¬xi[2]
ai[1]
bi[1]
bi[4]
bi[2]
bi[3]
xi[2]
xi[4]
¬xi[4]
ai[4]
xi[3]
ai[3]
¬xi[3]
ai[j]
bi[j]
N
N
¬xi[1]
m=4
xi[1]
ai[2]
¬xi[2]
ai[1]
bi[1]
bi[3]
xi[2]
xi[1]
ai[2]
¬xi[2]
¬xi[4]
bi[1]
bi[3]
xi[2]
xi[4]
bi[4]
bi[2]
ai[4]
xi[3]
ai[3]
ai[1]
xi[4]
bi[4]
bi[2]
¬xi[1]
m=4
¬xi[4]
ai[4]
xi[3]
ai[3]
¬xi[3]
¬xi[3]
N
N
n
TiT = {(¬xi[j], ai[j],
TiF = {(xi[j],
Ti =
xi[1], xi[2],…, xi[m]
xi=1
¬xi[1], ¬xi[2],…, ¬xi[m]
xi=0
TiT ∪
TiF
bi[j]) | 1≤j≤m}
ai[j+1], bi[j]) | 1≤j≤m−1}∪{(xi[m], ai[1], bi[m])}
N
cj = u ∨ v ∨ w
s1[j] s2[j]
N
(u, v, w
3
s1[j] s2[j]
)
3
3
3
u[j]
v[j]
s1[j]
w[j]
s2[j]
N
N
n
n
2mn
Cj ={([j], s1[j], s2[j]) | ∈ cj}
n
∪{(¬[j], s1[j], s2[j]) | ¬ ∈ cj}
c=u
v w
c={u, v, w}
m(n−1)
n
3DM
mn
m
N
3
N
(xi[j], g1[k], g2[k]), (¬xi[j], g1[k], g2[k])
i, j, k (1≤i≤n, 1≤j≤m, 1≤k≤m(n−1))
x1[1] ¬x1[1] x1[2] ¬x1[2]
n
G ={ (xi[j], g1[k], g2[k]) | 1≤k≤m(n−1), 1≤i≤n, 1≤j≤m}
{(¬xi[j], g1[k], g2[k]) | 1≤k≤m(n−1), 1≤i≤n, 1≤j≤m}
xn[m] ¬xn[m]
x1[1]
g1[k], g2[k]
g1[1] g2[1] g1[2] g2[2] g1[3] g2[3]
3
g1[m(n-1)]
g2[m(n-1)]
N
3Sat
φ=c1∧…∧cm
N
3DM
X = ∪i,j {xi[j], ¬xi[j]}
Y = ∪i,j {ai[j]}∪(∪j{s1[j]})∪(∪k{g1[k]})
Z = ∪i,j {bi[j]}∪(∪j{s2[j]})∪(∪k{g2[k]})
3Sat
1 ≤ i ≤ n,
1 ≤ j ≤ m,
1 ≤ k ≤ m(n−1)
3DM
Gk ={ (xi[j], g1[k], g2[k]) | 1≤i≤n, 1≤j≤m}
∪{(¬xi[j], g1[k], g2[k]) | 1≤i≤n, 1≤j≤m}
W = (∪iTi) ∪ (∪j Cj) ∪ (∪kGk)
<X, Y, Z; W>
W
3DM
X×Y×Z
3CNF
Ti = {(¬xi[j], ai[j], bi[j]) | 1≤j≤m}
∪{(xi[j], ai[j+1], bi[j]) | 1≤j≤m−1}∪{(xi[m], ai[1], bi[m])}
Cj ={(x[j], s1[j], s2[j]) | x ∈ cj}∪{(¬x[j], s1[j], s2[j]) | ¬x ∈ cj}
3CNF
3Sat
n
n
φ
⟺ <X, Y, Z; W>
n
N
N
⟹
⟸
φ
n
n
n
xi:=1
xi
¬xi[1], ¬xi[2],…, ¬xi[m]
xi:=0
xi
xi[1], xi[2],…, xi[m]
φ
n
φ
xi
1
¬xi[1], ¬xi[2],…, ¬xi[m]
0
xi
W
n
W
n
N
10.4 3DM
3DM
N
NP
n
10.3
n
9.7
3CNF
(x ∨ y ∨ z)∧(¬x ∨ ¬z ∨ ¬w)∧(¬y ∨ z ∨ w)
NP
n
n
φ
NP
3DM
n
1
X, Y, Z
n
n
3Sat ≤P 3DM
3Sat
9.5
NP
3DM
NP
N
3DM
SubsetSum
10.5 3DM
SubsetSum
N
37
N
3DM
N
SubsetSum
X×Y×Z
n
X={x1,…, xn}, Y={y1,…, yn}, Z={z1,…, zn}
w =(xi, yj, zk) W
X×Y×Z
E(w) = a1…an b1…bn c1…cn
ai=bj=ck
n
n=6
w = (x2, y4, z3)
0
1
0
0
X
0
E(w)
0
0
0
0
1
Y
0
0
0
0
1
0
Z
0
0
N
N
dn
3DM
E(t)
d-
M
⊕
W={w1,…,wk}
M ={u1,…,um} W
dE(M)
E(M) = E(u1) … E(um)
⊕
n
n d
d = |W| + 1
X×Y×Z
n = |X| = |Y| = |Z|
d = |W| + 1
E(wi) : wi
E(wi) : E(wi) dS = {E(w1), …, E(wk)}
t = (d3n−1)/(d−1) = d3n−1 + + d1 + d0
= |W| + 1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
0
0
0
0
2
0
0
0
S, t
N
3DM
SubsetSum
N
SubsetSum
SubsetSum
NP
10.6 SubsetSum
n
NP
n
M
⟺ E(M)
1
n
SubsetSum NP
n
10.5
3DM ≤P SubsetSum
n
10.4
3DM
n
9.5
NP
SubsetSum
NP
Sat
3Sat
Cook-Levin
NP
Clique
IndVertSet
3DM
SubsetSum
VertexCover
SetCover
© Copyright 2024 ExpyDoc
