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

iM BYLA RASSMOTRENA ZADA^A O WYPOLNIMOSTI (wyp): WYQSNITX WYPOLNIMOSTXKON_@NKTIWNOJ NORMALXNOJ FORMY (knf) | KON_@NKCII KONE^NOGO^ISLA DIZ_@NKTIWNYH FUNKCIJ, T.E. DIZ_@NKCIJ BULEWYH PEREMENNYH zi ILI IH OTRICANIJ zi . a IMENNO, W ZADA^E wyp TREBUETSQRASPOZNATX DLQ knf NA WHODE, SU]ESTWUET LI WYPOLNQ@]IJ NABORz 0 (DLQ KOTOROGO ZNA^ENIE knf RAWNO 1).tEOREMA 2 (S. A. Cook). wyp 2 NPC.dOKAZATELXSTWO POLINOMIALXNOJ SWODIMOSTIK wyp L@BOJNEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I OSNOWANO NA FORMALXNOJ ZAPISI USLOWIQ PRINADLEVNOSTI SLOWA QZYKU IZ KLASSA NP (TOGO, ^TO PRINIMAETSQ NEKOTOROJ ndmt, A ZNA^IT, I KAKOJ-TO dmt)W WIDE NABORA DIZ_@NKTIWNYH FUNKCIJ OT SPECIALXNO WWODIMYH BULEWYH PEREMENNYH, SWQZANNYH S SOSTOQNIQMI dmt W RAZLI^NYE MOMENTY WREMENI, I QWLQETSQ NEDOSTATO^NO PROSTYM DLQ WWODNOGO KURSA (SM.

[1,2]). pO\TOMU MY LI[X UBEDIMSQ W TOM, ^TO wyp 2 NP.dEJSTWITELXNO, WHODNOE SLOWO (PARAMETRY, OPREDELQ@]IE INDIWIDUALXNU@ ZADA^U WYPOLNIMOSTI) SODERVIT ^ISLO DIZ_@NKTIWNYHFUNKCIJ W knf I UKAZANIE DLQ KAVDOJ IZ NIH, KAKIE PEREMENNYEWHODQT S OTRICANIEM, A KAKIE NE WHODQT WOOB]E.

