[учебник] Основы оптимизации. Новикова (1998) ([учебник] Основы оптимизации. Новикова (1998).pdf), страница 2

dLQ RQDA DRUGIH ZADA^UDAETSQ DOKAZATX IH NEPOLINOMIALXNOSTX. tAK, IZWESTNY1) ALGORITMI^ESKI NERAZRE[IMYE ZADA^I, KOGDA NE SU]ESTWUETALGORITMA, RE[A@]EGO L@BU@ INDIWIDUALXNU@ ZADA^U, T.E. 8a9I 2 p: a NE PRIMENIM K I, W ^ASTNOSTI, tA (e(I)) = 1 ; NAPRIMER, 10-Q PROBLEMA gILXBERTA: PO DANNOMU MNOGO^LENU g S CELYMI2.8KO\FFICIENTAMI WYQSNITX, IMEET LI URAWNENIE g = 0 CELO^ISLENNOERE[ENIE (NERAZRE[IMOSTX DOKAZAL `. m. mATIQSEWI^ W 1970 G.);2) ZADA^I (NE QWLQ@]IESQ ZADA^AMI RASPOZNAWANIQ SWOJSTW), DLQKOTORYH DLINA ZAPISI RE[ENIQ PREWOSHODIT L@BOJ NAPERED ZADANNYJ POLINOM OT DLINY WHODA, NAPRIMER W ZADA^E KOMMIWOQVERA, ESLITREBUETSQ NAJTI WSE MAR[RUTY (IH \KSPONENCIALXNOE ^ISLO);3) W OSTALXNYH SLU^AQH FORMALXNO IMEEM 8a, RE[A@]EGO p SKODIROWKOJ e; 8p() 9I 2 p: ta (e(I)) > p(je(I)j). zDESX I DALEE p(),WOZMOVNO S INDEKSAMI, SLUVIT DLQ OBOZNA^ENIQ POLINOMOW.w NASTOQ]EE WREMQ DLQ L@BOJ MASSOWOJ ZADA^I p, DLQ KOTOROJDOKAZANO POSLEDNEE USLOWIE, POLU^EN I BOLEE SILXNYJ REZULXTAT: OTSUTSTWIE POLINOMIALXNOGO ALGORITMA, ISPOLXZU@]EGO PROIZWOLXNOE(PUSTX BESKONE^NOE) ^ISLO PARALLELXNYH PROCESSOROW.

wOPROS, SU]ESTWU@T LI NEPOLINOMIALXNYE ZADA^I p RASPOZNAWANIQ SWOJSTW,KOTORYE OKAZYWA@TSQ POLINOMIALXNO RAZRE[IMYMI PRI WOZMOVNOSTI RASPARALLELIWANIQ WY^ISLENIJ, QWLQETSQ OSNOWNOJ METODOLOGI^ESKOJ PROBLEMOJ TEORII SLOVNOSTI (OBUSLOWIW[EJ EE FORMIROWANIEKAK SAMOSTOQTELXNOJ NAU^NOJ DISCIPLINY).

oTWET, PO-WIDIMOMU,DOLVEN BYTX POLOVITELXNYM, I UVE UKAZAN BOLX[OJ KLASS MASSOWYH ZADA^ W KA^ESTWE KANDIDATOW (SM. KLASS NPC W x2), NO DOKAZATXILI OPROWERGNUTX \TU GIPOTEZU W DANNYJ MOMENT PREDSTAWLQETSQNEREALXNYM. dLQ EE FORMALIZACII WWODITSQ OB_EML@]IJ P KLASSNEDETERMINIROWANNO POLINOMIALXNYH ZADA^ | NP.3. oPREDELIM NEDETERMINIROWANNU@ MA[INU tX@RINGA (ndmt)^ KAK NABOR OBY^NYH | DETERMINIROWANNYH | MA[IN tX@RINGAA(dmt) A(S ) S ALFAWITOM , GDE S PROBEGAET WSE MNOVESTWO SLOW IZ:^ =: fA(S )gS 2 :Andmt a^ OSTANAWLIWAETSQ, KOGDA OSTANAWLIWAETSQ PERWAQ IZ dmta(S ), PRINIMA@]AQ WHODNOE SLOWO. sOOTWETSTWU@]IM KONE^NYM SOSTOQNIEM BUDET qY .

qZYK ndmt | MNOVESTWO SLOW, PRINIMAEMYHHOTQ BY ODNOJ dmt: A(S ) IZ A^ :^ ) = f 2 j 9S 2 : 2 L(a(S ))g.L^ (asLOWA S W OPREDELENII ndmt MOVNO PROINTERPRETIROWATX KAKPODSKAZKI K RE[ENI@ (DOGADKI), TOGDA dmt a(S ) PROWERQET DLQ9WHODNOGO SLOWA PODSKAZKU S I W SLU^AE PRAWILXNOSTI OSTANAWLIWAETSQ W SOSTOQNII qY . ndmt A^ PROWERQET DLQ WHODNOGO SLOWA WSE WOZMOVNYE PODSKAZKI, I ESLI HOTX ODNA PRAWILXNAQ DOGADKA SU]ESTWUET, TO ndmt OSTANAWLIWAETSQ S OTWETOM \DA".

(w SILU BESKONE^NOSTI ^ISLA DOGADOK, W SOSTOQNII qN ndmt OSTANOWITXSQ NEMOVET.)^ RE[AET MASSOWU@ ZADA^U p S KODIoPREDELENIE 3. ndmt aROWKOJ e, ESLI L(p,e) = L^ (a^ ), T.E. QZYKI ndmt I ZADA^I SOWPADA@T:8 2 L(p,e) 9S 2 : dmt a(S ) OSTANAWLIWAETSQ W SOSTOQNII qY ,I 8 2 n L(p,e); 8S 2 dmt a(S ) NE PRINIMAET (NE OSTANAWLIWAETSQ ILI OSTANAWLIWAETSQ W SOSTOQNII qN ).oPREDELIM 8 2 L^ (a^ ) WREMQ RABOTY ndmt a^ NAD SLOWOM KAKMINIMALXNOE IZ WREMEN RABOTY NAD WHODOM dmt a(S ), PRINIMA@]IH , S U^ETOM WREMENI PRO^TENIQ SLOWA S (T.E.

EGO DLINY):t^A^ () =:min fjS j + tA(S)()g:fS j 2L gA(S)^ RE[ENIQ MASSOWOJ ZADA^I p NAwREMENNOJ SLOVNOSTX@ ndmt aZOWEM FUNKCI@ T^A^ () : 8n 2 Z+T^A^ (n) =:maxt^^ () =maxmin fjS j +tA(S)()g:^ ): jj<n fS j2LA(S) g^ ): jj<n A2L^ (a2L^ (a SLOVNOSTI dmt: DLQpOD^ERKNEM RAZNICU S OPREDELENIEM WREMENNOJndmt RASSMATRIWA@TSQ LI[X SLOWA IZ QZYKA (SOOTWETSTWU@]IE INDIWIDUALXNYM ZADA^AM S OTWETOM \DA").oPREDELENIE 4. kLASS NEDETERMINIROWANNO POLINOMIALXNYHZADA^ NP =: fL(p,e)j 9a^ | ndmt, RE[A@]AQ p S KODIROWKOJe; 9p() | POLINOM: T^A^ (n) < p(n) 8n 2 Z+ g: eSLI DLQ ZADA^I p SU]ESTWUET TAKAQ KODIROWKA e, ^TO L(p,e) 2 NP, TO BUDEMNAZYWATX ZADA^U p NEDETERMINIROWANNO POLINOMIALXNOJ I POLXZOWATXSQ OBOZNA^ENIEM p2NP (KAK I DLQ KLASSA P, KORREKTNYM).pRIMEROM NEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I QWLQETSQkm, IBO W KA^ESTWE DOGADKI MOVNO ISPOLXZOWATX MAR[RUT I PROWERKA EGO DOPUSTIMOSTI POLINOMIALXNA.oTMETIM, ^TO POLINOMIALXNOSTX PROWERKI GARANTIRUETSQ TOLXKODLQ INDIWIDUALXNYH ZADA^ S OTWETOM \DA" (I WOZMOVNO, LI[X PRI10EDINSTWENNOJ PODSKAZKE), A DLQ I 2 D(p) n Y(p) ndmt PROSTONE OSTANOWITSQ.

w \TOM | SU]ESTWENNOE OTLI^IE KLASSOW P I NP.nEPOSREDSTWENNO IZ OPREDELENIJ SLEDUETuTWERVDENIE 1. P NP.wOPROS O NALI^II STROGOGO WKL@^ENIQ I QWLQETSQ FORMALIZACIEJOSNOWNOJ PROBLEMY TEORII SLOVNOSTI.x2. NP-POLNYE (UNIWERSALXNYE) ZADA^ItEOREMA OB \KSPONENCIALXNOJ OCENKE WREMENNOJ SLOVNOSTIDLQ ZADA^ IZ KLASSA NP. kLASS SO-Nr. zADA^I, IME@]IE HORO[U@ HARAKTERIZACI@. oPREDELENIE POLINOMIALXNOJ SWODIMOSTI.kLASS NPC. tEOREMA kUKA (BEZ DOKAZATELXSTWA). kRITERIJ NPPOLNOTY. dOKAZATELXSTWO NP-POLNOTY ZADA^I blH (BULEWY LINEJNYE NERAWENSTWA).1. rASSMOTRIM PODROBNEE KLASS NP.tEOREMA 1. dLQ L@BOJ NEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I SU]ESTWUET dmt, RE[A@]AQ EE S \KSPONENCIALXNOJ WREMENNOJSLOVNOSTX@, T.E.

8p2NP 9p() | POLINOM | I dmt a:a RE[AET p I Ta(n) < 2p(n) 8n 2 Z+:dOKAZATELXSTWO. tAK KAK p2NP, TO DLQ L@BOGO SLOWA IZQZYKA ZADA^I p SU]ESTWUET PRAWILXNAQ DOGADKA S POLINOMIALXNOJ DLINY: jS j < p1 (jj); p1 () | POLINOM, I SU]ESTWUET dmta(S ) : ta(S)() < p2(jj); p2() | POLINOM. pOSTROIM dmt a,KOTORAQ RABOTAET NAD L@BYM WHODNYM SLOWOM 2 (S L@BOJ INDIWIDUALXNOJ ZADA^EJ I 2 p) SLEDU@]IM OBRAZOM: RASSMATRIWA@TSQWSE SLOWA S IZ DLINY MENX[E p1 (jj) I DELAETSQ NE BOLEE p2 (jj)[AGOW S KAVDOJ dmt a(S ). eSLI O^EREDNAQ dmt OSTANAWLIWAETSQ WSOSTOQNII qY (T.E. SOOTWETSTWU@]AQ DOGADKA OKAZALASX PRAWILXNOJ),S^ITAEM SLOWO PRINQTYM I RABOTU dmt a ZAKON^ENNOJ; ESLI NIODNA IZ dmt a(S ) NE OSTANOWILASX ZA OTWEDENNOE WREMQ ILI OSTANOWILASX W SOSTOQNII qN , TO ZAKAN^IWAEM RABOTU dmt a I PRIPISYWAEM EJ KONE^NOE SOSTOQNIE qN .

w POSLEDNEM SLU^AE dmt a DELAETNAIBOLX[EE ^ISLO [AGOW, I \TO ^ISLO MENX[E p2 (jj)jjp (jj) (WTOROJSOMNOVITELX RAWEN ^ISLU PROWERQEMYH DOGADOK, jj | ^ISLO SIMWOLOW W ALFAWITE ). oTS@DA UVE NETRUDNO POLU^ITX UTWERVDENIETEOREMY.111dLQ TOGO ^TOBY LU^[E PO^UWSTWOWATX RAZLI^IE KLASSOW P I NP,WWEDEM PONQTIE DOPOLNITELXNOJ K p MASSOWOJ ZADA^I p, POLU^A@]EJSQ IZ p RASPOZNAWANIQ SWOJSTW ZAMENOJ ALXTERNATIWNOGO WOPROSA, OPREDELQ@]EGO OTWET W ZADA^E (SM. P.20 OPREDELENIQ p Wx1) EGO OTRICANIEM, NAPRIMER WOPROSOM W km \PRAWDA LI, ^TONE SU]ESTWUET MAR[RUTA DLINY, NE PREWOSHODQ]EJ B ?".

fORMALXNOD(p) = D(p); Y(p) = D(p) n Y(p).oPREDELIMKLASSY DOPOLNITELXNYH ZADA^ co-P =: fpj p 2 Pg I:co-NP = fpj p 2 NPg. iZ OPREDELENIJ O^EWIDNO, ^TO, ESLI dmt aRE[AET p, TO dmt a RE[AET p, GDE PROGRAMMA dmt a POLU^ENAIZ PROGRAMMY dmt a PROSTOJ ZAMENOJ KONE^NYH SOSTOQNIJ qY I qNDRUG NA DRUGA. tAKIM OBRAZOM, SPRAWEDLIWOuTWERVDENIE2.co-P = P.aNALOGI^NOE UTWERVDENIE DLQ KLASSA NP DO SIH POR NE UDAETSQNI DOKAZATX NI OPROWERGNUTX: PRIWEDENNOE WY[E DLQ dmt RASSUVDENIE NELXZQ OBOB]ITX NA ndmt, IBO DLQ INDIWIDUALXNYH ZADA^I S OTWETOM \NET" (T.E.

I 62 Y(p), ILI I 2 Y(p)) ndmt NE OSTANAWLIWAETSQ ZA WREMQ, OGRANI^ENNOE POLINOMOM OT DLINY WHODA I.w ^ASTNOSTI, NE IZWESTNA ndmt, RE[A@]AQ km ZA POLINOMIALXNOE WREMQ, TAK KAK DLQ NEE NE PRIDUMANO PODSKAZKI POLINOMIALXNOJDLINY (ESTESTWENNYJ WARIANT | POKAZATX WSE MAR[RUTY | NE POLINOMIALEN); WKL@^ENIE km 2 NP NE DOKAZANO I NE OPROWERGNUTO.upravnenie 3. dOKAZATX, ^TO ZADA^A RASPOZNAWANIQPROSTOTY ^ISLA PRINADLEVIT KLASSU SO-Nr, T.E.

p~ 2 NP.oPREDELENIE mASSOWAQ ZADA^A RASPOZNAWANIQ SWOJSTW NAZYWAETSQ IME@]EJ HORO[U@ HARAKTERIZACI@, ESLI DLQ NEE WYPOLNENOp 2 NP\co-NP.iZ UTWERVDENIQ 2 SLEDUET, ^TO P NP\co-NP. sOWREMENNAQ GIPOTEZA SOSTOIT W RAWENSTWE \TIH KLASSOW. oTS@DA I TERMIN \HORO[AQHARAKTERIZACIQ", TAK KAK DLQ PODOBNYH ZADA^ ESTX OSNOWANIQ NADEQTXSQ NA WOZMOVNOSTX POSTROENIQ POLINOMIALXNYH ALGORITMOW (SM.ZADA^U ln | LINEJNYE NERAWENSTWA | W RAZD.2).

oDNAKO DLQ ZADA^Ip~, OBLADA@]EJ HORO[EJ HARAKTERIZACIEJ (DLQ DOKAZATELXSTWA TOGO, ^TO p~ 2 NP, SM. [2, S. 414]), DETERMINIROWANNOGO POLINOMIALXNOGO ALGORITMA POKA NE NAJDENO, NESMOTRQ NA EE NEPOSREDSTWENNU@PRAKTI^ESKU@ ZNA^IMOSTX.5.122. zADA^ RASPOZNAWANIQ SWOJSTW | BOLX[OE RAZNOOBRAZIE, I DLQTEORII PREDSTAWLQET INTERES NE TOLXKO WOZMOVNOSTX IH KLASSIFIKACII, NO I SPOSOBY OPREDELENIQ KLASSA SLOVNOSTI ODNIH ZADA^ NAOSNOWE IZWESTNOGO KLASSA SLOVNOSTI DRUGIH.

pO\TOMU WWODITSQ BAZOWOE DLQ TEORII SLOVNOSTI PONQTIE POLINOMIALXNOJ SWODIMOSTI.oPREDELENIE 6. bUDEM GOWORITX, ^TO MASSOWAQ ZADA^A RASPOZNAWANIQ SWOJSTW p0 S KODIROWKOJ e0 POLINOMIALXNO SWODITSQ K ZADA^Ep S KODIROWKOJ e, ESLI L@BAQ INDIWIDUALXNAQ ZADA^A I0 2 p0 MOVET BYTX SWEDENA ZA POLINOMIALXNOE OT EE DLINY WREMQ K NEKOTOROJI 2 p S SOHRANENIEM OTWETA. fORMALXNOSU]ESTWUET FUNKCIQ SWODIMOSTI f : e0 (D(p0 )) ! e(D(p)), TAKAQ^TO f (e0 (Y(p0 ))) = e(Y(p)), T.E.

80 2 e0 (Y(p0 )) f (0 ) 2 e(Y(p))I 800 2 e0 (D(p0 ) n Y(p)) f (00 ) 2 e(D(p) n Y(p)),I SU]ESTWUET dmt Af ; REALIZU@]AQ f ZA POLINOMIALXNOE WREMQ,T.E. 9pf () | POLINOM: 8 2 e0 (D(p0 )) TAf (jj) < pf (jj):w SLU^AE, KOGDA SOOTWETSTWU@]IE KODIROWKI NE IZBYTO^NY, BUDEMISPOLXZOWATX TERMIN POLINOMIALXNOJ SWODIMOSTI PO OTNO[ENI@ KSAMIM ZADA^AM (BEZ UKAZANIQ KODIROWOK) I PRIMENQTX OBOZNA^ENIEp0 / p:(kORREKTNOSTX UPRO]ENIQ WYTEKAET IZ POLINOMIALXNOJ SWODIMOSTIZADA^I K SAMOJ SEBE, NO S DRUGOJ NEIZBYTO^NOJ KODIROWKOJ, I SLEDU@]EGO O^EWIDNOGO UTWERVDENIQ | TRANZITIWNOSTI OTNO[ENIQ /.)uTWERVDENIE 3.

eSLI p1 / p2 I p2 / p3 ; TO p1 / p3 .sU]ESTWENNYM DLQ TEORII SLOVNOSTI QWLQETSQuTWERVDENIE 4. eSLI p0 / p I p 2 P; TO I p0 2 P.dOKAZATELXSTWO. oBOZNA^IM a dmt, RE[A@]U@ p S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@, I POSTROIM dmt A0 , RE[A@]U@ p0 S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@, KAK SUPERPOZCI@dmt A I Af : A0 = A Af ; T.E. SNA^ALA K L@BOMU WHODNOMU SLOWU0 2 e0 (D(p0 )) PRIMENQETSQ Af ; A POTOM K POLU^IW[EMUSQ SLOWU = f (0 ) (DLINOJ NE BOLEE pf (j0 j)) PRIMENQETSQ A. wREMENNAQSLOVNOSTX A0 | TA0 () TAf () + TA (pf ()) | POLINOM.aNALOGI^NO DOKAZYWAETSQ (PRI ZAMENE SLOWA dmt NA ndmt)uTWERVDENIE 5. eSLI p0 / p I p 2 NP; TO I p0 2 NP.13oPREDELENIE 7.

mASSOWAQ ZADA^A p NAZYWAETSQ NP-POLNOJ ILIUNIWERSALXNOJ, ESLI p 2 NP I 8p0 2 NP p0 / p (T.E. L@BAQ NEDETERMINIROWANNO POLINOMIALXNAQ ZADA^A POLINOMIALXNO SWODITSQK p). kLASS WSEH NP-POLNYH ZADA^ (RASPOZNAWANIQ SWOJSTW) OBOZNA^AETSQ NPC (NP-complete).nEPUSTOTU KLASSA NPC DOKAZAL s. a. kUK W 1971 G.