.
Z NP-, Z' NP Z.
Z NP-, Z NP - Z NP.
, NP - NP: () , NP - . NP - ( !) NP - ( ). , - NP - P, P NP . , - NP - . .
- , NP - NP -? NP - . , , - NP - . NP - Z1. NP - Z2, : -, , Z2 NP ( ), -, Z1 Z2 ( Z2 Z1, !) , NP - Z Z2 Z1. NP - , Z1 Z2, Z3 , : Z1 Z3 Z2 Z3. . ( ) NP - NP - .
, NP - ( ?). NP -, NP.
, Z NP - , ~ Z NP -, , NP .
(S.A.Cook, 1971.) , : NP - .
NP - ? NP -: , . , . NP - . Z z Z l . , , , P(l) qy? , Z , . NP - Z0.
|
|
. Z1 , ( l) z0 Z0 z1 Z1. , Z1 NP -, NP -.
.
X = {xi, i=1...N} () G(X). X, G(X) = 1?
. NP -.
(.. , ).
n , m , l NP - z Z , P(l) NP - (.. , z Z, l .) , .
1) {Qik, 0iP(l), 0kn}; Qik = 1, i k.
2) {Hij, 0iP(l), -P(l)jP(l)}; Hij = 1, i j.
3) {Aijr, 0iP(l), -P(l)jP(l), 0rm}; Aijr = 1, i j ar.
Qik, Hij, Aijr , .. , . , , , , .. , . 6 . .
1. .
2. .
3. .
4. i = 0 q0, 1, .
5. , P(l) qy ( ).
6. i i+1 .
, .
. .
1. (Qi0 Qi1... Qin) & (~Qi0 ~Qi1) & (~Qi0 ~Qi2) &...
& (~Qi,n-1 ~Qi,n), 0iP(l) (.. Qij , !).
2. Hij.
3. Aijr , :
(Aij0 Aij1... Aijm) & (~Aij0 ~Aij1) &... & (~Ai,j,m-1 ~Ai,j,m),
0iP(l), -P(l)jP(l).
4. Q00 & H01 & A0,1,v1 & A0,1,v2 &... & A0,l,vl & A0,l+1,0.
av1, av2,... avl - ( ).
|
|
5. QP(l),1 (, qy q1).
6. :
6.1. i j, i+1.
~Aijr Hij Ai+1,j,r, 0iP(l), -P(l)jP(l), 0rm.
, , : j ar, , ! , , .
6.2. i qk, j ar, i+1 (q'k, j', a'r), :
~Qik ~Hij ~Aijr (Hi+1,j'Qi+1,k'Ai+1,j,r' Hi+1,j''Qi+1,k''Ai+1,j,r'' )
0iP(l), -P(l)jP(l), 0kn, 0rm.
. . , , l.
6.2 .
, 6 . G(Q, H, A), Z, z.
, , .. Qik, Hij, Aijr, 6 . , , .. z Z . , , Qik, Hij, Aijr, G(Q, H, A). z G(Q, H, A). , Z ( ). l? , , l.
Z NP, NP - . , , ( : , ), NP. , NP -, .
NP-
3- ( 3-). : x1, x2,... xn, . , , 1.
, NP, .. . NP -, , 3-.
, 3-, 3- , .
, , , .
8 :
G(X) =x1& (x1x3) & (x2x4x6) & (x3x5 x7 x8)
& (x1x2 x3x4 x5 x8).
G(X) . , 3, ( ) .
1) x1 (x1y1y2) & (x1y1 y2) & (x1 y1y2)
& (x1 y1 y2).
|
|
y1 y2, x1, .
2) x1x3 (x1x3y3) & (x1x3 y4).
.
3) x2x4x6.
.
4) x3x5 x7x8 (x3x5y5) & (y5 x7x8).
, . , , x5. , y5=1, . , , y5 .
5) x1x2 x3x4 x5 x8(x1x2y6) & (y6 x3y7) & (y7x4y8) & (y8 x5 x8).
, . , y6, y7, y8, . , y6, y7, y8.
: 4 5 , . : , , yi, .
, , xi, yj, . , xi , yj .
3-. -, , , . , : , , ?
, NP - 3‑.
( ). G = (V, E) V E. K. V V, , V. , G K.
NP - , 3‑. , .
: (x1x3x4) & (x1 x2x4). n=4, m=2. G :
1. xi , . xi xi.
2. ak -, ak1, ak2 ak3.
3. , . , x3, a12 x3. .
.2.1.
.2.1
K = n +2 m = 8.
, G V K , .
, . , xi - xi, . ak . n+2m = K . K . , K , xi - xi ak.
|
|
, . . ak ak, . xi - xi. xi, , . , , , , .. .
, xi, . n , . , , ak . ak, ( ). ak. ak, .. K .
3- . . . , NP -.
NP - . . .
. G = (V, E). , ?
. NP -.
. n, {aij, 1 i, j n} K. (.. ) , K? ( ).
. G = (V, E), A B, K. A B K?
, .
. n pi. ?
.
. n , bi ci, i = 1n. B. , K?.
. m n , 1, 2 .. i- j- tij. , . K. , ?
, , .
m = 2 , ( ). m = 3 , NP - .
. m , n , ti K. , ?
nn. nn, ( ). ?
. F(X) n (, ). K. , , K ?