5. クラスNP

2
HAMPATH
2
(2
)
5. 
NP
HAMPATH
={<G,s,t> | G
s
t
}
t
s
3
4
HAMPATH
HAMPATH
2
(2
2
(2
)
HAMPATH
={<G,s,t> | G
s
t
)
}
HAMPATH
={<G,s,t> | G
G
HAMPATH
s
t
s
t
}
5
6
HAMPATH
•  HAMPATH
COMPOSITES={x |
p,q>1
x=pq}
• 
x
p
7
5.1
(certificate)
V
V A
A
c
(verifier)
A={w |
c
V <w,c>
}
(polynomial time verifier)
c
A
A
w A
(certificate)
c A
(proof)
w
w
8
(polynomially verifiable)
•  HAMPATH
•  COMPOSITES
s
t
9
5.2
NP
HAMPATH
NP
•  HAMPATH COMPOSITES
10
N1=“
1.  n
NP
NTM
<G,s,t>
p1,...,pn
n
G
1 n
1
2. 
3.  s=p1
t=pn
4.  1
n-1
1
i
(pi,pi+1) G
”
11
12
5.3
5.3
NTM
NP
A NP
V NP
A
NTM N
A
DTM
nk
N=“
n
1. 
nk
2. 
<w,c>
3.  V
V
N
w
c
V
”
13
A
5.4
NTM N
V
V=“
1.  c
14
nk
N
NTM
• 
<w,c>
c
N
N
N
”
2. 
N
V
c
N
V
|w|=n
V
nk
15
16
5.6
CLIQUE NP
(clique)
k
kCLIQUE={<G,k> | G
k-
(k-clique)
}.
17
18
5.6
SUBSET-SUM
CLIQUE
V
V=“
<<G,k>,c>
1.  c G
k
2.  G
c
• 
3. 
19
20
5.7
SUBSET-SUM
6
NP
• 

Download Report