В.Б. Алексеев - Электронный коспект лекций (1158874), страница 10
Текст из файла (страница 10)
tAK KAK L 2 P , TO PREDIKAT Q RASPOZNAETSQZA WREMQ, POLINOMIALXNO ZAWISQ]EE OT jaj, A ZNA^IT I OT jaj + jbj, TOESTX Q 2 P . pRI \TOM, O^EWIDNO, ^TO DLQ L@BOGO a 2 A SPRAWEDLIWOSOOTNO[ENIEa 2 L () 9b 2 B (jbj 6 1&Q(a; b))(SERTIFIKAT b ZDESX NE ZAWISIT OT a). tAKIM OBRAZOM, L 2 NP . tEOREMADOKAZANA..48tEOREMA kUKAoPREDELENIE. qZYKL (ZADA^A RASPOZNAWANIQ) NAZYWAETSQNP -TRUDNYM, ESLI L@BOJ QZYK L1 IZ NP POLINOMIALXNO SWODITSQ KL.w SOOTWETSTWII S TEOREMOJ ( ), ESLI QZYK L QWLQETSQ NP -TRUDNYMI L 2 P , TO NP P I S U^ETOM TEOREMY ( ) P = NP . i OBRATNO, ESLIP 6= NP , TO L 2= P . tAKIM OBRAZOM, NP -TRUDNOSTX QZYKA QWLQETSQKOSWENNYM SWIDETELXSTWOM TOGO, ^TO L 2= P (KOSWENNYM POTOMU, ^TOWEROQTNO P 6= NP , NO \TO POKA NE DOKAZANO I NE OPROWERGNUTO).oPREDELENIE.
qZYK L (ZADA^A RASPOZNAWANIQ) NAZYWAETSQNP -POLNYM, ESLI L 2 NP I L QWLQETSQ NP -TRUDNYM.eSTESTWENNO WOZNIKAET WOPROS O TOM, SU]ESTWU@T LI TAKIE \UNIWERSALXNYE" ZADA^I W KLASSE NP , K KOTORYM POLINOMIALXNO SWODQTSQWSE ZADA^I IZ NP . oKAZYWAETSQ, ^TO SU]ESTWU@T. pERWYJ REZULXTATTAKOGO RODA BYL USTANOWLEN s. kUKOM.tEOREMA (s. kUK). zADA^A wyp O WYPOLNIMOSTI knf QWLQETSQ NP POLNOJdOKAZATELXSTWO wY[E UVE DOKAZANO, ^TO wyp 2 NP .
pO\TOMUNADO DOKAZATX, ^TO L@BOJ QZYK L IZ NP POLINOMIALXNO SWODITSQ Kwyp. pUSTX L 2 NP I L A. |TO OZNA^AET, ^TO SU]ESTWU@T POLINOMq(n), ALFAWIT B I PREDIKAT Q(x; y) : A B ! f\I", \L"g TAKIE, ^TOQ(x; y) 2 P I DLQ L@BOGO SLOWA a 2 A SPRAWEDLIWOa 2 L () 9b(jbj 6 q(jaj)&Q(a; b)):nAM NADO POKAZATX, ^TO L POLINOMIALXNO SWODITSQ K wyp. |TOOZNA^AET, ^TO NADO POSTROITX TAKOE PREOBRAZOWANIE S POLINOMIALXNOJSLOVNOSTX@ ' : A ! C , GDE C | ALFAWIT ZADA^I wyp, ^TO a 2L () '(a) = Fa | WYPOLNIMAQ knf OT NEKOTORYH PEREMENNYH.tAK KAK Q(x; y) 2 P , TO SU]ESTWUET MA[INA tX@RINGA M , KOTORAQ RASPOZNAET PREDIKAT Q(x; y) ZA WREMQ (^ISLO [AGOW), NE PREWOSHODQ]EE NEKOTOROGO POLINOMA p0 OT DLINY WHODA. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
