П = НП проблем

Из Википедије, слободне енциклопедије
Дијаграм класа комплексности под претпоставком да је ПНП. Постојање проблема који су изван обе класе (и П и НП) је показао Ладнер.[1]

Однос између класа комплексности П и НП представља нерешен проблем теоријског рачунарства. Сматра се да је то најважнији проблем у овој научној области - Клејов математички институт је понудио награду од милион америчких долара првој особи која реши овај проблем.[2]

У суштини, питање П = НП? гласи: ако одговори на да-не питање који гласе да могу да се провере брзополиномијалном времену), да ли сами одговори могу да се израчунају брзо?

Као пример може да се узме проблем суме подскупа, проблем код кога је за неко понуђено решење лако утврдити да ли је исправно, али се верује (није доказано) да је проналажење решења тешко. Ако је дат скуп целих бројева, да ли неки непразан подскуп овог скупа има збир једнак нули? На пример, да ли неки подскуп скупа {−2, −3, 15, 14, 7, −10} има збир једнак нули? Одговор да, јер је збир {−2, −3, −10, 15} једнак нули може брзо да се провери помоћу само неколико сабирања. Међутим, за проналажење таквог подскупа би било потребно много више времена. Ако је понуђен одговор на ово питање, тај одговор може да се верификује у полиномијалном времену, тако да овај проблем спада у класу НП.

Одговор на питање П = НП би одредио да ли је проблеме као што је сума подскупа подједнако лако решити као што је лако верификовати њихова решења. Ако би се испоставило да П није једнако НП, то би значило да је неке НП проблеме значајно теже решити него верификовати њихова решења.

Ограничење на проблеме одлучивања (да-не проблеме) није битно; резултујући проблем када се дозволе компликованији одговори (да ли је ФП = ФНП) је еквивалентан.[3]

Контекст проблема[уреди]

Релација између класа комплексности П и НП се проучава у рачунарској теорији комплексности, која се бави ресурсима неопходним током израчунавања како би се решио дати проблем. Најчешће посматрани ресурси су време (колико корака је потребно да би се проблем решио) и простор (колико меморије је неопходно имати).

У таквој анализи је неопходно прецизирати модел рачунара који се користи за израчунавање. Уобичајено је да се претпостави да је рачунар детерминистички (за дато тренутно стање рачунара и за дати било који улаз, постоји само једна могућа акција коју рачунар може да предузме) и секвенцијалан (акције спроводи једну по једну). Данас (2008. година), ове претпоставке су задовољене за практично све рачунаре који постоје, чак и за оне који практикују паралелно израчунавање.[тражи се извор од 06. 2011.]

У овој теорији, класа П се састоји од свих оних проблема одлучивања који могу да буду решени коришћењем детерминистичке секвенцијалне машине у времену које је полиномијално у односу на величину улаза; класа НП се састоји од свих оних проблема одлучивања чија позитивна решења могу да се верификују у полиномијалном времену ако је дата права информација, или еквивалентно, чије решење може да се нађе у полиномијалном времену помоћу недетерминистичке машине.[4] Једно од највећих, ако не и највеће отворено питање теоријског рачунарства се тиче односа између ове две класе:

Да ли је П једнако НП?

2002. године је спроведена анкета међу 100 стручњака и 61 је рекао да верује да је одговор не, 9 је сматрало да је одговор да, 22 није било сигурно а 8 је веровало да је питање можда независно у односу на тренутно прихваћене аксиоме, па би га стога било немогуће ни потврдити нити оповргнути.[5]

Формалне дефиниције за П и НП[уреди]

Проблем одлучивања се може посматрати као проблем који као улаз узима неку ниску (реч), а као излаз даје да или не. Ако постоји алгоритам (рецимо Тјурингова машина, или рачунарски програм са неограниченом меморијом) који је у стању да да тачан одговор за било коју улазну ниску дужине n у не више од c \cdot n^k корака, где су k и c константе независне од улазне ниске, онда се каже да је проблем решив у полиномијалном времену и налази се у класи комплексности П. Формално, П се дефинише као скуп свих језика који могу да буду одлучени детерминистичком полиномијалном Тјуринговом машином. То јест,

П = {L : L=L(M) за неку детерминистичку полиномијалну Тјурингову машину M }

где L(M) = \{ w\in\Sigma^{*}: M \text{ prihvata } w \}

а детерминистичка полиномијална Тјурингова машина је детерминистичка Тјурингова машина M која задовољава следећа два услова:

  1. M се зауставља за сваки улаз w; и
  2. постоји k \in N, такво да T_{M}(n)\in\; O(n^{k}),
где је T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \left|w\right| = n \}
и t_{M}(w) = број корака који су потребни да би се M зауставила за улаз w.

НП може на сличан начин да се дефинише коришћењем недетерминистичке Тјурингове машине (традиционални начин) Међутим, модеран приступ у дефинисању НП подразумева концепт верификатора. Формално, НП се дефинише као скуп свих језика над коначном азбуком, за које постоји верификатор у полиномијалном времену, где се верификатор дефинише на следећи начин.

