В.Б. Алексеев - Электронный коспект лекций, страница 11

pOSKOLXKU L | PROIZWOLXNYJ QZYK IZ NP , TOPOLU^AEM, ^TO wyp | NP -TRUDNAQ ZADA^A, A TAK KAK wyp 2 NP , TOwyp | NP -POLNAQ ZADA^A. tEOREMA kUKA DOKAZANA..53NP -POLNYE ZADA^IsLEDU@]AQ TEOREMA POZWOLQET WYWODITX NP -POLNOTU ODNIH ZADA^ IZ NP -POLNOTY DRUGIH ZADA^.tEOREMA. eSLI L1 NP TRUDNYJ QZYK I L1 POLINOMIALXNOSWODITSQ K QZYKU L2 TO L2 NP TRUDNYJ QZYK eSLI PRI \TOML2 2 NP TO L2 NP POLNYJ QZYKdOKAZATELXSTWO pUSTX L | L@BOJ QZYK IZ NP . tAK KAK L1| NP -TRUDNYJ QZYK, TO L POLINOMIALXNO SWODITSQ K L1. tAK KAKPO USLOWI@ L1 POLINOMIALXNO SWODITSQ K L2, TO I L POLINOMIALXNOSWODITSQ K L2.

tAK KAK L | PROIZWOLXNYJ QZYK IZ NP , TO L2 |NP -TRUDNYJ QZYK PO OPREDELENI@.oPREDELENIE. knf, U KOTOROJ W KAVDOM DIZ_@NKTE ROWNO 3LITERALA, BUDEM NAZYWATX 3-knf.zADA^A 3-WYPOLNIMOSTX (3-wyp).wHODNOJ ALFAWIT TOT VE, ^TO I W ZADA^E wyp.wOPROS WERNO LI, ^TO WHODNOE SLOWO | \TO 3-knf, KOTORAQ WYPOLNIMA.uTWERVDENIE. wyp 2 NP:dOKAZATELXSTWO zADA^A 3-wyp UDOWLETWORQET OPREDELENI@ ZADA^ IZ KLASSA NP . pRI \TOM W KA^ESTWE SERTIFIKATA DOSTATO^NO WZQTXNABOR ~ , NA KOTOROM DANNAQ 3-knf WYPOLNIMA (ESLI TAKOJ SU]ESTWUET), A ALGORITM PROWERKI SERTIFIKATA BUDET PROWERQTX, DEJSTWITELXNOLI WHODNOE SLOWO ESTX 3-knf I WERNO LI, ^TO \TA knf NA NABORE ~RAWNA 1.

wSE \TO MOVNO OSU]ESTWITX ZA POLINOMIALXNOE (OT DLINYWHODA) WREMQ.tEOREMA. zADA^A wyp NP POLNAdOKAZATELXSTWO sWEDEM ZADA^U wyp POLINOMIALXNO K ZADA^E3-wyp. pUSTX A | ALFAWIT OBEIH ZADA^. nAM NADO DLQ KAVDOGO SLOWAa 2 A ZA POLINOMIALXNOE (OT DLINY SLOWA a) WREMQ POSTROITX SLOWO'(a) TAK, ^TOBY '(a) BYLO WYPOLNIMOJ 3-knf TOGDA I TOLXKO TOGDA,KOGDA a | WYPOLNIMAQ knf. eSLI a 2 A NE knf, TO POLOVIM '(a) =a. eSLI VE a | knf D1 D2 : : : Ds OT PEREMENNYH x1; x2; : : : ; xn ; TOPREOBRAZUEM EE W 3-knf '(a) = F1 F2 : : : Fs SLEDU@]IM OBRAZOM.

pUSTXY = fy1; y2; : : : g | NEKOTORYE PEREMENNYE, KOTORYE NE WSTRE^A@TSQ Wknf a. rASSMOTRIM 4 SLU^AQ.1) eSLI Di = ti;1 _ ti;2 _ ti;3; TO POLOVIM Fi = Di.2) eSLI Di = ti;1 _ ti;2; TO POLOVIM Fi = (ti;1 _ ti;2 _ yj ) (ti;1 _ ti;2 _ yj );GDE yj 2 Y . zAMETIM, ^TO Fi = 1 () Di = 1.|,,|-|--...:3.3--.54.3) eSLI Di = ti ; TO POLOVIMFi = (ti _ yk _ yl)(ti _ yk _ yl ) (ti _ yk _ yl )(ti _ yk _ yl );GDE yk 6= yl . oPQTX Fi = 1 () Di = 1.4) pUSTX Di = t1 _ t2 _ : : : _ tm I m > 4.pOLOVIMFi = (t1 _ t2 _ y1)(y1 _ t3 _ y2)(y2 _ t4 _ y3) : : :: : : (ym;4 _ tm;2 _ ym;3)(ym;3 _ tm;1 _ tm ); (18)GDE WSE yj RAZLI^NY.lEMMA.