dLINU TAKOGO SLOWAMOVNO OGRANI^ITX SNIZU SUMMOJ DLIN DIZ_@NKTIWNYH FUNKCIJ, PONIMAQ POD DLINOJ FUNKCII ^ISLO EE PEREMENNYH (ILI ^ISLO ZNAKOWDIZ_@NKCII + 1). eSLI TEPERX W KA^ESTWE PODSKAZKI DLQ OPREDELQEMOJ WHODNYM SLOWOM knf WZQTX z0 | WYPOLNQ@]IJ EE NABOR, TOWY^ISLENIE NA NEM ZNA^ENIQ knf (PROWERKA WYPOLNIMOSTI) POTREBUET TAKOGO VE PO PORQDKU ^ISLA [AGOW.iZ OPREDELENIQ NP-POLNOTY NEPOSREDSTWENNO SLEDUETuTWERVDENIE 6. eSLI P \ NPC =6 ;, TO P = NP. a ESLINPC \ (NP n P) =6 ;, TO NPC NP n P.tAKIM OBRAZOM, ESLI BY UDALOSX NAJTI POLINOMIALXNYJ ALGORITM RE[ENIQ HOTX ODNOJ NP-POLNOJ ZADA^I, TO BYLI BY POSTROENY14POLINOMIALXNYE ALGORITMY RE[ENIQ WSEH NP-POLNYH ZADA^ I WSEHZADA^ IZ KLASSA NP, A ESLI DLQ KAKOJ-LIBO NP-POLNOJ ZADA^I DOKAZATX OTSUTSTWIE POLINOMIALXNOGO ALGORITMA EE RE[ENIQ, TO \TONE TOLXKO DAET STROGOE WKL@^ENIE P NP (T.E.

OTWET K OSNOWNOJPROBLEME TEORII SLOVNOSTI), NO I WLE^ET ZA SOBOJ DOKAZATELXSTWO NEWOZMOVNOSTI POSTROENIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ L@BOJ ZADA^I IZ KLASSA NPC. pOSKOLXKU NI TOGO, NI DRUGOGO POKA NESDELANO, S^ITAETSQ, ^TO ZADA^I IZ NPC OTWE^A@T VITEJSKOMU PREDSTAWLENI@ O TRUDNOJ ZADA^E I WRQD LI DOPUSKA@T \FFEKTIWNOE RE[ENIE. pO\TOMU, ESLI WSTRE^AETSQ ZADA^A, DLQ KOTOROJ NA PRAKTIKENE UDAETSQ PRIDUMATX NEPEREBORNYJ ALGORITM, TO IMEET SMYSL POPYTATXSQ DOKAZATX EE NP-POLNOTU, ^TOBY OPRAWDATX PRIMENENIE KNEJ TEH ILI INYH PEREBORNYH SHEM.3. pOSLE TOGO KAK BYLA USTANOWLENA NEPUSTOTA KLASSA NPC (TEOREMOJ kUKA), POQWILASX WOZMOVNOSTX DOKAZATELXSTWA NP-POLNOTYMASSOWOJ ZADA^I p PUTEM POLINOMIALXNOGO SWEDENIQ K p ODNOJ IZIZWESTNYH NP-POLNYH ZADA^ (SOOTWETSTWU@]IJ SPISOK SM.

W [1]).dEJSTWITELXNO, IZ UTWERVDENIQ 3 SLEDUETtEOREMA 3 (KRITERIJ NP-POLNOTY). mASSOWAQ ZADA^A p RASPOZNAWANIQ SWOJSTW NP-POLNA TOGDA I TOLXKO TOGDA, KOGDA ONA PRINADLEVIT KLASSU NP I K NEJ POLINOMIALXNO SWODITSQ KAKAQ-LIBONP-POLNAQ ZADA^A:fp 2 NPCg () fp 2 NP I 9p0 2 NPC : p0 / pg:pOLXZUQSX TEOREMOJ 3, MOVNO POKAZATX NP-POLNOTU ZADA^I O SU]ESTWOWANII CELO^ISLENNOGO RE[ENIQ SISTEMY LINEJNYH NERAWENSTWS CELYMI KO\FFICIENTAMI (cln).uTWERVDENIE 7. cln 2 NPC.dOKAZATELXSTWO. 1) cln 2 NP, TAK KAK PODSKAZKOJ MOVETSLUVITX RE[ENIE SISTEMY, A EGO PROWERKA SWODITSQ K UMNOVENI@ NAZADANNYE KO\FFICIENTY I SLOVENI@, ^TO NE PREWOSHODIT POLINOMAOT DLINY ZAPISI WSEH KO\FFICIENTOW (DOKAZATELXSTWO POLINOMIALXNOSTI DLINY ZAPISI RE[ENIQ SM.

W [2, S. 330]).2) wyp / cln. oB]IJ WID SISTEMY LINEJNYH NERAWENSTWaj 1 z1 + aj 2 z2 + : : : + ajn zn bj ; j = 1; : : : ; m:nETRUDNO PREDSTAWITX W PODOBNOJ FORME USLOWIE ISTINNOSTI DIZ_@NKTIWNOJ FUNKCII. dLQ \TOGO ZAMENIM W KAVDOJ j -J FUNKCII ZNAKI15DIZ_@NKCII ZNAKAMI SUMMY, A OTRICANIQ PEREMENNYH zi | NA (1 zi )I NAPI[EM DLQ POLU^IW[EJSQ LINEJNOJ FUNKCII USLOWIE 1, DOBAWIW OGRANI^ENIQ zi 0 I zi 1 NA WSE PEREMENNYE. cELO^ISLENNOERE[ENIE z0 = fzi0g SISTEMY WSEH POSTROENNYH NERAWENSTW QWLQETSQ WYPOLNQ@]IM NABOROM DLQ ISHODNOJ knf (TAK KAK ISTINNOSTXknf \KWIWALENTNA ISTINNOSTI WSEH OBRAZU@]IH EE DIZ_@NKTIWNYHFUNKCIJ).

tAKIM SPOSOBOM RE[ENIE L@BOJ INDIWIDUALXNOJ ZADA^IO WYPOLNIMOSTI SWODITSQ K RE[ENI@ NEKOTOROJ INDIWIDUALXNOJ ZADA^I I 2 cln. pOLINOMIALXNOSTX SWEDENIQ O^EWIDNA.zAMETIM, ^TO FAKTI^ESKI W P.2 DANNOGO DOKAZATELXSTWA DOKAZANBOLEE SILXNYJ REZULXTAT O SWEDENII wyp K PODZADA^E cln | ZADA^E O SU]ESTWOWANII BULEWA RE[ENIQ SISTEMY LINEJNYH NERAWENSTWS CELYMI KO\FFICIENTAMI (bln). dOKAZATELXSTWO PRINADLEVNOSTIbln KLASSU NEDETERMINIROWANNO POLINOMIALXNYH ZADA^ POWTORQETP.1 DANNOGO DOKAZATELXSTWA BEZ SSYLKI NA [2] (TAK KAK POLINOMIALXNOSTX DLINY BULEWA RE[ENIQ O^EWIDNA), TEM SAMYM POLU^ENO IuTWERVDENIE 8. bln 2 NPC.x3. kLASSY SLOVNOSTI.sILXNAQ NP-POLNOTA I PSEWDOPOLINOMIALXNOSTXdOKAZATELXSTWO NP-POLNOTY ZADA^I O 3-WYPOLNIMOSTI. wZAIMOOTNO[ENIE KLASSOW r, Nr I Nrs, Nr I SO-Nr.

NP-TRUDNYEZADA^I. kLASS rSrase. pSEWDOPOLINOMIALXNYE ALGORITMY. pRIMER DLQ ZADA^I O R@KZAKE. sILXNAQ NP-POLNOTA. tEOREMA O SWQZI SILXNOJ NP-POLNOTY ZADA^I S SU]ESTWOWANIEM PSEWDOPOLINOMIALXNOGO ALGORITMA EE RE[ENIQ.1. kROME ZADA^I O WYPOLNIMOSTI, NP-POLNOTA WSEH OSTALXNYHIZWESTNYH ZADA^ IZ KLASSA NPs (W TOM ^ISLE I km) BYLA DOKAZANANA OSNOWE TEOREMY 3 S POMO]X@ POLINOMIALXNOGO SWEDENIQ. oB]IERECEPTY DOKAZATELXSTWA POLINOMIALXNOJ SWODIMOSTI (SM. W [1]) LEGKO ISPOLXZOWATX LI[X W PROSTEJ[IH SLU^AQH. ~TOBY NAU^ITXSQ IHPRIMENQTX, NADO RAZOBRATX BOLX[OE ^ISLO PRIMEROW (W ^ASTNOSTI,IME@]IESQ W [1,2]), NA ^TO U NAS W RAMKAH DANNOJ RABOTY NET WOZMOVNOSTI.

oDNAKO, E]E ODIN PRIMER BUDET DALEE PRIWEDEN S CELX@POKAZATX, ^TO NE TOLXKO L@BAQ PODZADA^A SWODITSQ K SOOTWETSTWU@]EJ ZADA^E (AWTOMATI^ESKI), NO WOZMOVNO I OBRATNOE SWEDENIE.16rASSMOTRIM ^ASTNYJ SLU^AJ ZADA^I O WYPOLNIMOSTI, KOGDA Wknf MOGUT WHODITX LI[X DIZ_@NKTIWNYE FUNKCII TREH PEREMENNYH (3-wyp). pOSKOLXKU D(3-wyp)D(wyp), TO PO OPREDELENI@ 3-wyp/wyp. tAK ^TO 3-wyp2NP (PO UTWERVDENI@ 5). nOEE NP-POLNOTA TREBUET SPECIALXNOGO DOKAZATELXSTWA, IBO ^ASTNYEMASSOWYE ZADA^I SODERVAT MENX[E INDIWIDUALXNYH ZADA^ I MOGUTOKAZATXSQ PRO]E; NAPRIMER, ANALOGI^NAQ ZADA^A 2-wyp POLINOMIALXNA.

dLQ POLU^ENIQ REZULXTATA 3-wyp 2 NPs DOKAVEM, ^TO NPPOLNAQ ZADA^A O WYPOLNIMOSTI SWODITSQ K SWOEJ PODZADA^E (^ASTNOMUSLU^A@) 3-wyp.uTWERVDENIE 9. wyp / 3-wyp.dOKAZATELXSTWO. pOKAVEM, ^TO PROIZWOLXNU@ DIZ_@NKTIWNU@FUNKCI@ f j (zj ) k PEREMENNYH MOVNO PREDSTAWITX W WIDE KON_@NKCII DIZ_@NKTIWNYH FUNKCIJ OT TREH PEREMENNYH (ZA S^ET WWEDENIQjDOPOLNITELXNYH PEREMENNYH uj ). oBOZNA^IM ^EREZ yi PEREMENNU@ ziILI zji W ZAWISIMOSTI OT TOGO, KAK i-Q KOMPONENTA zj WHODIT W RASSMATRIWAEMU@ DIZ_@NKTIWNU@ FUNKCI@; TOGDA POSLEDN@@ MOVNOZAPISATX KAK y1 _ y2 _ : : : _ yk I PRI k > 3 ZAMENITX NA knf:(y1 _ y2 _ uj1)&(y3 _ uj1 _ uj2)&(y4 _ uj2 _ uj3)& : : :: : : &(yk 2 _ ujk 4 _ ujk 3 )&(yk 1 _ yk _ ujk 3 ).oTMETIM, ^TO DANNAQ ZAMENA NE QWLQETSQ \KWIWALENTNOJ.

dEJSTWITELXNO, ESLI ISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX NUL@, TO POSTROENNAQ knf RAWNA NUL@ PRI WSEH ZNA^ENIQH u, NO ESLIISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX 1, TO NAJDETSQ TAKOEZNA^ENIE u, ^TOBY knf RAWNQLASX 1. |TOGO, ODNAKO, DOSTATO^NO DLQSOHRANENIQ OTWETA NA WOPROS O SU]ESTWOWANII WYPOLNQ@]EGO NABORA.upravnenie 4. zAWER[ITX DOKAZATELXSTWO Nr-POLNOTY ZADA^I 3-wyp (RASSMOTRETX SLU^AI k < 3).2. uNIWERSALXNOSTX ZADA^ IZ KLASSA NPs (NP-POLNYH ZADA^) SOSTOIT W TOM, ^TO OSNOWNYE NERE[ENNYE WOPROSY DLQ KLASSA NP (NEDETERMINIROWANNO POLINOMIALXNYH ZADA^) DOSTATO^NO RAZRE[ITX HOTQ BY DLQ ODNOJ NP-POLNOJ ZADA^I, ^TOBY POLU^ITX OTWET DLQ WSEGOKLASSA NP. kROME UTWERVDENIQ 6 ZDESX TAKVE WAVNOeSLI DLQ NEKOTOROJ NP-POLNOJ ZADA^I p DOuTWERVDENIEPOLNITELXNAQ K NEJ p PRINADLEVIT KLASSU NP, TO NP = co-NP.10.17tAK KAK p 2 NPC, TO 8p0 2 NP p0 / p,OTS@DA I p / p (POLINOMIALXNOE SWEDENIE OSU]ESTWLQETSQ0 TOJ VEFUNKCIEJ | SM.

OPREDELENIE 6). nO p 2 NP, ZNA^IT, p 2 NPPO UTWERVDENI@ 5. s U^ETOM PROIZWOLXNOSTI p0 2 NP POLU^ILI,^TO co-NP NP. oBRATNOE WKL@^ENIE DOKAZYWAETSQ NA OSNOWANIIO^EWIDNOGO RAWENSTWA p = p.nAPOMNIM, ^TO GIPOTEZA NP = co-NP W NASTOQ]EE WREMQ KAVETSQ NEREALXNOJ (REALXNAQ GIPOTEZA P = NP\co-NP), I WRQD LIDLQ KAKOJ-LIBO NP-POLNOJ ZADA^I UDASTSQ DOKAZATX PRINADLEVNOSTXKLASSU co-NP. pO\TOMU DLQ KONKRETNOJ NEDERMINIROWANNO POLINOMIALXNOJ MASSOWOJ ZADA^I p2NP, ESLI EE RE[ENIE PREDSTAWLQETINTERES, IMEET SMYSL POPYTATXSQ DOKAZATX WKL@^ENIE p 2 NP (T.E.EE HORO[U@ HARAKTERIZACI@) I ZATEM POSTROITX POLINOMIALXNYJALGORITM RE[ENIQ, LIBO, KOGDA UKAZANNOE WKL@^ENIE NE DOKAZYWAETSQ, NADO POPROBOWATX POLINOMIALXNO SWESTI K p ODNU IZ IZWESTNYHNP-POLNYH ZADA^ (T.E.

POKAZATX NP-POLNOTU p) I W SLU^AE USPEHAPODYSKIWATX PEREBORNU@ SHEMU RE[ENIQ (U^ITYWAQ OGRANI^ENIQ NARAZMERNOSTX PRAKTI^ESKI RE[AEMYH INDIWIDUALXNYH ZADA^).dOKAZATELXSTWO UNIWERSALXNOSTI p, T.E. WKL@^ENIQ p2NPC,UDAETSQ NE WSEGDA, I W TEORII SLOVNOSTI BYL WWEDEN OB_EML@]IJNPC KLASS NP-TRUDNYH ZADA^, SODERVA]IJ1) 0p RASPOZNAWANIQ SWOJSTW, DLQ KOTORYH DOKAZANO, ^TO p0 / pDLQ p 2 NPC, NO NE POKAZANO, ^TO p 2 NP (W ^ASTNOSTI, \TO ZADA^Ip2co-NPC);2) p OPTIMIZACII, DLQ KOTORYH SOOTWETSTWU@]IE p RASPOZNAWANIQ SWOJSTW NP-POLNY (NAPRIMER, ZADA^A KOMMIWOQVERA IZ P.1x1);3) I OSTALXNYE MASSOWYE ZADA^I (NE OBQZATELXNO RASPOZNAWANIQSWOJSTW), K KOTORYM SWODQTSQ PO tX@RINGU KAKIE-LIBO NP-POLNYEZADA^I p0 2 NPC, GDE SWODIMOSTX PO tX@RINGU | p0 /T p | OZNA^AET, ^TO IZ SU]ESTWOWANIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ pSLEDUET SU]ESTWOWANIE POLINOMIALXNOGO ALGORITMA I DLQ p0 .zADA^I p (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW), DLQ KOTORYH9p0 2 NPC: p0 /T p I 9p00 2 NP: p /T p00 , NAZYWA@TSQ ZADA^AMI IZ KLASSA NP-\KWIWALENTNYH.dOKAZATELXSTWO.018wSE RASSMOTRENNYE NAMI KLASSY ZADA^ p | KLASSY SLOVNOSTIWKL@^A@TSQ W OB]IJ KLASS PSPACE MASSOWYH ZADA^ (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW), DLQ RE[ENIQ KOTORYH SU]ESTWU@TALGORITMY, TREBU@]IE NE BOLEE ^EM POLINOMIALXNOJ PAMQTI.

wOPROS O RAWENSTWE P I PSPACE QWLQETSQ OTKRYTYM. rABO^AQ GIPOTEZA SOSTOIT W NALI^II STROGOGO WKL@^ENIQ PPSPACE, PRI\TOM NP-POLNYE, NP-TRUDNYE I NP-\KWIWALENTNYE ZADA^I DOLVNYWKL@^ATXSQ W PSPACE n P. (sOOTWETSTWU@]U@ DIAGRAMMU WZAIMOSWQZI KLASSOW SLOVNOSTI SM. W [2, S. 412].)zAMETIM, ^TO TEORETI^ESKI RASSMOTRENNU@ SHEMU POSTROENIQKLASSOW SLOVNOSTI MOVNO PRIMENQTX I DLQ DRUGIH SHEM KLASSIFIKACII; W ^ASTNOSTI, WWODQT TAKVE KLASS PSPACE-POLNYH ZADA^ (K KOTORYM POLINOMIALXNO SWODITSQ L@BAQ ZADA^A IZ KLASSA PSPACE).kROME POLINOMIALXNOJ SWODIMOSTI MOVNO ANALOGI^NO GOWORITX OLOGARIFMI^ESKOJ SWODIMOSTI, O ZADA^AH, TREBU@]IH LOGARIFMI^ESKOJ PAMQTI I T.P. w NASTOQ]EE WREMQ NAIBOLEE INTENSIWNO IZU^AEMYM ZDESX OKAZYWAETSQ KLASS NC (Nick Class, AWTOR N. Pippenger)ZADA^, RE[AEMYH ZA WREMQ, OGRANI^ENNOE POLINOMOM OT LOGARIFMADLINY WHODA, I TREBU@]IH POLINOMIALXNOJ PAMQTI (LOGARIFMI^ESKOE WREMQ PRI WOZMOVNOSTI POLINOMIALXNOGO ^ISLA PROCESSOROW).k SOVALENI@, IZLOVENIE POLU^ENNYH DLQ NC REZULXTATOW WYHODITZA RAMKI WWEDENIQ W TEORI@ SLOVNOSTI.3.