Нека је L језик над коначном азбуком, \Sigma.

L\in\mathbf{NP} ако и само ако постоји бинарна релација R\subset\Sigma^{*}\times\Sigma^{*} и позитиван цео број k, такав да су следећа два услова задовољена:

  1. За свако x\in\Sigma^{*}, x\in L \Leftrightarrow\exists y\in\Sigma^{*} тако да (x,y)\in R\; и \left|y\right|\in\; O(\left|x\right|^{k}); и
  2. Језик L_{R} = \{ x\# y:(x,y)\in R\} над \Sigma\cup\{\#\} је одлучив помоћу Тјурингове машине.

Тјурингова машина која одлучује L_{R} се назива верификатором за L.

Начелно, верификатор не мора да ради у полиномијалном времену. Међутим, да би L било унутар НП, неопходно је да постоји верификатор у полиномијалном времену.

НП комплетност[уреди]

У решавању питања да ли је П = НП, врло је користан концепт НП-комплетности. Неформално, НП-комплетни проблеми су најтежи проблеми у класи НП у смислу да ако су неки НП проблеми изван класе П, онда су то НП-комплетни проблеми. НП-комплетни проблеми су они НП-тешки проблеми који су у класи НП, а НП-тежак проблем је онај проблем на који се било који проблем из класе НП може свести у полиномијалном времену. На пример, проблем трговачког путника дефинисан у виду проблема одлучивања је НП-комплетан, тако да сваки примерак сваког НП проблема може механички да се трансформише у неки примерак проблема трговачког путника и то у полиномијалном времену, тако да је одговор на почетни проблем да ако и само ако је одговор на добијени примерак проблема трговачког путника да. Проблем трговачког путника је један од многих НП-комплетних проблема. Ако је било који НП-комплетан проблем у класи П, онда би следило да је П = НП. Међутим, иако је за многе важне проблеме показано да су НП-комплетни, још увек није пронађен ниједан брз алгоритам за било који од њих.

На основу саме дефиниције, није очигледно да постоје НП-комплетни проблеми. Тривијалан НП-комплетан проблем би могао да се дефинише на следећи начин: ако је дат опис Тјурингове машине M, за који се гарантује да ће стати у полиномијалном времену, да ли постоји улаз полиномијалне дужине који ће M прихватити?[6] Овај проблем је у НП, јер за дати улаз је једноставно проверити да ли ће га M прихватити простим симулирањем рада M (пустимо машину да изврши израчунавање); НП-тежак је, јер верификатор за сваку појединачну инстанцу проблема у НП може да се кодира у полиномијалну машину M која узима решење као верификован улаз. Онда се питање да ли је инстанца има решење или не решава одговором на питање да ли постоји валидан улаз.

Први природни проблем за који је показано да је НП-комплетан је био САТ-проблем. Ово је резултат Кук-Левинове теореме; њен доказ да је САТ проблем НП-комплетан садржи техничке детаље о Тјуринговим машинама и како се оне односе на дефиницију НП. Међутим, након што је за овај проблем доказано да је НП-комплетан, методом свођења је постало много лакше да се за разне друге проблеме докаже да су у овој класи (простим свођењем на САТ проблем). Тако данас постоји велика класа наизглед невезаних проблема који су сви узајамно сводљиви један на други, па у неку руку представљају исти проблем.

Формална дефиниција НП-комплетности[уреди]

Постоје многи еквивалентни начини да се опише НП-комплетност, али је у контексту питања да ли је П = НП можда најзгодније да се НП-комплетни проблеми дефинишу у односу на НП проблеме.

Нека је L језик над коначном азбуком \ \Sigma.

L је НП-комплетан ако и само ако су задовољена следећа два услова:

  1. L\in\mathbf{NP}; и
  2. свако L^{'}\in\mathbf{NP} је у полиномијалном времену сводљиво на L (што се записује као L^{'}\leq_{p} L), где је L^{'}\leq_{p} L ако и само ако су следећа два услова задовољена:
    1. Постоји f : \Sigma^{*}\rightarrow\Sigma^{*} таква да 
\forall w\in\Sigma^{*}(w\in L^{'}\Leftrightarrow f(w)\in L); и
    2. постоји полиномијална Тјурингова машина која се зауставља са \ f(w) на траци за сваки улаз \ w.


Референце[уреди]

  1. ^ R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
  2. ^ „Millennium Prize Problems“. 24. 05. 2000. Приступљено 12. 01. 2008.. 
  3. ^ Scott Aaronson. Complexity Zoo: FP. "FP = FNP if and only if P = NP". http://qwiki.stanford.edu/wiki/Complexity_Zoo#fp}-
  4. ^ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
  5. ^ Gasarch, William I. (June 2002). „The P=?NP poll.“ (PDF). SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804. 
  6. ^ Scott Aaronson. „PHYS771 Lecture 6: P, NP, and Friends“ Приступљено 27. 08. 2007.. 

Спољашње везе[уреди]