多項式時間検証可能装置

C
! 
NP
! 
7
! 
NP
Clique
! 
NP
SubsetSum
NP
HamPath
HamPath
={<G,s,t> | G
s
t
}
2
! 
(2
)
s
t
HamPath
HamPath
! 
HamPath
={<G,s,t> | G
s
t
HamPath
}
! 
2
! 
(2
HamPath
! 
)
t
s
Composites={x |
p,q>1
x=pq}
V
V A
! 
A={w |
x
! 
G
c
}
|w|
! 
(polynomial time
! 
! 
A
(verifier)
V <w,c>
x
p
verifier)
c
|w|
A
! 
A
(polynomially verifiable)
(certificate)
c
! 
w
! 
c
A
A
(certificate)
(proof)
!  HamPath
s
t
!  Composites
NP
9
NP
NP
NP
HamPath
N1=“
NP
<G,s,t>
1.  G
n
7.1 HamPath
NP
7.2 Composites
n
{1,…,n}
p1,...,pn
2. 
s=p1, t=pn
NP
3. 
i=1,…,n−1
i
4. 
11
(pi, pi+1)
G
”
12
NP
NP
NP
7.3
L
NTM
NP
L
NP =
kNTIME(n
! 
L
NP
! 
V
nk
L
DTM
NTM N
! 
k)
V
N=“
n
1. 
nk
2. 
<w,c>
L
w
c
V
3.  V
”
13
14
NP
! 
! 
N
N
V=“
1.  c
NTM
L
N
nk
V
L
<w,c>
N
c
N
2.  N
! 
N
CLIQUE
”
c
|w|=n
V
nk
V
V
N
15
NP
NP
Clique
! 
Clique = {<G, k> | G
(clique)
! 
k
k-
NP
7.4 Clique
NP
Clique
V
Clique
V=“
Clique
<<G, k>, c>
1.  c G
k
2.  G
c
3. 
SUBSETSUM
19
k-
}.
NP
NP
SubsetSum
SubsetSum
SubsetSum
7.5 SubsetSum NP
SubsetSum
={<S, t > | S
t = Σx T x
S
T
}.
!  S={12,
1, 3, 8, 20, 50}, t=44
!  S={12, 1, 3, 8, 20, 50}, t=14
NP
SubsetSum
7.5
V
SubsetSum
V=“
1.  c
2.  c
SubsetSum
<<S, >, c>
S
t
3. 
23
! 
G=(VG, EG) H=(VH, EH)
(isomorphic)
φ: VG → VH
{u,v} EG " {φ(u), φ(v)} EH
! 
Iso = {<G, H> | G H
Iso
NP
}

Download Report