eSLI Fi = 1 TO I Di = 1 eSLI Di = 1 TO SU]ESTWUETNABOR ZNA^ENIJ PEREMENNYH y1; y2; : : : ; ym;3 TAKOJ ^TO Fi = 1dOKAZATELXSTWO pUSTX ~ = (1; : : : ; n)|NABOR ZNA^ENIJ PEREMENNYH x1; : : : ; xn IZ Di I ~ = (1; : : : ; m;3 )|NABOR ZNA^ENIJ PEREMENNYH y1; : : : ; ym;3. pUSTX Fi(~; ~) = 1, TO ESTX WSE SKOBKI W Fi NA NABORE(~; ~) RAWNY 1. eSLI 1 = 0, TO t1(~) _ t2(~) = 1 I Di(~) = 1. eSLIm;3 = 1, TO tm;1 (~) _ tm(~) = 1 I Di(~) = 1. eSLI VE 1 = 1 I m;3 = 0,TO NAJDETSQ k TAKOE, ^TO k = 1, k+1 = 0.

tAK KAK k _ tk+2 _ k+1 = 1,TO W \TOM SLU^AE tk+2(~) = 1 I Di(~) = 1. sLEDOWATELXNO, ESLI Fi = 1,TO I Di = 1. oBRATNO PUSTX Di(~) = 1. tOGDA SU]ESTWUET tk TAKOE, ^TOtk (~) = 1. eSLI k = 1 ILI k = 2, TO WYBEREM 1 = 2 = : : : = m;3 = 0.pRI \TOM Fi (~; ~) = 1. eSLI k = m ; 1 ILI k = m, TO WYBEREM1 = 2 = : : : = m;3 = 1. pRI \TOM OPQTX Fi (~; ~) = 1. w OSTALXNYHSLU^AQH POLOVIM 1 = 2 = : : : = k;2 = 1, k;1 = k = : : : = m;3 = 0:sNOWA POLU^IM Fi (~; ~) = 1.

