В.Б. Алексеев - Электронный коспект лекций, страница 14

zk QWLQETSQ NP TRUDNOJdOKAZATELXSTWO pUSTX SU]ESTWUET ALGORITM H DLQ zk SO SLOVNOSTX@, POLINOMIALXNO ZAWISQ]EJ OT DLINY WHODA. pUSTX DAN GRAFG = (V; E ) S n WER[INAMI I SPRA[IWAETSQ ESTX LI W G GAMILXTONOWCIKL. pUSTX V = fv1; v2; : : : ; vn g. pOSTROIM POLNYJ GRAF Kn NA MNOVESTWE WER[IN V I ZADADIM WESA SLEDU@]IM OBRAZOM:pRIMENIM ALGORITM H DLQ zk K GRAFU Kn S \TIMI WESAMI. eSLIPOLU^IM DLQ zk, ^TO Fmin = n, TO W G SU]ESTWUET GAMILXTONOW CIKL,INA^E W G NE SU]ESTWUET GAMILXTONOWA CIKLA. tAKIM OBRAZOM, POLU^AEM ALGORITM DLQ ZADA^I O GAMILXTONOWOM CIKLE (gc).

pOSKOLXKU W GMENX[E, ^EM n2 REBER, TO SUMMARNAQ DLINA DWOI^NOJ ZAPISI WSEH WESOWNE PREWOSHODIT cn2, GDE c|NEKOTORAQ KONTSANTA, TO ESTX DLINA WHODADLQ H NE PREWOSHODIT POLINOMA OT n. tAK KAK H |POLINOMIALXNYJ (OTDLINY WHODA) ALGORITM, TO POSTROENNYJ NAMI ALGORITM DLQ gc IMEETPOLINOMIALXNU@ OT n SLOVNOSTX. tAKIM OBRAZOM IZ SU]ESTWOWANIQALGORITMA S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk WYTEKAET SU]ESTWOWANIE AGORITMA S POLINOMIALXNOJ SLOVNOTX@ DLQ gc. pOSKOLXKUZADA^A gc QWLQETSQ NP -POLNOJ, TO POLU^AEM, ^TO ZADA^A zk QWLQETSQNP -TRUDNOJ.tEOREMA.

eSLI P =6 NP TO NI DLQ KAKOGO SKOLX UGODNO BOLX[OGO POSTOQNNOGO ^ISLA " PRIBLIVENNOGO ALGORITMA DLQ zk S POLINOMIALXNOJ SLOVNOSTX@::-..,---.69dOKAZATELXSTWO dOPUSTIM, ^TO SU]ESTWUET " I SU]ESTWUET"-PRIBLIVENNYJ ALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk.pOSTROIM TOGDA ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ gc.pUSTX DAN GRAF G = (V; E ) S n WER[INAMI. pOSTROIM POLNYJ GRAFKn = (V; E 0 ) I DLQ WSEH e 2 E 0 POLOVIMpRIMENIM K Kn c WESAMI d ALGORITM H .

pUSTX ALGORITM HNAHODIT GAMILXTONOW CIKL S SUMMARNOJ DLINOJ FH .lEMMA. eSLI W GARFE G ESTX GAMILXTONOW CIKL TO FH 6 n(1 +") eSLI W GRAFE G NET GAMILXTONOWA CIKLA TO FH > n(1 + ") + 1dOKAZATELXSTWO eSLI W G ESTX GAMILXTONOW CIKL, TO W zk DLQKn c dtcfvb d BUDET FOPT = n. tAK KAK H QWLQETSQ "-PRIBLIVENNYMALGORITMOM DLQ zk, TO FH 6 FOPT(1 + ") = n(1 + "). eSLI W G NETGAMILXTONOWA CIKLA, TO L@BOJ GAMILXTONOW CIKL SODERVIT HOTQ BYODNO REBRO S WESOM [3 + "n] I n ; 1 REBER S WESOM NE MENEE 1. tAKIMOBRAZOM, SUMMARNYJ WES L@BOGO GAMILXTONOWA CIKLA NE MENX[E ^EMn ; 1 + 2 + "n = n(1 + ") + 1.lEMMA POKAZYWAET, ^TO PO REZULXTATU RABOTY ALGORITMA H MOVNO OPREDELITX, ESTX LI W G GAMILXTONOW CIKL. tAKIM OBRAZOM, MYPOLU^AEM ALGORITM H1 DLQ ZADA^I gc.

oCENIM WREMQ EGO RABOTY.dLINA DWOI^NOGO PREDSTAWLENIQ KAVDOGO WESA d(e) NE PREWOSHODITc log2 n, GDE c|NEKOTORAQ KONSTANTA, I KOLI^ESTWO WESOW MENX[E, ^EMn2. pO\TOMU DLINA WHODA DLQ ALGORITMA H NE PREWOSHODIT POLINOMAOT n. pOSKOLXKU WREMQ RABOTY H ZAWISIT POLINOMIALXNO OT DLINYWHODA, TO OB]EE WREMQ RABOTY ALGORITMA H1 NE PREWOSHODIT POLINOMAOT n. w REZULXTATE MY POLU^AEM, ^TO ESLI SU]ESTWUET "-PRIBLIVENNYJALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk, TO SU]ESTWUETALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ ZADA^I gc.

nO ZADA^Agc NP -POLNA. tOGDA POLU^AEM, ^TO P = NP . tEOREMA DOKAZANA.wO MNOGIH PRAKTI^ESKIH ZADA^AH WESA UDOWLETWORQ@T ESTESTWENNOMU OGRANI^ENI@, NAZYWAEMOMU NERAWENSTWOM TREUGOLXNIKA:d(vi ; vj ) 6 d(vi ; vk ) + d(vk ; vj )DLQ WSEH RAZLI^NYH i; j; k. bUDEM GOWORITX, ^TO DANA ZADA^A KOMMIWOQVERA S NERAWENSTWOM TREUGOLXNIKA (zknt), ESLI NA WHOD POSTUPA@TTOLXKO WESA, UDOWLETWORQ@]IE NERAWESTWU TREUGOLXNIKA.tEOREMA.

zknt NP POLNAdLQ DOKAZATELXSTWA \TOJ TEOREMY POLNOSTX@ PROHODIT DOKAZATELXSTWO TEOREMY ( ). dOSTATO^NO TOLXKO OTMETITX, ^TO NABOR WESOW,KOTORYJ STROITSQ W \TOM DOKAZATELXSTWE, UDOWLETWORQET NERAWENSTWUTREUGOLXNIKA..,.,.-.70.tEOREMA. dLQ zknt SU]ESTWUET PRIBLIVENNYJ ALGORITM S1-POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO mY DOLVNY POSTROITX ALGORITM H DLQ zkntTAKOJ, ^TO WSEGDA FH 6 2FOPT. pRIMENIM K ZADANNOMU GRAFU KnS WESAMI d ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ POSTROENIQKRAT^AJ[EGO OSTOWNOGO DEREWA. 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.