В.Б. Алекссев - Сложные алгоритмы (1132790), страница 14
Текст из файла (страница 14)
pUSTX ON STROIT KRAT^AJ[EE OSTOWNOEDEREWO D S SUMMARNYM WESOM REBER d(D). pUSTX C | L@BOJ GAMILXTONOW CIKL. eSLI WYBROSITX L@BOE REBRO IZ C , TO POLU^IM DEREWO T .pRI \TOMd(D) 6 d(T ) 6 d(C ):pO\TOMU d(D) 6 FOPT. rASSMOTRIM DEREWO D I ZAMENIM KAVDOE REBROe = (vi ; vj ) W D DWUMQ REBRAMI e0 = (vi; vj ) I e" = (vi ; vj ). tOGDAPOLU^IM MULXTIGRAF K (GRAF S KRATNYMI REBRAMI), W KOTOROM STEPENXKAVDOJ WER[INY ^ETNA. tAK KAK D| OSTOWNOE DEREWO, TO MULXTIGRAFK SWQZNYJ. wY[E DOKAZANO (SM. TEOREMU ( )), ^TO W L@BOM SWQZNOMMULXTIGRAFE, W KOTOROM STEPENI WSEH WER[IN ^ETNY, SU]ESTWUET \JLEROW CIKL. pRIMENIM K K ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQPOSTROENIQ W K \JLEROWA CIKLA C1 (SU]ESTWOWANIE TAKOGO ALGORITMADOKAZANO W TEOREME( )).
pOSKOLXKU CIKL C1 PROHODIT PO KAVDOMU REBRUW K ROWNO 1 RAZ, TO WES d(C1) = 2d(D) 6 2FOPT. wYBEREM L@BU@ WER[INU v1 W C1 W KA^ESTWE NA^ALXNOJ I PUSTX WER[INY W C1 WSTRE^A@TSQW PORQDKE v1; v2 ; v3; : : : ; vi;1 ; vi ; vi+1 ; : : : ; v1 . pUSTX WYDELENNOE ZNA^ENIEvi WSTRE^AETSQ W CIKLE RANX[E. tOGDA ZAMENIM POSLEDOWATELXNOSTXREBER (vi;1; vi ); (vi ; vi+1 ) NA REBRO (vi;1; vi+1 W ISHODNOM GRAFE. pRI \TOMPOLU^IM OPQTX CIKL, PROHODQ]IJ PO WSEM WER[INAM. pOSKOLXKU WESAUDOWLETWORQ@T NERAWENSTWU TREUGOLXNIKA, TO SUMMARNYJ WES CIKLAPRI \TOM NE WOZRASTET.
eSLI W POLU^ENNOM CIKLE SNOWA ESTX POWTORQ@]IESQ WER[INU, TO OPQTX WYBROSIM ODNU WER[INU, OSU]ESTWIW"SPRQMLENIE". |TOT PROCESS BUDEM POWTORQTX DO TEH POR, POKA NEPOLU^ITSQ CIKL C2 BEZ POWTORQ@]IHSQ WER[IN. tOGDA CIKL C2 BUDETGAMILXTONOWYM I d(C2) 6 d(C1) 6 2FOPT. w REZULXTATE MY POLU^AEMALGORITM DLQ zknt S POLINOMIALXNOJ SLOVNOSTX@, KOTORYJ QWLQETSQ1-PRIBLIVENNYM...71zADA^A O MAKSIMALXNOJ KLIKEwY[E BYLO DOKAZANO, ^TO ZADA^A klika QWLQETSQ NP -POLNOJ.rASSMOTRIM TEPERX SLEDU@]U@ ZADA^U mk.wHOD NEORIENTIROWANNYJ GRAF G.tREBUETSQ NAJTI KAKU@-NIBUDX MAKSIMALXNU@ PO ^ISLU WER[INKLIKU.tEOREMA.
zADA^A O MAKSIMALXNOJ KLIKE mk QWLQETSQNP TRUDNOJdOKAZATELXSTWO pUSTX A | ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ mk, I PUSTX PARA (G; k) | WHOD DLQ ZADA^I klika.pRIMENIM K G ALGORITM A I NAJDEM MO]NOSTX m POLU^ENNOJ MAKSIMALXNOJ KLIKI W G. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
