В.Б. Алекссев - Сложные алгоритмы (1132790), страница 9
Текст из файла (страница 9)
sLEDOWATELXNO, OT PROTIWNOGO, POLU^AEM, ^TO PRIWYPOLNENII USLOWIQ A) ILI B) QZYK L REGULQREN. tEOREMA DOKAZANA.sLEDSTWIE. eSLI dM (n) = o(log n) ILI TM (n) = o(n log n) TOSU]ESTWUET MA[INA tX@RINGA AWTOMAT N RASPOZNA@]AQ TOT VEQZYK L DLQ KOTOROJ dN (n) = 1 TN (n) = n + 1.|,(|).:);),|( ),.|.2..,(,),,.44kLASSY P I NPoPREDELENIE.
pUSTX ALGORITM OSU]ESTWLQET PREOBRAZOWANIE ' :! B SLOW W ALFAWITE A W SLOWA W ALFAWITE B . tOGDA \TOT ALGORITM NAZYWAETSQ POLINOMIALXNYM (ILI IME@]IM POLINOMIALXNU@SLOVNOSTX), ESLI SU]ESTWUET POLINOM p(n) TAKOJ, ^TO DLQ L@BOGO NATURALXNOGO n WREMQ RABOTY ALGORITMA NA L@BOM WHODNOM SLOWE DLINY nNE PREWOSHODIT p(n). (pRI \TOM MOVNO S^ITATX, ^TO WSE KO\FFICIENTYW p(n) NEOTRICATELXNY, TO ESTX p(n) WOZRASTA@]AQ FUNKCIQ.)oPREDELENIE. zADA^EJ RASPOZNAWANIQ NAZYWAETSQ L@BOE OTOBRAVENIE ' : A ! f\DA", \NET"g.s L@BOJ ZADA^EJ RASPOZNAWANIQ ' MOVNO SWQZATX QZYK L' ASLEDU@]IM OBRAZOM: a 2 L' () ' : a ! \DA".
i OBRATNO, L@BOJ QZYKMOVNO RASSMATRIWATX KAK ZADA^U RASPOZNAWANIQ.oPREDELENIE. kLASS P |\TO KLASS WSEH QZYKOW (ZADA^ RASPOZNAWANIQ), DLQ KAVDOGO IZ KOTORYH SU]ESTWUET RASPOZNA@]IJ ALGORITMS POLINOMIALXNOJ SLOVNOSTX@.oPREDELENIE. bUDEMGOWORITX, ^TO QZYK L1 A POLINOMIALXNOSWODITSQ K QZYKU L2 B , ESLI SU]ESTWUET POLINOMIALXNYJ ALGORITM(NAPRIMER, MA[INA tX@RINGA) ' : A ! B , TAKOJ ^TO '(a) 2 L2 ()a 2 L1.tEOREMA.
pUSTX L1 A L2 B L2 2 P I L1 POLINOMIALXNOSWODITSQ K L2 tOGDA L1 2 PdOKAZATELXSTWO. pO USLOWI@ SU]ESTWU@T MA[INY tX@RINGAM1 I M2 TAKIE, ^TO M1 POLINOMIALXNO SWODIT L1 K L2, A M2 S POLINOMIALXNOJ SLOVNOSTX@ RASPOZNAET L2. rASSMOTRIM MA[INU tX@RINGAM = M2(M1). tOGDA M : A ! f\DA", \NET"g, PRI^EM DLQ L@BOGO SLOWAa 2 A IMEEMM (a) = \DA" () M2(M1(a)) = \DA" () M1(a) 2 L2 () a 2 L1;TO ESTX M RASPOZNAET QZYK L1. pO USLOWI@ WREMQ RABOTY (^ISLO [AGOW)MA[IN M1 I M2 NA WHODNYH SLOWAH DLINY n NE PREWOSHODIT p1 (n) Ip2(n), GDE p1; p2 | POLINOMY. tOGDA WREMQ RABOTY M NA SLOWE a DLINYn NE PREWOSHODIT p1 (n) + p2(jM1(a)j); GDE jM1(a)j | DLINA SLOWA M1(a).tAK KAK MA[INA tX@RINGA M1 NA KAVDOM [AGE MOVET UWELI^IWATXDLINU SLOWA NE BOLEE ^EM NA 1, TO jM1(a)j 6 n + p1(n) I WREMQ RABOTYM NA a NE PREWOSHODIT p1(n) + p2(n + p1(n)) = p3(n), GDE p3 | POLINOM.
(zDESX S^ITAETSQ, ^TO WSE KO\FFICIENTY W p2 NEOTRICATELXNYI, SLEDOWATELXNO, p2 (n) | NEUBYWA@]AQ FUNKCIQ). tAKIM OBRAZOM MRASPOZNAET QZYK L1 S POLINOMIALXNOJ SLOVNOSTX@. tEOREMA DOKAZANA.A,.,.45|TA TEOREMA POZWOLQET POLU^ATX POLINOMIALXNYE ALGORITMY DLQODNIH ZADA^ RASPOZNAWANIQ IZ IME@]IHSQ POLINOMIALXNYH ALGORITMOW DLQ DRUGIH ZADA^ PROSTO PUTEM POLINOMIALXNOGO SWEDENIQ ODNIHZADA^ K DRUGIM.k SOVALENI@, DLQ BOLX[INSTWA ZADA^, WOZNIKA@]IH NA PRAKTIKE,POKA NE IZWESTNO, WHODQT LI ONI W KLASS P , NO PO^TI WSE TAKIE ZADA^IOKAZYWA@TSQ W DRUGOM KLASSE, KOTORYJ OBOZNA^A@T NP .oPREDELENIE.
qZYK L A (ZADA^A RASPOZNAWANIQ) WHODIT WKLASS NP , ESLI I TOLXKO ESLI SU]ESTWU@T ALFAWIT B , POLINOM q(n)I PREDIKAT Q(x; y) : A B ! fI, Lg TAKIE, ^TO Q(x; y) 2 P I DLQL@BOGO SLOWA a 2 A WYPOLNQETSQ:a 2 L () 9b 2 B (jbj 6 q(jaj)&Q(a; b))(ZDESX jaj I jbj |DLINA SLOW a I b).sLOWO b NAZYWA@T SERTIFIKATOM DLQ SLOWA a, A ALGORITM, RASPOZNA@]IJ PREDIKAT Q(a; b), | ALGORITMOM PROWERKI SERTIFIKATA.tAKIM OBRAZOM, ESLI a 2 L (W ZADA^E RASPOZNAWANIQ DLQ WHODA a OTWET\DA"), TO DOLVNO SU]ESTWOWATX BYSTROE PODTWERVDENIE DLQ \TOGO, TOESTX DOLVEN SU]ESTWOWATX PODTWERVDA@]IJ \TO SERTIFIKAT b (NEBOLX[OJ DLINY) I BYSTRYJ SPOSOB PODTWERDITX, ^TO \TO DEJSTWITELXNOPODHODQ]IJ SERTIFIKAT.
eSLI VE a 2= L, TO PO OPREDELENI@ W \TOMSLU^AE NI^EGO NE TREBUETSQ. tAKIM OBRAZOM, OTWETY \DA" I \NET"ZDESX NE SIMMETRI^NY. zAMETIM TAKVE, ^TO DLQ SLU^AQ a 2 L LI[XUTWERVDAETSQ SU]ESTWOWANIE SERTIFIKATA b, NO NI^EGO NE GOWORITSQO SLOVNOSTI EGO NAHOVDENIQ (ESLI W B IMEETSQ r BUKW I jaj = n,TO jbj 6 q(n) I ^ISLO TAKIH SLOW b NE MENX[E, ^EM rq(n), TO ESTX\KSPONENCIALXNO ZAWISIT OT n).rASSMOTRIM PRIMERY QZYKOW IZ NP .klika.
wHOD L@BOJ NEORIENTIROWANNYJ GRAF G I NATURALXNOE ^ISLO k.wOPROS sU]ESTWUET LI W GRAFE G KLIKA RAZMERA k, TO ESTX kWER[IN TAKIH, ^TO L@BAQ PARA IZ NIH SOEDINENA REBROM?bOLEE STROGO, MY DOLVNY ZADATX WHODNOJ ALFAWIT A I SPOSOBPREDSTAWLENIQ GRAFOW W \TOM ALFAWITE. mOVNO, NAPRIMER, S^ITATX,^TO A = f0; 1; ; g I GRAF ZADAETSQ MATRICEJ SMEVNOSTI (IZ 0 I 1),KOTORAQ ZATEM WYPISYWAETSQ W ODNO SLOWO PODRQD PO STROKAM MATRICYS RAZDELITELEM ; MEVDU STROKAMI MATRICY.uTWERVDENIE.
klika 2 NPdOKAZATELXSTWO w KA^ESTWE SERTIFIKATA b DLQ WHODA a BUDEMBRATX SPISOK IZ k WER[IN, SOSTAWLQ@]IH KLIKU. o^EWIDNO, jbj 6 jaj.::..46pREDIKAT Q BUDET OBOZNA^ATX, ^TO DANNYE WER[INY ZADA@T KLIKU WDANNOM GRAFE I \TIH WER[IN ROWNO k. dLQ RASPOZNAWANIQ SPRAWEDLIWOSTI TAKOGO SWOJSTWA Q LEGKO POSTROITX ALGORITM SO SLOVNOSTX@, NEPREWOSHODQ]EJ POLINOMA OT SUMMARNOJ DLINY KODA GRAFA a I SERTIFIKATA b.gamilxtonow cikl (gc).
wHOD L@BOJ NEORIENTIROWANNYJ GRAF G.wOPROS sU]ESTWUET LI W GRAFE G GAMILXTONOW CIKL, TO ESTXCIKL, PROHODQ]IJ ^EREZ KAVDU@ WER[INU ROWNO 1 RAZ?uTWERVDENIE. gc 2 NPdOKAZATELXSTWO sERTIFIKATOM ZDESX QWLQETSQ POSLEDOWATELXNOSTX IZ WER[IN v1; v2; : : : ; vm . pREDIKAT Q WYRAVAET UTWERVDENIE,^TO W \TOJ POSLEDOWATELXNOSTI WSE WER[INY GRAFA WSTRE^A@TSQ ROWNO1 RAZ I W GRAFE ESTX REBRA (vi ; vi+1 ) DLQ WSEH i = 1; 2; : : : ; m ; 1, A TAKVEREBRO (vm; v1). dLQ RASPOZNAWANIQ SPRAWEDLIWOSTI TAKOGO SWOJSTWA QLEGKO POSTROITX ALGORITM SO SLOVNOSTX@, NE PREWOSHODQ]EJ POLINOMAOT SUMMARNOJ DLINY KODA GRAFA a I SERTIFIKATA b.oPREDELENIE.
kON_@NKTIWNOJ NORMALXNOJ FORMOJ (knf) NAZYWAETSQ BULEWA FORMULA WIDA F (x1; : : : ; xm ) = D1&D2& : : : &Dk, GDEDLQ KAVDOGO j : Dj = tj;1 _ tj;2 _ : : : _ tj;nj I WSE tj;k | LIBO PEREMENNYE,LIBO OTRICANIQ PEREMENNYH. wYRAVENIQ Dj NAZYWA@T DIZ_@NKTAMI,A SOSTAWLQ@]IE IH tj;k LITERALAMI.wypolnimostx (wyp). wHOD L@BAQ FORMULA F W WIDEknf.wOPROS SU]ESTWUET LI NABOR PEREMENNYH (1; : : : ; m ), NA KOTOROM F (1; : : : ; m ) = 1 (WYPOLNIMA LI F )?uTWERVDENIE. wyp 2 NPdOKAZATELXSTWO sERTIFIKATOM DLQ WHODA F QWLQETSQ NABOR(1; : : : ; m ), NA KOTOROM F (1; : : : ; m ) = 1.
pREDIKAT Q WYRAVAETTOT FAKT, ^TO DANNAQ FORMULA F NA DANNOM NABORE (1; : : : ; m ) DEJSTWITELXNO PRINIMAET ZNA^ENIE 1. dLQ RASPOZNAWANIQ SPRAWEDLIWOSTITAKOGO SWOJSTWA Q LEGKO POSTROITX ALGORITM SO SLOVNOSTX@, NE PREWOSHODQ]EJ POLINOMA OT SUMMARNOJ DLINY KODA FORMULY F I KODANABORA (1; : : : ; m ).e]E RAZ OBSUDIM WOPROS O PREDSTAWLENII WHODNYH DANNYH.
mY NEMOVEM, NAPRIMER, WKL@^ITX W ALFAWIT A PROIZWOLXNYE PEREMENNYE,TAK KAK IH BESKONE^NOE ^ISLO, A L@BAQ MA[INA tX@RINGA RABOTAETLI[X S KONE^NYMI ALFAWITAMI. oDNAKO DOSTATO^NO WZQTX ALFAWITA = fx; 0; 1; &; _; e; (; )g I PEREMENNU@ xi ZAPISYWATX KAK x S IDU]IM::..::..47DALEE ^ISLOM i, PREDSTAWLENNYM W DWOI^NOJ SISTEME S^ISLENIQ. oBRATIM TAKVE WNIMANIE NA TO, ^TO W OPREDELENII ZADA^ RASPOZNAWANIQ NAWHOD MOVET POSTUPITX L@BOE SLOWO W ZADANNOM ALFAWITE A. w ZADA^Ewyp MNOGIE TAKIE SLOWA NE PREDSTAWLQ@T knf. pREDPOLAGAETSQ, ^TOOTWETOM DLQ TAKIH WHODNYH SLOW QWLQETSQ \NET". aNALOGI^NO PONIMA@TSQ I DRUGIE ZADA^I (NAPRIMER, klika ILI gc).tEOREMA.
P NP .dOKAZATELXSTWO pUSTX L 2 P , I L A. wOZXMEM L@BOJALFAWIT B I q(n) = 1. pREDIKAT Q(a; b) PUSTX WYRAVAET TOT FAKT, ^TOa 2 L (NEZAWISIMO OT b). tAK KAK L 2 P , TO PREDIKAT Q RASPOZNAETSQZA WREMQ, POLINOMIALXNO ZAWISQ]EE OT jaj, A ZNA^IT I OT jaj + jbj, TOESTX Q 2 P . pRI \TOM, O^EWIDNO, ^TO DLQ L@BOGO a 2 A SPRAWEDLIWOSOOTNO[ENIEa 2 L () 9b 2 B (jbj 6 1&Q(a; b))(SERTIFIKAT b ZDESX NE ZAWISIT OT a). tAKIM OBRAZOM, L 2 NP . tEOREMADOKAZANA..48tEOREMA kUKAoPREDELENIE.
qZYKL (ZADA^A RASPOZNAWANIQ) NAZYWAETSQNP -TRUDNYM, ESLI L@BOJ QZYK L1 IZ NP POLINOMIALXNO SWODITSQ KL.w SOOTWETSTWII S TEOREMOJ ( ), ESLI QZYK L QWLQETSQ NP -TRUDNYMI L 2 P , TO NP P I S U^ETOM TEOREMY ( ) P = NP . i OBRATNO, ESLIP 6= NP , TO L 2= P . tAKIM OBRAZOM, NP -TRUDNOSTX QZYKA QWLQETSQKOSWENNYM SWIDETELXSTWOM TOGO, ^TO L 2= P (KOSWENNYM POTOMU, ^TOWEROQTNO P 6= NP , NO \TO POKA NE DOKAZANO I NE OPROWERGNUTO).oPREDELENIE. qZYK L (ZADA^A RASPOZNAWANIQ) NAZYWAETSQNP -POLNYM, ESLI L 2 NP I L QWLQETSQ NP -TRUDNYM.eSTESTWENNO WOZNIKAET WOPROS O TOM, SU]ESTWU@T LI TAKIE \UNIWERSALXNYE" ZADA^I W KLASSE NP , K KOTORYM POLINOMIALXNO SWODQTSQWSE ZADA^I IZ NP . oKAZYWAETSQ, ^TO SU]ESTWU@T.
pERWYJ REZULXTATTAKOGO RODA BYL USTANOWLEN s. kUKOM.tEOREMA (s. kUK). zADA^A wyp O WYPOLNIMOSTI knf QWLQETSQ NP POLNOJdOKAZATELXSTWO wY[E UVE DOKAZANO, ^TO wyp 2 NP . pO\TOMUNADO DOKAZATX, ^TO L@BOJ QZYK L IZ NP POLINOMIALXNO SWODITSQ Kwyp. pUSTX L 2 NP I L A. |TO OZNA^AET, ^TO SU]ESTWU@T POLINOMq(n), ALFAWIT B I PREDIKAT Q(x; y) : A B ! f\I", \L"g TAKIE, ^TOQ(x; y) 2 P I DLQ L@BOGO SLOWA a 2 A SPRAWEDLIWOa 2 L () 9b(jbj 6 q(jaj)&Q(a; b)):nAM NADO POKAZATX, ^TO L POLINOMIALXNO SWODITSQ K wyp. |TOOZNA^AET, ^TO NADO POSTROITX TAKOE PREOBRAZOWANIE S POLINOMIALXNOJSLOVNOSTX@ ' : A ! C , GDE C | ALFAWIT ZADA^I wyp, ^TO a 2L () '(a) = Fa | WYPOLNIMAQ knf OT NEKOTORYH PEREMENNYH.tAK KAK Q(x; y) 2 P , TO SU]ESTWUET MA[INA tX@RINGA M , KOTORAQ RASPOZNAET PREDIKAT Q(x; y) ZA WREMQ (^ISLO [AGOW), NE PREWOSHODQ]EE NEKOTOROGO POLINOMA p0 OT DLINY WHODA.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
