Метода

pOD QZYKOM, WOSPRINIMAEMYM MAGAZINNYM AWTOMATOM, PONIMA@T MNOVESTWO WSEH WOSPRINIMAEMYH IM SLOW.

71

AWTOMAT DOLVEN IMETX WOZMOVNOSTX W L@BOJ UDOBNYJ MOMENT PEREJTI OT ZAPOMINANIQ W STEKE PRO^ITANNOJ ^ASTI SLOWA (SOSTOQNIE q1 ) K SRAWNENI@ NEPRO^ITANNOJ ^ASTI \TOGO SLOWA S SODERVIMYM STEKA (SOSTOQNIE

mOVNO DOKAZATX SLEDU@]U@ TEOREMU. qZYK WOSPRINIMAETSQ MAGAZINNYM AWTOMATOM TOGDA I TOLXKO TOGDA, KOGDA ON QWLQETSQ KONTEKSTNO SWOBODNYM. dOKAZATELXSTWO MOVNO NAJTI W [7; 9] .

72

g l a w a 5 slovnostx algoritmow

x1. zADA^I, ALGORITMY, SLOVNOSTX

s RAZWITIEM WY^ISLITELXNOJ TEHNIKI, OKAZALOSX, ^TO DLQ NEKOTORYH ZADA^ NEDOSTATO^NO IMETX ALGORITMY, RE[A@]IE IH, NO I TREBUETSQ, ^TOBY \TI ALGORITMY DAWALI OTWET ZA PRIEMLEMOE WREMQ I S ISPOLXZOWANIEM OGRANI^ENNOGO KOLI^ESTWA RESURSOW (PAMQTI). rASSMOTRIM FAKTORY, WLIQ@]IE NA WREMQ RABOTY ALGORITMA.

1.tIP USTROJSTWA, NA KOTOROM RABOTAET ALGORITM (KOMPX@TER, MIKROKALXKULQTOR, ^ELOWEK).

2.sPOSOB REALIZACII (QZYKI PROGRAMMIROWANIQ pASKALX, sI, aSSEMBLER).

3.oB_<M WHODNYH DANNYH.

oT PERWYH DWUH FAKTOROW ZAWISIT WREMQ RABOTY ALGORITMA, NO ONI NE HARAKTERIZU@T KA^ESTWO SAMOGO ALGORITMA. sLEDOWATELXNO, PRI SRAWNENII ALGORITMOW NADO OCENIWATX NE FIZI^ESKOE WREMQ RABOTY, A KOLI^ESTWO [AGOW, KOTORYE DELA@T \TI ALGORITMY, BUDU^I ZAPISANNYMI ODNIM I TEM VE SPOSOBOM (NAPRIMER, NA ODNOM I TOM VE QZYKE PROGRAMMIROWANIQ).

wAVNOSTX TRETXEGO FAKTORA POD^<RKIWAETSQ SLEDU@]IM OBSTOQTELXSTWOM. kAVDYJ ALGORITM MOVET RE[ATX POTENCIALXNO BESKONE^NOE KOLI^ESTWO ODNOTIPNYH ZADA^, INA^E MOVNO BYLO BY SOSTAWITX TABLICU OTWETOW I OTPALA BY NADOBNOSTX W POSTROENII ALGORITMA. |TO SWOJSTWO ALGORITMOW NAZYWAETSQ MASSOWOSTX@, A ZADA^I, KOTORYE ONI RE[A@T NAZYWA@TSQ MASSOWYMI. mASSOWAQ ZADA^A \TO ZADA^A, IME@]AQ NESKOLXKO (OBY^NO ^ISLOWYH) PARAMETROW, PRI^<M NEKOTORYE IZ NIH MOGUT PRINIMATX BESKONE^NOE ^ISLO ZNA^ENIJ.

73

mASSOWAQ ZADA^A ZADA<TSQ:

1)OB]IM SPISKOM WSEH PARAMETROW,