lEMMA DOKAZANA.pRODELAEM UKAZANNYE WY[E W PUNKTAH 2)-4) ZAMENY Di NA Fi,ISPOLXZUQ DLQ RAZNYH Di RAZNYE PEREMENNYE yj . tOGDA PO LEMME POLU^AEM, ^TO ESLI 3-knf F1 F2 : : : Fs RAWNA 1 NA KAKOM-TO NABORE, TO NATOM VE NABORE RAWNA 1 I knf D1 D2 : : : Ds, I OBRATNO, ESLI knfD1 D2 : : : Ds RAWNA 1 NA NEKOTOROM NABORE, TO SU]ESTWUET NABOR, NAKOTOROM 3-knf F1 F2 : : : Fs TAKVE RAWNA 1. tAKIM OBRAZOM 3-knfF1 F2 : : : Fs WYPOLNIMA TOGDA I TOLXKO TOGDA, KOGDA WYPOLNIMA knfD1 D2 : : : Ds, TO ESTX NA[E PREOBRAZOWANIE QWLQETSQ SWEDENIEM ZADA^Iwyp K ZADA^E 3-wyp.rASPOZNATX, QWLQETSQ LI WHODNOE SLOWO a 2 A knf MOVNO ZAPOLINOMIALXNOE OT DLINY a WREMQ. pREOBRAZOWATX WSE Di W Fi TAKVEMOVNO ZA POLINOMIALXNOE WREMQ. pO\TOMU MY IMEEM POLINOMIALXNOESWEDENIE ZADA^I wyp K ZADA^E 3-wyp.

pOSKOLXKU ZADA^A wyp QWLQETSQ NP -POLNOJ I 3-wyp 2 NP , TO PO TEOREME POLU^AEM, ^TO ZADA^A3-wyp QWLQETSQ NP -POLNOJ.pOSMOTRIM, NELXZQ LI W POSLEDNEJ TEOREME ZAMENITX 3 NA 2.,.,,.55.oPREDELENIE. knf, U KOTOROJ W KAVDOM DIZ_@NKTE NE BOLEE 2LITERALOW, BUDEM NAZYWATX 2-knf.zADA^A 2-WYPOLNIMOSTX (2-wyp).wHODNOJ ALFAWIT TOT VE, ^TO I W ZADA^E wyp.wOPROS WERNO LI, ^TO WHODNOE SLOWO | \TO 2-knf, KOTORAQ WYPOLNIMA.tEOREMA. dLQ ZADA^I wyp SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO ESTX wyp 2 PdOKAZATELXSTWO pROWERITX, QWLQETSQ LI WHODNOE SLOWO 2-knf,MOVNO ZA POLINOMIALXNOE WREMQ. pO\TOMU BUDEM S^ITATX, ^TO NAM UVEDANA 2-knf D1 D2 : : : Ds I TREBUETSQ WYQSNITX, WYPOLNIMA LI ONA.pUSTX DIZ_@NKTY D0 = xi _ t1 I D00 = xi _ t2 IME@T PROTIWOPOLOVNYELITERALY xi I xi (PRI \TOM MOVET BYTX t1 = ? ILI t2 = ?).

tOGDAREZOLXWENTOJ DIZ_@NKTOW D0 I D00 PO xi BUDEM NAZYWATX DIZ_@NKT D =t1 _ t2 (ESLI t1 = t2, TO t1 _ t2 = t1). eSLI t1 = ? I t2 = ?, TO POLOVIMD 0.lEMMA. dLQ L@BYH FORMUL A I B WYPOLNQETSQ RAWENSTWO(xi _ A)(xi _ B ) = (xi _ A)(xi _ B )(A _ B ):dOKAZATELXSTWO eSLI PRAWAQ ^ASTX RAWNA 1, TO, O^EWIDNO, I LEWAQ^ASTX RAWNA 1. eSLI PRAWAQ ^ASTX RAWNA 0, TO LIBO xi _ A = 0, LIBOxi _ B = 0, LIBO A _ B = 0. w PERWYH DWUH SLU^AQH LEWAQ ^ASTX RAWNA0.

w POSLEDNEM SLU^AE A = 0 I B = 0. tOGDA LEWAQ ^ASTX RAWNA (xi _0)(xi _ 0) = xi xi = 0. lEMMA DOKAZANA.lEMMA ( ) POKAZYWAET, ^TO DOBAWLENIE K 2-knf REZOLXWENTY L@BOJ PARY DIZ_@NKTOW NE MENQET FUNKCI@, REALIZUEMU@ 2-knf. bUDEMPROSMATRIWATX WSE PARY DIZ_@NKTOW TEKU]EJ 2-knf I STROITX IHREZOLXWENTY. eSLI OKAVETSQ, ^TO NEKOTORAQ REZOLXWENTA OTSUTSTWUET WTEKU]EJ 2-knf, TO DOBAWIM EE I NA^NEM PROSMOTR SNA^ALA. tAK BUDEMDELATX DO TEH POR, POKA NE OKAVETSQ, ^TO WSE REZOLXWENTY TEKU]EJ2-knf UVE SODERVATSQ W NEJ.eSLI PRI \TOM BUDET POROVDENA REZOLXWENTA 0, TO WYDAEM OTWET: \iSHODNAQ 2-knf NEWYPOLNIMA", INA^EWYDAEM OTWET: \iSHODNAQ 2-knf WYPOLNIMA".lEMMA.

aLGORITM OBQZATELXNO OSTANOWITSQ I RABOTAET POLINOMIALXNOE WREMQdOKAZATELXSTWO eSLI DLINA ISHODNOJ 2-knf RAWNA n, TO W NEJNE BOLEE n PEREMENNYH, IZ KOTORYH MOVNO POSTROITX NE BOLEE (n + 1)2DIZ_@NKTOW S ODNOJ ILI DWUMQ PEREMENNYMI. pO\TOMU POISK NOWYHREZOLXWENT BUDET POWTORQTXSQ NE BOLEE (n + 1)2 RAZ, PRI \TOM ^ISLO:2-(-2-)...-..56PROSMATRIWAEMYH PAR DIZ_@NKTOW NE PREWOSHODIT (n + 1)4. oTS@DASLEDUET UTWERVDENIE LEMMY.lEMMA. aLGORITM PRAWILXNO RE[AET ZADA^U wypdOKAZATELXSTWO 1) pUSTX K = D1D2 : : : Ds| ISHODNAQ 2-knfI PUSTX W KONE^NOJ knf K 0 ESTX SOMNOVITELX 0. pO LEMME K = K 0 I,SLEDOWATELXNO, K 0, TO ESTX K NEWYPOLNIMA. 2) pUSTX W KONE^NOJ2-knf K 0 NET 0.

