В.Б. Алекссев - Сложные алгоритмы (1132790), страница 10
Текст из файла (страница 10)
bUDEM S^ITATX, ^TO NA^ALXNAQ KONFIGURACIQ MA[INY M1 QWLQETSQ STANDARTNOJ, TO ESTX PARA(a; b) PREDSTAWLQETSQ NA LENTE DWUMQ SLOWAMI a I b S ODNOJ RAZDELQ@]EJQ^EJKOJ, W KOTOROJ STAWITSQ PUSTOJ SIMWOL , GOLOWKA OBOZREWAET SAMYJ LEWYJ SIMWOL SLOWA a I MA[INA NAHODITSQ W NA^ALXNOM SOSTOQNIIq1. tOGDA WREMQ RABOTY M1 NA PROIZWOLXNOJ PARE (a; b) NE PREWY[AETp0(jaj + jbj +1).
bUDEM S^ITATX, ^TO MA[INA M1 OSTANAWLIWAETSQ TOLXKOW ODNOM IZ DWUH ZAKL@^ITELXNYH SOSTOQNIJ, PRI^EM ZAKL@^ITELXNOE(-..49)-SOSTOQNIE q0 MA[INY M1 SOOTWETSTWUET OTWETU \DA" (KAKOE SOSTOQNIESOOTWETSTWUET OTWETU \NET" DLQ NAS BUDET NE WAVNO).pUSTX DANO a 2 A I jaj = n.
tOT FAKT, ^TO a 2 L, RAWNOSILEN WSOOTWETSTWII S () TOMU, ^TO NAJDETSQ SLOWO b 2 B S DLINOJ jbj 6 q(n)TAKOE, ^TO MA[INA M1 NA^AW RABOTU NA PARE (a; b) PRIDET W SOSTOQNIEq0 = \DA". pRI \TOM WREMQ RABOTY M1 NA PARE (a; b) NE PREWOSHODITp0(n + q(n) + 1) = p(n), GDE p | NEKOTORYJ POLINOM. oTMETIM, ^TOMOVNO S^ITATX, ^TO WO WSEH POLINOMAH WSE KO\FFICIENTY NEOTRICATELXNY.
tOGDA p(n) > n + 1 + q(n).nESKOLXKO MODIFICIRUEM PROGRAMMU MA[INY M1. a IMENNO, ESLI MA[INA M1 NAHODITSQ W NEKOTOROM ZAKL@^ITELXNOM SOSTOQNII IGOLOWKA OBOZREWAET NEKOTORYJ SIMWOL, TO PUSTX MA[INA M1 OSTAWLQETW Q^EJKE TOT VE SIMWOL, GOLOWKA NIKUDA NE SDWIGAETSQ I MA[INAOSTAETSQ W TOM VE SOSTOQNII. tO ESTX REALXNO NI^EGO NE PROISHODIT,NO FORMALXNO MA[INA PRODOLVAET RABOTATX BESKONE^NO. pOLU^ENNU@MA[INU OBOZNA^IM M . tOGDA DLQ SLOWA a 2 A DLINY jaj = n IMEEM:a 2 L () 9b 2 B (jbj 6 q(n) I MA[INA M , ZAPU]ENNAQ NA PARE (a; b),W MOMENT WREMENI p(n) BUDET NAHODITXSQ W SOSTOQNII q0 = \DA").nA[A DALXNEJ[AQ CELX | ZAPISATX PRAWU@ ^ASTX W \TOJ RAWNOSILXNOSTI W WIDE knf Fa(x1; : : : ; xm ) OT NEKOTORYH PEREMENNYH, TAK^TOBY FORMULA Fa BYLA WYPOLNIMA TOGDA I TOLXKO TOGDA, KOGDA \TAPRAWAQ ^ASTX ISTINNA.
pEREPI[EM ( ) BOLEE PODROBNO:a 2 L () 9b 2 B 9K0; K1; : : : ; Kp(n) (jbj 6 q(n) I K0; K1; : : : ; Kp(n)| KONFIGURACII MA[INY M TAKIE, ^TO K0 | NA^ALXNAQ KONFIGURACIQ DLQ PARY (a; b), SOSTOQNIE W Kp(n) ESTX q0 I DLQ KAVDOGO j =0; 1; : : : ; p(n) ; 1 KONFIGURACIQ Kj+1 POLU^AETSQ IZ Kj PO PROGRAMMEMA[INY M ).pUSTX Q^EJKI LENTY W M ZANUMEROWANY CELYMI ^ISLAMI SLEWANAPRAWO I Q^EJKA, S KOTOROJ GOLOWKA NA^INAET RABOTATX (I S KOTOROJNA^INAETSQ SLOWO a), IMEET NOMER 0.
tOGDA ZA p(n) TAKTOW GOLOWKA NEMOVET POPASTX W Q^EJKI S NOMERAMI MENX[E ;p(n) I BOLX[E p(n). pO\TOMU MOVNO S^ITATX, ^TO KONFIGURACII K0; K1; : : : ; Kp(n) OPREDELENYTOLXKO NA ZONE [;p(n); p(n)] LENTY.pUSTX MA[INA M IMEET LENTO^NYJ ALFAWIT D = fd0; d1; : : : ; dm g,GDE d0 = , PRI \TOM A D I B D. pUSTX Q = fq0; q1; : : : ; ql g | MNOVESTWO SOSTOQNIJ MA[INY M , PRI^EM q1 | NA^ALXNOE SOSTOQNIE I q0 =\DA". wWEDEM BULEWSKIE PEREMENNYE xti;j ; yit; zkt , GDE i = ;p(n); ;p(n) +1; : : : ; p(n); j = 0; 1; : : : ; m; k = 0; 1; : : : ; l; t = 0; 1; : : : ; p(n) I PRIDADIMIM SLEDU@]IJ SMYSL:50dj ;xti;j = \I" () W i-J Q^EJKE W KONFIGURACII Kt NAHODITSQ SIMWOLyit = \I" () W KONFIGURACII Kt GOLOWKA OBOZREWAET Q^EJKU SNOMEROM i;zkt = \I" () W KONFIGURACII Kt SOSTOQNIE qk .iSKOMU@ FORMULU Fa MY BUDEM STROITX KAK knf OT WSEH \TIHPEREMENNYH Fa(fxti;j g; fyitg; fzkt g) PRI^EM TAK, ^TOBY ONA BYLA WYPOLNIMA TOGDA I TOLXKO TOGDA, KOGDA PRAWAQ ^ASTX W ( ) ISTINNA.
dLQ\TOGO DOSTATO^NO, ^TOBY knf Fa BYLA ISTINNA NA NEKOTOROM NABORETOGDA I TOLXKO TOGDA, KOGDA: 1) \TOT NABOR KORREKTNO ZADAET NABORKONFIGURACIJ K0; K1; : : : ; Kp(n) MA[INY M ; 2) PRI \TOM KONFIGURACIQK0 QWLQETSQ PRAWILXNOJ NA^ALXNOJ KONFIGURACIEJ DLQ PARY (a; b), GDEa | ZADANNOE SLOWO I b 2 B | KAKOE-NIBUDX SLOWO DLINY NE BOLEEq(n); 3) W KONFIGURACII Kp(n) SOSTOQNIE q0 = \DA"; 4) DLQ KAVDOGOj = 0; 1; : : : ; p(n);1 KONFIGURACIQ Kj+1 POLU^AETSQ IZ Kj PO PROGRAMMEMA[INY M .rASSMOTRIM SWOJSTWO 1). eSLI ZADANA KONFIGURACIQ Kt, TO PO NEJODNOZNA^NO OPREDELQ@TSQ ZNA^ENIQ PEREMENNYH xti;j ; yit; zkt PRI DANNOMt.
oBRATNOE NEWERNO, POSKOLXKU, NAPRIMER, ESLI SRAZU 2 PEREMENNYExi;j1 I xi;j2 ISTINNY, TO \TO OZNA^AET, ^TO W KONFIGURACII Kt W Q^EJKEi DOLVNY NAHODITXSQ I SIMWOL dj1 I SIMWOL dj2 . lEGKO PONQTX, ^TOUSLOWIE KORREKTNOGO ZADANIQ KONFIGURACIJ WYRAVAETSQ SLEDU@]IMOBRAZOM: PRI KAVDOM t DLQ KAVDOGO i ROWNO ODNA IZ PEREMENNYH xti;j =\I"; PRI KAVDOM t ROWNO ODNA IZ PEREMENNYH yit = \I" I PRI KAVDOM tROWNO ODNA IZ PEREMENNYH zkt = \I".pUSTX H (v1; : : : ; vs ) | FUNKCIQ ALGEBRY LOGIKI, RAWNAQ 1 TOGDAI TOLXKO TOGDA, KOGDA SREDI v1; : : : ; vs ROWNO 1 EDINICE.lEMMA. fUNKCI@ H (v1; : : : ; vs) MOVNOPREDSTAWITX W WIDE knfS DLINOJ ^ISLOM LITERALOW NE BOLEE s2dOKAZATELXSTWO lEGKO PROWERITX, ^TOH (v1; : : : ; vs ) = (v1 _ v2 _ : : : _ vs )&(&i6=j (vi _ vj )):dLINA \TOJ knf RAWNA s + s(s2;1) 2 = s2.lEMMA.
tOT FAKT ^TO NABOR PEREMENNYH xti;j ; yit; zkt KORREKTNOZADAET KONFIGURACII K0; K1; : : : ; Kp(n) MOVNO WYRAZITX W WIDE knfF1 DLINY NE BOLEE p1(n) GDE p1 NEKOTORYJ POLINOMdOKAZATELXSTWO |TOT FAKT WYRAVAETSQ FORMULOJ()..,,,|..p(n)tttF10 = &p(n)t=0 &i=;p(n) H (xi;0 ; xi;1 ; : : : ; xi;m ) &p(n)tttt tt& &p(n)t=0 H (y;p(n) ; y;p(n)+1 ; : : : ; yp(n) ) & &t=0 H (z0 ; z1 ; : : : ; zl ): (15)51pREDSTAWLQQ KAVDU@ FUNKCI@ H S POMO]X@ knf W SOOTWETSTWII SLEMMOJ ( ), POLU^IM knf F1 DLINY(p(n)(2p(n)+1)(m +1)2 +(p(n)+1)(2p(n)+1)2 +(p(n)+1)(l +1)2 6 p1(n);GDE p1(n) | NEKOTORYJ POLINOM.lEMMA.
pRI USLOWII ^TO NABOR PEREMENNYH x0i;j ; yi0; zk0 KORREKTNO ZADAET KONFIGURACI@ K0; TOT FAKT ^TO K0 QWLQETSQ PRAWILXNOJNA^ALXNOJ KONFIGURACIEJ DLQ PARY (a; b) GDE a ZADANNOE SLOWO Ib 2 B KAKOE NIBUDX SLOWO DLINY NE BOLEE q(n) MOVNO WYRAZITX WWIDE knf F2 DLINY NE BOLEE p2(n) GDE p2 NEKOTORYJ POLINOMdOKAZATELXSTWO pUSTX a = dj1 dj2 : : : djn I b 2 B , GDE B =fdr1 ; dr2 ; : : : ; drw g.
tOGDA UKAZANNYJ W LEMME FAKT WYRAVAETSQ FORMULOJ,-,,||-,,|..F2 = x00;j1 &x01;j2 & : : : &x0n;1;jn &x0n;0 &000& (&;i=1;p(n)x0i;0) & &n+q(n)i=n+1 (xi;r1 _ xi;r2 _ : : : _ xi;rw ) &n+q(n);1 00& (&p(n)xi;0 _ x0i+1;0): (16)i=n+q(n)+1 xi;0) & &i=n+1 (pOSLEDNQQ SKOBKA x0i;0 _ x0i+1;0 = x0i;0 ! x0i+1;0 OZNA^AET, ^TO ESLI W Q^EJKEi STOIT PUSTOJ SIMWOL, TO I W SLEDU@]EJ Q^EJKE DOLVEN STOQTX PUSTOJSIMWOL, TO ESTX SLOWO b NE MOVET IMETX RAZRYWOW. fORMULA F2 QWLQETSQknf S DLINOJn + 1 + p(n) + q(n) w + p(n) ; n ; q(n) ; 1 + (q(n) ; 1) 2 6 p2(n);GDE p2 | NEKOTORYJ POLINOM.sLEDU@]EE UTWERVDENIE O^EWIDNO.lEMMA.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