2)OPISANIEM SWOJSTW, KOTORYM DOLVEN UDOWLETWORQTX OTWET. iNDIWIDUALXNAQ ZADA^A POLU^AETSQ IZ MASSOWOJ, ESLI WSEM PARAMETRAM \TOJ ZADA^I PRIDATX KONKRETNYE ZNA^ENIQ. iMENNO \TI KONKRETNYE ZNA^ENIQ DLQ PARAMETROW I PEREDA@TSQ ALGORITMU W KA- ^ESTWE WHODNYH DANNYH DLQ RE[ENIQ INDIWIDUALXNOJ ZADA^I. pOSKOLXKU INDIWIDUALXNYH ZADA^ DLQ DANNOGO ALGORITMA MOVET BYTX BESKONE^NO MNOGO, TO OB_<M WHODNYH DANNYH MOVET NEOGRANI^ENNO WOZRASTATX. s ROSTOM OB_<MA WHODNYH DANNYH RAST<T I KOLI^ESTWO [AGOW ALGORITMA. pO\TOMU, KA^ESTWO I SKOROSTX ALGORITMA HARAKTERIZUET WREMENNAQ FUNKCIQ T (n) , ZNA^ENIEM KOTOROJ QWLQETSQ MAKSIMALXNOE ^ISLO [AGOW ALGORITMA DLQ INDIWIDUALXNYH ZADA^ S OB_<MOM WHODNYH DANNYH, RAWNYM n , PRI^<M WAVNYM QWLQETSQ TO, KAK RAST<T \TA FUNKCIQ PRI BOLX[IH n .

oKAZALOSX, ^TO \FFEKTIWNYMI (BYSTRYMI) QWLQ@TSQ POLINOMIALXNYE ALGORITMY, T.E. ALGORITMY, U KOTORYH FUNKCIQ WREMENNOJ SLOVNOSTI T(n) MOVET BYTX OGRANI^ENA POLINOMOM. w PROTIWOPOLOVNOSTX \TOMU, ALGORITMY, U KOTORYH FUNKCIQ T(n) \KSPONENCIALXNA, UVE PRI NEBOLX[IH n RABOTA@T NEPRIEMLEMO DOLGO. rAZLI- ^IE MEVDU POLINOMIALXNYMI I \KSPONENCIALXNYMI ALGORITMAMI HORO[O WIDNO IZ TABLIC 5 I 6. pERWAQ TABLICA POZWOLQET SRAWNITX WREMQ RABOTY ALGORITMOW S POLINOMIALXNYMI I \KSPONENCIALXNOJ

FUNKCIQMI WREMENNOJ SLOVNOSTI (ZDESX S^ITAETSQ, ^TO ODIN [AG ALGORITMA WYPOLNQETSQ ZA 10;6 SEKUNDY), A WTORAQ POKAZYWAET NASKOLXKO UWELI^ATSQ RAZMERY ZADA^, RE[AEMYH ZA ODIN ^AS MA- [INNOGO WREMENI, ESLI BYSTRODEJSTWIE |wm WOZRAST<T W 100 ILI

1000 RAZ.

tABLICA 5

tABLICA 6

mOVNO PROWERITX, ^TO POLINOMIALXNOSTX ILI \KSPONENCIALXNOSTX { HARAKTERISTIKI SAMOGO ALGORITMA, ONI NE ZAWISQT NI OT TIPA USTROJSTWA, NI OT SPOSOBA REALIZACII \TOGO ALGORITMA. |TO POZWOLQET, W ZAWISIMOSTI OT SITUACII, ISPOLXZOWATX RAZLI^NYE SPOSOBY ZAPISI ALGORITMOW.

x2. zADA^I RASPOZNAWANIQ I IH SLOVNOSTX

w DALXNEJ[EM, IZ SOOBRAVENIJ UDOBSTWA, MY BUDEM RASSMATRI-

WATX TOLXKO ZADA^I RASPOZNAWANIQ SWOJSTW, T.E. TAKIE MASSOWYE

ZADA^I, KOTORYE IME@T TOLXKO DWA WOZMOVNYH RE[ENIQ "DA" ILI

"NET".

w SWQZI S \TIM, WNES<M NESKOLXKO NEPRINCIPIALXNYH IZMENENIJ W PONQTIE MA[INY tX@RINGA.

oPREDELENIE 1. dETERMINIROWANNOJ MA[INOJ tX@RINGA, SOKRA]ENNO dmt, NAZYWAETSQ TROJKA M = (A; Q; P ) , GDE

NIJ ALFAWIT, 2 A { PUSTOJ SIMWOL, Q { ALFAWIT WNUTRENNIH SOSTOQNIJ, q1 2 Q { NA^ALXNOE, qY ; qN 2 Q { ZAKL@^ITELXNYE SOSTOQNIQ, P { PROGRAMMA, SOSTOQ]AQ IZ KOMAND WIDA qa ! q0a0s ,

GDE q 2 Q n fqY ; qN g , q0 2 Q , a; a0 2 A , s 2 fL; R; Eg , PRI^<M DLQ

L@BOGO q 2 Q n fqY ; qN g I L@BOGO a 2 A ESTX W TO^NOSTI ODNA KOMANDA WIDA qa ! : : : .

pONQTIE KONFIGURACII I SWQZANNYE S NIM DRUGIE PONQTIQ I OBOZNA^ENIQ TE VE, ^TO I W GL.2.

mNOVESTWO WSEH KONE^NYH SLOW W ALFAWITE A OBOZNA^AETSQ ^E- REZ A . pODMNOVESTWO L A NAZYWAETSQ QZYKOM W ALFAWITE A .

oPREDELENIE 2. dmt M DOPUSKAET (RASPOZNAET) DANNOE SLO-

WO U 2 A , ESLI M , NA^AW RABOTU NA SLOWE U , OSTANAWLIWAETSQ W ZAKL@^ITELXNOM SOSTOQNII qY .

75

QZYK L A , ESLI L SOSTOIT IZ WSEH SLOW, DOPUSKAEMYH M . |TOT QZYK BUDEM OBOZNA^ATX ^EREZ LM .

oBOZNA^IM ^EREZ tM (U) KOLI^ESTWO [AGOW, KOTOROE DELAET MA- [INA tX@RINGA M NA SLOWE U .

oPREDELENIE 4. wREMENNOJ SLOVNOSTX@ DETERMINIROWANNOJ

MA[INY tX@RINGA M NAZYWAETSQ FUNKCIQ TM : N ! N , ZADAWAEMAQ RAWENSTWOM

TM (n) = maxftM (U) j U 2 LM ;jUj = ng:

mEVDU ZADA^AMI RASPOZNAWANIQ I QZYKAMI MOVNO USTANOWITX SOOTWETSTWIE. dLQ \TOGO NADO WYBRATX SPOSOB KODIROWANIQ, POZWOLQ@]IJ PREDSTAWITX NABOR NA^ALXNYH ZNA^ENIJ PARAMETROW INDIWIDUALXNOJ ZADA^I W WIDE SLOWA W NEKOTOROM ALFAWITE (\TO MOVET BYTX, NAPRIMER, PERE^ISLENIE W OPREDEL<NNOM PORQDKE \TIH ZNA^E- NIJ ^EREZ ZAPQTU@). w REZULXTATE WSE SLOWA W ALFAWITE RAZDELQTSQ NA TRI GRUPPY: SLOWA, QWLQ@]IESQ KODAMI INDIWIDUALXNYH ZADA^, NA KOTORYE DOLVEN BYTX POLU^EN OTWET "DA" (QZYK L1 ), SLOWA, QWLQ@]IESQ KODAMI INDIWIDUALXNYH ZADA^, U KOTORYH OTWET "NET" (QZYK L2 ), I SLOWA, NE QWLQ@]IESQ KODAMI ZADA^ (QZYK L3 ).

tOGDA ALGORITMU, RE[A@]EMU DANNU@ ZADA^U RASPOZNAWANIQ, BUDET SOOTWETSTWOWATX DETERMINIROWANNAQ MA[INA tX@RINGA M , OSTANAWLIWA@]AQSQ W SOSTOQNII qY NA SLOWAH IZ QZYKA L1 , W SOSTOQNII qN NA SLOWAH IZ L2 , I NE OSTANAWLIWA@]AQSQ NA SLOWAH IZ L3 . w \TOM SLU^AE

wOZMOVNY RAZLI^NYE SPOSOBY KODIROWKI NA^ALXNYH DANNYH, A, ZNA^IT, ODNOJ I TOJ VE ZADA^E I ODNOMU I TOMU VE ALGORITMU, RE[A@]EMU \TU ZADA^U, MOGUT SOOTWETSTWOWATX RAZLI^NYE QZYKI I RAZLI^NYE MA[INY tX@RINGA. fUNKCII WREMENNOJ SLOVNOSTI U \TIH MA[IN TAKVE BUDUT OTLI^ATXSQ DRUG OT DRUGA, NO, W SLU^AE WYBORA "RAZUMNYH" KODIROWOK, \TI FUNKCII BUDUT POLINOMIALXNO \KWIWALENTNYMI. pOD "RAZUMNOJ" MY BUDEM PONIMATX KODIROWKU, KOTORAQ QWLQETSQ 1) DEKODIRUEMOJ, 2) SVATOJ (NE SODERVA]EJ IZBYTO^NOJ INFORMACII).

dLQ BOLX[EJ OPREDEL<NNOSTI, BUDEM PRIDERVIWATXSQ SLEDU@- ]IH PRAWIL.

76

1.cELYE ^ISLA PREDSTAWLQ@TSQ W POZICIONNOJ SISTEME S^ISLENIQ (OBY^NO DWOI^NOJ ILI DESQTI^NOJ).

2.wER[INY GRAFA NUMERU@TSQ ^ISLAMI 1; 2; : : : ; n , A GRAF ZADA<TSQ LIBO SPISKOM REB<R, LIBO MATRICEJ SMEVNOSTI.

3.pEREMENNYE W LOGI^ESKIH FORMULAH BUDEM ZAMENQTX NA ^ISLA 1; 2; : : : ; n , A LOGI^ESKIE SWQZKI RASSMATRIWAEM KAK SIMWOLY ALFAWITA.

oPREDELENIE 5. dmt M IMEET POLINOMIALXNU@ WREMENNU@ SLOVNOSTX, ESLI SU]ESTWUET POLINOM p(n) TAKOJ, ^TO DLQ L@BOGO n WERNO NERAWENSTWO

wSE ZADA^I, W ZAWISIMOSTI OT TOGO KAKU@ WREMENNU@ SLOVNOSTX IMEET NAILU^[IJ IZ IZWESTNYH ALGORITMOW, RE[A@]IH DANNU@ ZADA^U, MOVNO RAZBITX NA TRI KLASSA.

kLASS P. w \TOT KLASS WHODQT "HORO[IE" (POLINOMIALXNYE) ZADA^I, T.E. TAKIE ZADA^I, DLQ KOTORYH IZWESTNY ALGORITMY, RE[A- @]IE IH ZA POLINOMIALXNOE WREMQ. |TIM ZADA^AM SOOTWETSTWU@T QZYKI IZ KLASSA P .

oPREDELENIE 6. qZYK L PRINADLEVIT KLASSU P , ESLI SU]ESTWUET IME@]AQ POLINOMIALXNU@ WREMENNU@ SLOVNOSTX DETERMINIROWANNAQ MA[INA tX@RINGA M TAKAQ, ^TO LM = L .

kLASS E. w \TOT KLASS WHODQT \KSPONENCIALXNYE PO SWOEJ PRIRODE ZADA^I, T.E. ZADA^I, DLQ KOTORYH DOKAZANO, ^TO ONI NE MOGUT BYTX RE[ENY ALGORITMOM S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@. |TIM ZADA^AM SOOTWETSTWU@T QZYKI IZ KLASSA E .

oPREDELENIE 7. qZYK L PRINADLEVIT KLASSU E , ESLI DLQ L@BOGO POLINOMA p I DLQ L@BOJ DETERMINIROWANNOJ MA[INY tX@- RINGA M TAKOJ, ^TO LM = L , SU]ESTWUET ^ISLO n , PRI KOTOROM

TM (n) > p(n) .

zADA^I, NE POPAW[IE W KLASSY P I E. w \TOT KLASS WHODQT ZADA^I, DLQ KOTORYH IZWESTNY TOLXKO \KSPONENCIALXNYE ALGORITMY, NO NE DOKAZANO, ^TO NE SU]ESTWUET POLINOMIALXNYH. w \TOM KLASSE OSOBU@ ROLX IGRA@T TAK NAZYWAEMYE PEREBORNYE ZADA^I, T.E. ZADA^I, RE[AEMYE PEREBOROM WARIANTOW, PRI^<M KOLI^ESTWO WARIANTOW RAST<T \KSPONENCIALXNO, NO NA PROWERKU KAVDOGO TREBUETSQ LI[X POLINOMIALXNOE WREMQ. iZU^ENI@ TAKIH ZADA^ BUDUT POSWQ-

77

]ENY DALXNEJ[IE PARAGRAFY.

x3. ndmt I KLASS NP

oPREDELENIE 1. nEDETERMINIROWANNOJ MA[INOJ tX@RINGA, SO-

pONQTIE KONFIGURACII I SWQZANNYE S NIM DRUGIE PONQTIQ I OBOZNA^ENIQ TE VE, ^TO I W GL.2.

pRINCIPIALXNYM OTLI^IEM ndmt OT dmt QWLQETSQ TO, ^TO W PROGRAMME NEDETERMINIROWANNOJ MA[INY tX@RINGA MOVET BYTX NESKOLXKO KOMAND S ODINAKOWOJ LEWOJ ^ASTX@. |TO WED<T K TOMU, ^TO IZ ODNOJ I TOJ VE NA^ALXNOJ KONFIGURACII WOZMOVEN PEREHOD K RAZLI^NYM ZAKL@^ITELXNYM KONFIGURACIQM. pO\TOMU, DLQ ndmt TREBUETSQ WNESTI RQD IZMENENIJ W OPREDELENIQ, DANNYE DLQ dmt.

oPREDELENIE 2. kONFIGURACIQ WIDA UqY V NAZYWAETSQ DOPUS-

KA@]EJ.

oPREDELENIE 3. nEDETERMINIROWANNAQ MA[INA tX@RINGA M DOPUSKAET SLOWO U 2 A , ESLI SU]ESTWUET TAKAQ DOPUSKA@]AQ KONFIGURACIQ Kn , ^TO M : K1 ` Kn , GDE K1 = q1U .

oPREDELENIE 4. nEDETERMINIROWANNAQ MA[INA tX@RINGA M RASPOZNAET QZYK L , ESLI L SOSTOIT IZ TEH I TOLXKO TEH SLOW, KOTORYE DOPUSKAET M . |TOT QZYK OBOZNA^AETSQ LM .

oPREDELENIE 5. wREMENEM RABOTY NEDETERMINIROWANNOJ MA- [INY tX@RINGA M NA SLOWE P 2 LM NAZYWAETSQ ^ISLO tM (P) RAWNOE MINIMALXNOMU n , DLQ KOTOROGO SU]ESTWUET POSLEDOWATELXNOSTX KONFIGURACIJ K1 , K2 , K3 , : : : , Kn TAKAQ, ^TO K1 = q1P , Kn { DOPUSKA@]AQ KONFIGURACIQ I M : K1 ! K2 ! : : : ! Kn .

oPREDELENIE 6. wREMENNOJ SLOVNOSTX@ NEDETERMINIROWAN-

NOJ MA[INY tX@RINGA M NAZYWAETSQ FUNKCIQ TM : N ! N ZA78

DAWAEMAQ RAWENSTWOM

TM (n) = maxftM (U) j U 2 LM ;jUj 6 ng:

oPREDELENIE 7. nEDETERMINIROWANNAQ MA[INA tX@RINGA M IMEET POLINOMIALXNU@ WREMENNU@ SLOVNOSTX, ESLI SU]ESTWUET POLINOM p(n) TAKOJ, ^TO DLQ L@BOGO ^ISLA n WYPOLNENO NERAWENSTWO

TM (n) 6 p(n) .

oPREDELENIE 8. qZYK L PRINADLEVIT KLASSU NP , ESLI SU- ]ESTWUET IME@]AQ POLINOMIALXNU@ WREMENNU@ SLOVNOSTX NEDETERMINIROWANNAQ MA[INA tX@RINGA M TAKAQ, ^TO

eSLI ZADA^E RASPOZNAWANIQ SWOJSTW SOOTWETSTWUET QZYK IZ KLASSA NP , TO PRO TAKU@ ZADA^U GOWORQT, ^TO ONA TOVE IZ KLASSA NP . o^EWIDNO, ^TO P NP . wOPROS O SOWPADENII ILI NE SOWPADENII \TIH KLASSOW NA SEGODNQ[NIJ DENX OTKRYT I QWLQETSQ ODNOJ IZ

SAMYH WAVNYH OTKRYTYH PROBLEM W TEORII ALGORITMOW. pROBLEMA. kAKOE IZ SOOTNO[ENIJ IMEET MESTO: P = NP ILI

P 6= NP ?

pOSKOLXKU NA SEGODNQ[NIJ DENX IZWESTNO BOLX[OE KOLI^ESTWO ZADA^ IZ KLASSA NP , DLQ KOTORYH, NESMOTRQ NA MNOGO^ISLENNYE POPYTKI, DO SIH POR NE PRIDUMANY POLINOMIALXNYE ALGORITMY, TO OBY^NO S^ITA@T, ^TO P 6= NP .

x4. pOLINOMIALXNAQ SWODIMOSTX I NP-POLNOTA

oPREDELENIE 1. qZYK L1 A1 NAZYWAETSQ POLINOMIALXNO

SWODIMYM (TRANSFORMIRUEMYM) K L2 A2 , OBOZNA^AETSQ L1 / L2 ,

ESLI SU]ESTWUET FUNKCIQ f : A1 ! A2 , UDOWLETWORQ@]AQ USLOWIQM:

1)FUNKCIQ f MOVET BYTX WY^ISLENA NA DETERMINIROWANNOJ MA[INE tX@RINGA S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@,

2)DLQ L@BOGO SLOWA W 2 A1 WERNO, ^TO W 2 L1 , f(W ) 2 L2 . wAVNOSTX \TOGO PONQTIQ WIDNA IZ SLEDU@]EGO UTWERVDENIQ.

uTWERVDENIE 1. eSLI L1 / L2 I L2 2 P , TO L1 2 P . dOKAZATELXSTWO. pUSTX FUNKCIQ f OSU]ESTWLQET POLINOMI-

ALXNU@ SWODIMOSTX QZYKA L1 K L2 , Mf { DETERMINIROWANNAQ MA- [INA tX@RINGA, WY^ISLQ@]AQ FUNKCI@ f , A M2 { DETERMINI-

79

ROWANNAQ MA[INA tX@RINGA, RASPOZNA@]AQ QZYK L2 , PRI^<M DLQ

NEKOTORYH POLINOMOW pf (n) I p2(n) NERAWENSTWA TMf (n) 6 pf (n) I TM2 (n) 6 p2(n) WYPOLNENY PRI L@BOM n .

rASSMOTRIM MA[INU tX@RINGA M = Mf M2 , RASPOZNA@]U@ QZYK L1 . oCENIM WREMENNU@ SLOVNOSTX \TOJ MA[INY. pUSTX SLO-

NE BOLEE, ^EM p2(jf(W )j) [AGOW. wREMQ RABOTY MA[INY M NA SLOWE W SKLADYWAETSQ IZ WREM<N RABOTY MA[IN Mf I M2 . zNA^IT, tM (W) 6 pf (n)+p2(n+pf (n)) = p1(n) DLQ NEKOTOROGO POLINOMA p1 , WID KOTOROGO NE ZAWISIT OT SLOWA W . pO\TOMU, TM (n) 6 p1(n) DLQ L@BOGO n . sLEDOWATELXNO, DETERMINIROWANNAQ MA[INA tX@RINGA M IMEET POLINOMIALXNU@ WREMENNU@ SLOVNOSTX I L1 2 P , ^TO I TREBOWALOSX DOKAZATX.

oPREDELENIE 2. qZYK L BUDET NAZYWATXSQ NP -SLOVNYM ILI NP -TRUDNYM, ESLI L@BOJ QZYK IZ KLASSA NP POLINOMIALXNO SWODITSQ K L .

oPREDELENIE 3. qZYK L BUDET NAZYWATXSQ NP -POLNYM, ESLI L 2 NP I L QWLQETSQ NP -SLOVNYM.

zADA^I RASPOZNAWANIQ, SOOTWETSTWU@]IE NP -SLOVNYM I NP - POLNYM QZYKAM, TAKVE NAZYWA@TSQ NP -SLOVNYMI I NP -POLNYMI. nEFORMALXNO, IZ OPREDELENIQ 3 SLEDUET, ^TO NP -POLNYE ZADA^I QWLQ@TSQ SAMYMI SLOVNYMI W KLASSE NP , A IZ UTWERVDENIQ 1 POLU^AEM, ^TO NAHOVDENIE POLINOMIALXNOGO ALGORITMA DLQ L@BOJ NP -POLNOJ ZADA^I BUDET OZNA^ATX, ^TO P = NP .

80