Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 2
Текст из файла (страница 2)
(s E]E ODNOJ POLINOMIALXNOJ ZADA^EJ MY WSTRETIMSQ W RAZD.2.) dLQ ZADA^I RASPOZNAWANIQ PROSTOTY ^ISLA (p~)WOPROS O EE POLINOMIALXNOSTI POKA OTKRYT. 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 a^^ROWKOJ 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):min fjS j + tA(S)()g:t^A^ () =:fS j 2L gA(S)^ RE[ENIQ MASSOWOJ ZADA^I p NAwREMENNOJ SLOVNOSTX@ ndmt a^ZOWEM FUNKCI@ TA^ () : 8n 2 Z+T^A^ (n) =max^ ): jj<n2L^ (at^A^ () =:maxmin fjS j +tA(S)()g:^ ): jj<n fS j2LA(S) g2L^ (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^I SLOVNOSTItEOREMA OB \KSPONENCIALXNOJ OCENKE WREMENNOJDLQ 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. pOSTROIMdmt 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
