Алексеев - Сложность алгоритмов (1123759), страница 10
Текст из файла (страница 10)
tOT FAKT ^TO W Kp(n) SOSTOQNIE q0 WYRAVAETSQ WWIDE knf F3 = z0p(n)rASSMOTRIM TEPERX BOLEE PODROBNO PROGRAMMU MA[INY M . pREDSTAWIM EE KOMANDY W WIDE aj qk ! a'(j;k)q (j;k) R(j; k), GDE R(j; k) = ;1; 0ILI 1 SOOTWETSTWENNO, DLQ SDWIGA WLEWO, OSTAWLENIQ GOLOWKI NA MESTEI SDWIGA WPRAWO.lEMMA. pRI USLOWII ^TO NABOR PEREMENNYH xti;j ; yit; zkt KORREKTNOZADAET KONFIGURACII K0; K1; : : : ; Kp(n) TOT FAKT ^TO KAVDAQ KONFIGURACIQ Kj+1 POLU^AETSQ IZ Kj PO PROGRAMME MA[INY M MOVNOWYRAZITX W WIDE knf F4 DLINY NE BOLEE p4(n) GDE p4 NEKOTORYJPOLINOM,,.,,,-,,.52|dOKAZATELXSTWO |TOT FAKT WYRAVAETSQ FORMULOJ;1 p(n)m lt ttF40 = &p(n)t=0 &i=;p(n) &j=0 &k=0 (yi ξj &zk !t+1t+1! xt+1i;'(j;k) &z (j;k) &yi+R(j;k)) &;1 p(n)t& &p(n)yit ! &mj=0(xt+1t=0 &i=;p(n) (i;j xi;j )): (17)pERWAQ ^ASTX \TOJ FORMULY WYRAVAET IZMENENIE INFORMACII W OBOZREWAEMOJ Q^EJKE, IZMENENIE SOSTOQNIQ I SDWIG GOLOWKI, WTORAQ ^ASTXWYRAVAET TOT FAKT, ^TO SIMWOLY WO WSEH Q^EJKAH, KROME OBOZREWAEMOJ,NE IZMENQ@TSQ.
wYRAVENIE W PERWOJ SKOBKE W F40 | \TO FUNKCIQ OT 6PEREMENNYH I EE (KAK L@BU@ FUNKCI@ ALGEBRY LOGIKI, OTLI^NU@ OTKONSTANTY 1) MOVNO PREDSTAWITX W WIDE knf NEKOTOROJ DLINY L1.aNALOGI^NO MOVNO PREDSTAWITX W WIDE knf KONSTANTNOJ DLINY L2FUNKCI@ OT 2m + 1 PEREMENNYH, STOQ]U@ WO WTOROJ SKOBKE. pRI \TOMF40 PREOBRAZUETSQ W knf K4 DLINY p(n) (2p(n) + 1) m l L1 + p(n) (2p(n) + 1) L2 6 p4(n), GDE p4 | NEKOTORYJ POLINOM.pOLOVIM Fa = F1 F2 F3 F4. tOGDA Fa | knf I PO LEMMAMNA NABORE PEREMENNYH xti;j ; yit; zkt ONA ISTINNA TOGDA I TOLXKO TOGDA,KOGDA PEREMENNYE KORREKTNO ZADA@T NEKOTOROE WY^ISLENIE MA[INYM , PRIWODQ]EE W SOSTOQNIE q0 = \DA", DLQ WHODNOJ PARY (a; b), GDE b| KAKOE-NIBUDX SLOWO IZ B TAKOE, ^TO jbj 6 q(jaj).
tAKIM OBRAZOM FaISTINNA HOTQ BY NA ODNOM NABORE (T.E. WYPOLNIMA) W TOM I TOLXKO WTOM SLU^AE, ESLI ISTINNA PRAWAQ ^ASTX W (1) I, SLEDOWATELXNO, ESLIa 2 L. pOLU^AEM, ^TO Fa | ISKOMAQ knf. eE DLINA NE PREWOSHODITNEKOTOROGO POLINOMA OT n.
pRI \TOM NETRUDNO PONQTX, ^TO PO DANNOMUSLOWU a (I FIKSIROWANNOJ PROGRAMME MA[INY M ) \TA knf Fa = F1 F2 F3 F4 WYPISYWAETSQ ZA WREMQ, OGRANI^ENNOE POLINOMOM OT EE DLINY,I, SLEDOWATELXNO, OGRANI^ENNOE POLINOMOM OT DLINY SLOWA a. tAKIMOBRAZOM, OTOBRAVENIE a ! Fa QWLQETSQ POLINOMIALXNYM SWEDENIEMQZYKA L K QZYKU wyp. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