pO POSTROENI@ K 0 ZAMKNUTA OTNOSITELXNO WZQTIQREZOLXWENT, TO ESTX REZOLXWENTA L@BYH DWUH DIZ_@NKTOW IZ K 0 SNOWASODERVITSQ W K 0 . dOKAVEM, ^TO L@BAQ 2-knf S TAKIM SWOJSTWOM WYPOLNIMA. dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU PEREMENNYH nW 2-knf K 0 .bAZIS INDUKCII n = 1. tOGDA K 0 = xi ILI K 0 = x0i .

w L@BOMSLU^AE K 0 WYPOLNIMA.iNDUKTIWNYJ PEREHOD pUSTX UTWERVDENIE WERNO DLQ 2-knf Sn < m PEREMENNYMI I PUSTX W K 0 IMEETSQ m PEREMENNYH x1; x2; : : : ; xm .tOGDAK 0 = (xm _ t1)(xm _ t2) : : : (xm _ tk )(xm _ t01)(xm _ t02) : : :: : : (xm _ t0l ) C1 C2 : : : Cr ; (19)GDE ti ; t0j | LITERALY, LIBO 0, I C1 C2 : : : Cr | 2-knf S PEREMENNYMIx1; x2; : : : ; xm;1 , ZAMKNUTAQ OTNOSITELXNO WZQTIQ REZOLXWENT. pO PREDPOLOVENI@ INDUKCII SU]ESTWUET NABOR ~ = (1; : : : ; m;1 ), NA KOTOROMC1 C2 : : : Cr RAWNO 1.

eSLI BY SU]ESTWOWALI ti I t0j TAKIE, ^TO ti(~) = 0I t0j (~) = 0, TO BYLO BY I ti (~) _ t0j (~) = 0. nO ti _ t0j | REZOLXWENTADIZ_@NKTOW xm _ ti I xm _ t0j . tAK KAK 2-knf K 0 ZAMKNUTA OTNOSITELXNOWZQTIQ REWOLXWENT, TO ti _ t0j SODERVITSQ SREDI C1; C2; : : : ; Cr . nO \TOPROTIWORE^IT TOMU, ^TO Cv (~) = 1 PRI WSEH v. sLEDOWATELXNO, LIBO WSEti(~) = 1, LIBO WSE t0j (~) = 1. w PERWOM SLU^AE K 0 WYPOLNIMA NA NABORE(~; 0), WO WTOROM | NA NABORE (~; 1):tEOREMA POLNOSTX@ DOKAZANA.2-.:.57.tEOREMA. zADA^A klika QWLQETSQ NP POLNOJ-.dOKAZATELXSTWO pOKAVEM, ^TO ZADA^A wyp POLINOMIALXNO SWODITSQ K ZADA^E klika. dLQ \TOGO KAVDOMU SLOWU a W ALFAWITE QZYKAwyp SOPOSTAWIM PARU '(a) = (G; k), GDE G | NEKOTORYJ GRAF I k |NATURALXNOE ^ISLO, TAK, ^TOBY W G SU]ESTWOWALA KLIKA S k WER[INAMITOGDA I TOLXKO TOGDA, KOGDA a | WYPOLNIMAQ knf.

eSLI a | NE knf,TO POLOVIM '(a) = (G2; 2), GDE G2 | GRAF S 2 WER[INAMI I BEZ REBER(O^EWIDNO, W G2 NET KLIKI S 2 WER[INAMI). pUSTX TEPERX a | knf Ia = D1 D2 : : : Ds, GDE Di = ti;1 _ ti;2 _ : : : _ ti;mi | DIZ_@NKTY. pOSTROIMGRAF '(a) = Ga = (V; E ) S MNOVESTWOM WER[IN V I MNOVESTWOM REBERE SLEDU@]IM OBRAZOM. kAVDOMU LITERALU ti;j IZ a SOPOSTAWIM WER[INUvi;j I BUDEM S^ITATX, ^TO(vi1;j1 ; vi2;j2 ) 2 E () (i1 6= i2) I (ti2;j2 6= ti1;j1 ):pOLOVIM k = s, GDE s | ^ISLO DIZ_@NKTOW W a.lEMMA. w Ga ESTX KLIKA S s WER[INAMI TOGDA I TOLXKO TOGDAKOGDA knf a WYPOLNIMAdOKAZATELXSTWO pUSTX knf a PRINIMAET ZNA^ENIE 1 NA NABORE~.