Алексеев - Сложность алгоритмов (1123759), страница 14
Текст из файла (страница 14)
eSLI m > k, TO DLQ PARY (G; k) W ZADA^E klikaOTWET "DA", INA^E OTWET "NET". pOLU^AEM POLINOMIALXNYJ ALGORITMDLQ ZADA^I klika. tAK KAK klika NP -POLNA, TO IZ SU]ESTWOWANIQPOLINOMIALXNOGO ALGORITMA DLQ mk SLEDUET SU]ESTWOWANIE POLINOMIALXNOGO ALGORITMA DLQ WSEH ZADA^ IZ NP , TO ESTX mk NP -TRUDNA.pREVDE, ^EM ISSLEDOWATX PRIBLIVENNYE ALGORITMY DLQ mk, DOKAVEM LEMMU.oPREDELENIE.2 pUSTX G2 =2 (V; E ) | NEORIENTIROWANNYJ GRAF.oPREDELIM GRAF G = (V ; E ) KAK GRAF S MNOVESTWOM WER[INV 2 = V V = f(u; v)ju 2 V; v 2 V g I MNOVESTWOM REBER E 2 =f(u1; v1); (u2; v2)g, GDE LIBO u1 = u2 I (v1; v2 ) 2 E , LIBO (u1; u2) 2 E .lEMMA. eSLI W G ESTX KLIKA RAZMERA k TO W G2 ESTX KLIKARAZMERA k2 eSLI W G2 ESTX KLIKA RAZMERA m GDE (k ; 1)2 < m 6 k2TO W G ESTX KLIKA RAZMERA k I W G2 ESTX KLIKA RAZMERA k2dOKAZATELXSTWO pUSTX W G ESTX KLIKA C = fv1; v2; : : : ; vk g.tOGDA IZ OPREDELENIQ LEGKO PROWERITX, ^TO C 2 = f(u; v)ju 2 C; v 2 C g| KLIKA W G2 RAZMERA k2.
oBRATNO, PUSTX W G2 ESTX KLIKA D RAZMERA m.wER[INAMI W D QWLQ@TSQ PARY (u; v) 2 V 2. pUSTX V = fv1; v2; : : : ; vn gI PUSTX Di|MNOVESTWO WER[IN (u; v) IZ D, U KOTORYH u = vi . pOOPREDELENI@ GRAFA G2 WER[INY (u; v0 ) I (u; v") SMEVNY W G2 TOGDAI TOLXKO TOGDA, KOGDA (v0 ; v") 2 E . pO\TOMU WTORYE KOORDINATY WSEHWER[IN IZ Di OBRAZU@T KLIKU W G. eSLI jDij > k HOTQ BY DLQ ODNOGOi, TO POLU^AEM W G KLIKU RAZMERA k. w PROTIWNOM SLU^AE jDij 6 k ; 1DLQ WSEH i I, SLEDOWATELXNO, ^ISLO NEPUSTYH Di NE MENEE k, TAK KAKm > (k ; 1)2.
wYBEREM W KAVDOM NEPUSTOM Di L@BU@ WER[INU (vi; vdi ).tAK KAK WSE \TI WER[INY PRINADLEVAT ODNOJ KLIKE D, TO WSE ONISMEVNY. tAK KAK vi =6 vj PRI i =6 i, TO (vi ; vj ) 2 E DLQ WSEH PERWYHKOORDINAT WYBRANNYH WER[IN PO OPREDELENI@ GRAFA G2. pOSKOLXKU::(-)..,.,,,..72^ISLO WYBRANNYH WER[IN m > k, TO POLU^AEM KLIKU W G RAZMERA k.pOSLEDNEE UTWERVDENIE LEMMY SLEDUET IZ PERWOGO.sLEDSTWIE1.
mO]NOSTX MAKSIMALXNOJ KLIKI W G2 IMEET WIDk2 DLQ NEKOTOROGO NATUARLXNOGO ksLEDSTWIE 2. sU]ESTWUET POLINOMIALXNYJ2 ALGORITM2 KOTORYJ PO ZADANNOJ KLIKE D MO]NOSTI m W GRAFE G GDE (k ; 1) < m 6k2 STROIT KLIKU C MO]NOSTI k W GRAFE GpUSTX mALG I mmax | MO]NOSTX KLIKI, KOTORAQ STROITSQ NEKOTORYM ALGORITMOM, I MO]NOSTX MAKSIMALXNOJ KLIKI DLQ DANNOGOWHODA G. tOGDA mALG 6 mmax I" = jmALGm; mmaxj 6 1:.,-,,.maxtEOREMA. eSLI DLQ ZADA^I mk SU]ESTWUET POLINOMIALXNYJ" PRIBLIVENNYJ ALGORITM DLQ NEKOTOROGO 0 < " < 1 TO DLQ mkSU]ESTWUET POLINOMIALXNYJ " PRIBLIVENNYJ ALGORITM DLQ WSEH 0 <"<1dOKAZATELXSTWO pUSTX DLQ ZADA^I mk DLQ NEKOTOROGO 0 < " < 1IMEETSQ POLINOMIALXNYJ "|PRIBLIVENNYJ ALGORITMA" , I PUSTX 0 <r2 < 1.
wYBEREM NATURALXNOE r TAK, ^TO (1 ; ) < 1 ; ". tAKOE r SU]ESTWUET, TAK KAK 1 ; < 1. rASSMOTRIM SLEDU@]IJ ALGORITM B . pUSTXrNA WHOD POSTUPAETGRAF G. sTROIM POSLEDOWATELXNO Gr 2; G4; : : : ; G2 .r2 . pO KLIKE DpRIMENQEM K G2 ALGORITMA.pOLU^AEMKLIKUDWG"rrr;12STROIM KLIKU Dr;1 W G TAK, KAKr;W2 DOKAZATELXSTWE LEMMY. pO Dr;1ANALOGI^NO STROIM KLIKU Dr;2 W G2 I T.D.
DO KLIKI D0 W G. kLIKU D0WYDAEM W OTWET. tAK KAK r|FIKSIROWANO, TO ALGORITM B POLINOMIALEN(SM. SLEDSTWIE 2). dOKAVEM, ^TO ON QWLQETSQ -PRIBLIVENNYM.pUSTX MO]NOSTX MAKSIMALXNOJKLIKIW G RAWNA k. tOGDA MO]rr22NOSTX MAKSIMALXNOJ KLIKI W G RAWNA k PO LEMME (SM. SLEDSTWIE1).rtAK KAK ALGORITM Ap" QWLQETSQ "-PRIBLIVENNYM, TO jDrj > k2 (1 ; ").pOSKOLXKU jDi;1j > jDij DLQ WSEH i, TOpjD0j > 2r 1 ; " > k(1 ; ):sLEDOWATELXNO, ALGORITM B QWLQETSQ -PRIBLIVENNYM. tEOREMA DOKAZANA.-,-..73kLASSY PSPACE I DLOGkLASSY P I NP OPREDELQLISX ^EREZ ISPOLXZUEMOE ALGORITMOMWREMQ RABOTY. dRUGIE KLASSY MY MOVEM POLU^ITX, ESLI BUDEM RASSMATRIWATX ISPOLXZUEMU@ PAMQTX.oPREDELENIE.
kLASS PSPACE OPREDELQETSQ KAK KLASS WSEH ZADA^ RASPOZNAWANIQ (QZYKOW), DLQ KOTORYH SU]ESTWUET ALGORITM, ISPOLXZU@]IJ PAMQTX (NAPRIMER, ^ISLO Q^EEK MA[INY tX@RINGA), NEPREWOSHODQ]U@ p(n), GDE n |DLINA WHODA I p| PROIZWOLXNYJ (FIKSIROWANNYJ DLQ DANNOJ ZADA^I) POLINOM.o^EWIDNO, ^TO P PSPACE .tEOREMA. NP PSPACEdOKAZATELXSTWO pUSTX ZADA^A RASPOZNAWANIQ R(x) 2 NP . pOOPREDELENI@ KLASSA NP R(x) PREDSTAWIMO W WIDE:R(x) = 9y(jyj 6 p1(jxj)&Q(x; y));GDE jxj I jyj |DLINA SLOW x I y, p1| NEKOTORYJ POLINOM I PREDIKATQ(x; y) 2 P . pOKAVEM, ^TO DLQ WY^ISLENIQ R(x) SU]ESTWUET ALGORITMS POLINOMIALXNOJ PAMQTX@. pUSTX DAN WHOD x. wY^ISLQEM DLINU nSLOWA x.
wY^ISLQEM p1(n) I OTME^AEM W PAMQTI ZONU p1(n), NA KOTOROJPEREBIRAEM PO O^EREDI WSE SLOWA y DLINY 6 p1(n). dLQ KAVDOGO yWY^ISLQEM Q(x; y). eSLI PRI WY^ISLENII Q(x; y) HOTQ BY ODIN RAZOTWET Q(x; y) = "I"(ISTINA), TO WYDAEM OTWET "DA", INA^E WYDAEMOTWET "NET". tAK KAK jxj + jyj 6 n + p1(n) I Q 2 P , TO WREMQ WY^ISLENIQQ(x; y) DLQ ODNOGO y NE PREWOSHODIT NEKOTOROGO POLINOMA OT n. NOTOGDA I ISPOLXZUEMAQ PAMQTX NE PREWOSHODIT POLINOMA OT n. tEOREMADOKAZANA.lEMMA. eSLI ZONA RABOTY MA[INY tX@RINGA NA WHODAH DLINYn SODERVIT NE BOLEE p1(n) Q^EEK GDE p1(n) NEKOTORYJ POLINOM WLENTO^NOM ALFAWITE MA[INY r SIMWOLOW U MA[INY k SOSTOQNIJ IMA[INA OSTANAWLIWAETSQ NA L@BOM WHODE TO MAKSIMALXNOE WREMQRABOTY t(n) MA[INY NA SLOWAH DLINY n UDOWLETWORQET NERAWENSTWUt(n) 6 rp1(n)p1(n) k 6 2p(n);GDE p(n) NEKOTORYJ POLINOMdOKAZATELXSTWO eSLI ZONA RABOTY MA[INY SODERVIT NE BOLEE p1(n) Q^EEK, TO PRI RABOTE MA[INY MOVET POROVDATXSQ NE BOLEErp1(n) p1(n) k RAZLI^NYH KONFIGURACIJ, POSKOLXKU NA LENTE MOVNOZAPISATX NE BOLEE rp1(n) RAZLI^NYH SLOW, GOLOWKA MOVET OBOZREWATXL@BU@ IZ NE BOLEE p1(n) Q^EEK I MA[INA MOVET NAHODITXSQ W L@BOM IZ k..,|,,,:|..74SOSTOQNIJ.
pOSKOLXKU PO USLOWI@ PRI L@BOM WHODE MA[INA OSTANAWLIWAETSQ, TO ONA NE MOVET "ZACIKLITXSQ", TO ESTX KONFIGURACIQ NE MOVETPOWTORITXSQ. PO\TOMU WREMQ RABOTY PRI L@BOM WHODE NE PREWOSHODIT^ISLA RAZLI^NYH KONFIGURACIJ. pRI \TOMlog2(rp1(n) p1(n) k) = p1 (n) log2 r + log2 p1(n) + log2 k 6 p(n);GDE p(n)| NEKOTORYJ POLINOM. tEOREMA DOKAZANA.sLEDSTWIE.
dLQ L@BOJ ZADA^I IZ PSPACE t(n) 6 2p(n) GDEp(n) NEKOT RYJ POLINOMoPREDELENIE. zADA^A RASPOZNAWANIQ (QZYK) L NAZYWAETSQPSPACE -POLNOJ, ESLI:1)L PSPACE ,2)K L POLINOMIALXNO SWODQTSQ WSE ZADA^I IZ PSPACE .uTWERVDENIE. eSLI DLQ NEKOTOROJ PSPACE POLNOJ ZADVA^I SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO,|o.-PSPACE = P-,.zADA^A O KWANTIFICIROWANNYH BULEWSKIH FORMULAH (QBF).wHOD FORMULA WIDA:(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];GDE x1; : : : ; xm |BULEWSKIE PEREMENNYE, F |BULEWSKAQ FORMULA W BAZISEfKON_@NKCIQ,DIZ_@NKCIQ,OTRICANIEg, Q ; i 2 f9; 8g DLQ WSEH i.tREBUETSQ WYQSNITX, ISTINNA LI DANNAQ FORMULA.lEMMA. QBF 2 PSPACE:.dOKAZATELXSTWO pUSTX NA WHOD POSTUPILA FORMULA(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];DLINY n.
tOGDA DLINA FORMULY F (x1; : : : ; xm ) NE BOLEE n, I DLQ L@BOGOZADANNOGO NABORA (1; : : : ; m WY^ISLENIE F (1; : : : ; m ) MOVNO WYPOLNITX ZA WREMQ, A ZNA^IT I S ISPOLXZOWANIEM PAMQTI, NE BOLEE p1(n),GDE p1 |NEKOTORYJ POLINOM. eSLI ZAFIKSIROWANY TOLXKO ZNA^ENIQ1; : : : ; k PEREMENNYH x1; : : : ; xk , TO MY POLU^AEM PODZADA^U: NAJTIISTINNOSTNOE ZNA^ENIE FORMULY(Qk+1xk+1) : : : (Qmxm )[F (1; : : : ; k )(xk+1; : : : ; xm )]:pRIMENIM DLQ RE[ENIQ ISHODNOJ ZADA^I (I WSEH EE PODZADA^) SLEDU@]IJ REKURSIWNYJ ALGORITM:1.wY^ISLITX (Q2x2) : : : (Qm xm)F (0; x2 ; : : : ; xm ) \TIM VE REKURSIWNYM ALGORITMOM.
zAPOMNITX POLU^ENNOE ZNA^ENIE (1 BIT) W DOPOLNITELXNOJ Q^EJKE..752.wY^ISLITX NA TOJ VE ZONE \TIM VE ALGORITMOM(Q2x2) : : : (Qm xm )F (0; x2; : : : ; xm ).3.eSLI Q1 = 8 I OBA ZNA^ENIQ, WY^ISLENNYE W 1 I 2, RAWNY 1,TOWYDATX OTWET 1, INA^E WYDATX 0.eSLI Q1 = 9 I OBA ZNA^ENIQ W 1 I 2RAWNO 0, TO WYDATX 0, INA^E WYDATX 1.iZ OPISANIQ ALGORITMA WIDNO, ^TO DLQ RE[ENIQ ZADA^I KAVDOGO UROWNQ NUVNO NA 1 Q^EJKU BOLX[E, ^EM NA RE[ENIE L@BOJ EEPODZADA^I.
tAK KAK NA WY^ISLENIE F (1; : : : ; m ) TREBUETSQ PAMQTINE BOLEE p1 (n), TO DLQ WY^ISLENIQ ISTINNOSTNOGO ZNA^ENIQ ISHODNOJFORMULY TREBUETSQ PAMQTX NE BOLEE p1(n) + n Q^EEK. dLQ UPRAWLENIQPROCESSOM PEREHODA OT ODINH PODZADA^ K DRUGIM W OPISANNOM ALGORITMEDOSTATO^NO POMNITX, KAKAQ PODZADA^A RE[AETSQ W DANNYJ MOMENT, TOESTX POMNITX ZNA^ENIQ 1 ; : : : ; k , OPREDELQ@]IE \TU PODZADA^U. tAKIMOBRAZOM, W CELOM OPRISANNYJ ALGORITM TREBUET NE BOLEE p(n) Q^EEKPAMQTI, GDE p|NEKOTORYJ POLINOM.tEOREMA.
zADA^A QBF QWLQETSQ PSPACE POLNOJdOKAZATELXSTWO nAM NADLO DOKAZATX, ^TO L@BAQ ZADA^A L IZPSPACE POLINOMIALXNO SWODITSQ K QBF . eSLI L 2 PSPACE , TOSU]ESTWUET MA[INA tX@RINGA M , KOTORAQ RE[AET ZADA^U L S PAMQTX@NE BOLEE p1 (n) I WREMENEM NE BOLEE p(n) (SM. LEMMU), GDE n|DLINA WHODA.pUSTX x|WHOD DLINY n DLQ ZADA^I L. nAM NADO ZA POLINOMIALXNOEWREMQ POSTROITX KWANTIFICIROWANNU@ FORMULU F (x) TAK, ^TO F (x)ISTINNA TOGDA I TOLXKO TOGDA, KOGDA x 2 L.
tOT FAKT, ^TO x 2 L,RAWNOSILEN UTWERVDENI@: DLQ WHODA x SU]ESTWUET PRINIMA@]EE (SOTWETOM "DA") WY^ISLENIE MA[INY M . |TO POSLEDNEE UTWERVDENIEMY I WYRAZIM W WIDE FORMULY F (x). tAK VE, KAK PRI DOKAZATELXSTWENP -POLNOTY ZADA^I wyp, WWEDEM DWA MNOVESTWA PEREMENNYH V I V 0,OPISYWA@]IH 2 PROIZWOLXNYE KONFIGURACII NA ZONE p1(n), I ZAPI[EMFORMULU F0(V; V 0) WYRAVA@]U@ TOT FAKT, ^TO V I V 0 PRAWILXNOZADA@T KONFIGURACII I LIBO V = V 0 , LIBO IZ KONFIGURACII V MYZA ODIN [AG MA[INY M PEREHODIM W KONFIGURACI@ V 0. kAK POKAZANO PRI DOKAZATELXSTWE NP -POLNOTY ZADA^I wyp DLINA FORMULYF0(V; V 0) MOVET BYTX OGRANI^ENA NEKOTORYM POLINOMOM p2(n) I EEMOVNO POSTROITX ZA POLINOMIALXNOE OT n WREMQ. fORMULA F0(V; V 0 )WYRAVAET TOT FAKT, ^TO IZ KONFIGURACII V W KONFIGURACI@ V 0 MOVNOPEREJTI ZA NE BOLEE ^EM 1 [AG.
pOSTROIM TEPERX INDUKTIWNO FORMULYF1; F2; : : : ; Fs , GDE s = p(n), SLEDU@]IM OBRAZOM. pUSTX W |E]E ODNOMNOVESTWO PEREMENNYH, OPISYWA@]IH KONFIGURACI@ NA ZONE p1(n).|.76.tOGDA POLOVIMFk (V; V 0) = 9W [Fk;1(V; W )&Fk;1(W; V 0 )]:fORMULA Fk WYRAVAET TOT FAKT, ^TO V; V 0|PRAWILXNYE KONFIGURACIII IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE, ^EM 2k [AGOW. fORMULA WKWADRATNYH SKOBKAH RAWNOSILXNA SLEDU@]EJ FORMULE:(8Y )(8Z )[(Y = V )&(Z = W ) _ (Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]GDE Y; Z |DWA MNOVESTWA PEREMENNYH, OPISYWA@]IH 2 PROIZWOLXNYEKONFIGURACII. pO\TOMU FORMULU Fk MOVNO ZAPISATX W WIDE:Fk (V; V 0 ) = (9W )(8Y )(8Z )[(Y = V )&(Z = W )_(Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]:tAKIM OBRAZOM, DLINA Fk(V; V 0) OTLI^AETSQ OT DLINY Fk;1(V; V 0 ) NEBOLEE ^EM NA NEKOTORYJ POLINOM p3(n) I DLINA Fk (V; V 0) NE PREWOSHODITp2(n) + kp3 (n).
pUSTX WREMQ RABOTY MA[INY M NE PREWOSHODIT 2p(n) Is + p(n). tOGDA Fs(V; V 0) IMEET DLINU NE BOLEE p2(n)+ p(n) p3(n) = p4(n),GDE p4| POLINOM, I WYRAVAET TOT FAKT, ^TO V I V 0 PRAWILXNYE KONFIGURACII I IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE 2p(n) [AGOW MA[INYM . pUSTX FORMULA Gx(V ) WYRAVAET TOT FAKT, ^TO KONFIGURACIQ VQWLQETSQ PRAWILXNOJ NA^ALXNOJ KONFIGURACIEJ DLQ WHODA x (yf pjytp1(n)), A FORMULA H (V ) WYRAVAET TOT FAKT, ^TO W KONFIGURACII VSOSTOQNIE "DA".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
