Изворни код странице П = НП проблем

[[Датотека:Complexity classes sr.svg|мини|250п|Дијаграм класа комплексности под претпоставком да је '''П''' ≠ '''НП'''. Постојање проблема који су изван обе класе (и П и НП) је показао Ладнер.<ref name="Ladner">-{R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151&ndash;171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site]}-.</ref>]]

Однос између '''[[класа комплексности]] [[П (комплексност)|П]] и [[НП (класа комплексности)|НП]]''' представља нерешен проблем [[теоријско рачунарство|теоријског рачунарства]]. Сматра се да је то најважнији проблем у овој научној области - [[Клејов математички институт]] је понудио награду од милион америчких долара првој особи која реши овај проблем.<ref name="CMI Millennium Prize Problems">{{cite web| title = Millennium Prize Problems| url = http://www.claymath.org/millennium/| date = 24. 5. 2000| accessdate = 12. 1. 2008| archive-date = 08. 01. 2008| archive-url = https://web.archive.org/web/20080108223641/http://www.claymath.org/millennium/| url-status = dead}}</ref>

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

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

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

Ограничење на проблеме одлучивања (''да-не проблеме'') није битно; резултујући проблем када се дозволе компликованији одговори (да ли је [[ФП (комплексност)|ФП]] = [[ФНП (комплексност)|ФНП]]) је еквивалентан.<ref>-{Scott Aaronson. Complexity Zoo: FP. "FP = FNP if and only if P = NP". http://qwiki.stanford.edu/wiki/Complexity_Zoo#fp}- {{Wayback|url=http://qwiki.stanford.edu/wiki/Complexity_Zoo |date=20100726082118 }}</ref>

== Историја ==

О питањима у основи овог проблема први пут се водила дискусија током 1950-их, у писмима [[Džon Neš|Џона Форбса Наша млађег]] упућеним [[Национална сигурносна агенција|Агенцији за националну сигурност]], и писмима [[Курт Гедел|Курта Гедела]] послатих [[Џон фон Нојман|Џону фон Нојману]]. Прецизну тврдњу о проблему -{'''P'''}- насупрот -{'''NP'''}- увео је 1971. године [[Стивен Кук]] у свом семиналном раду с насловом „Комплексност процедура доказивања теорема”<ref>{{Cite book|last=Cook|first=Stephen|authorlink=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapterurl=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pages=151–158}}</ref> (а независно се јавља у раду [[Leonid Levin|Леонида Левина]] из 1973.<ref>{{cite journal |author = L. A. Levin |editor=  |format= |url= http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=914&option_lang=rus |title= Универсальные задачи перебора |type=  |origyear= | agency =  |edition= Problems of Information Transmission  |location=  |date=  1973  |volume= 9 |number= 3|pages = 115–116 |series=  |isbn =  |issn =  |doi =  |bibcode =  |pmid =  |ref=  |archiveurl =  |archivedate =  |language= ru |quote=  }}</ref>) и многи га сматрају најважнији отворени проблем у [[Информатика|рачунарској науци]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | authorlink = Lance Fortnow | year = 2009 | title = The status of the '''P''' versus '''NP''' problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | access-date = 06. 11. 2019 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24. 02. 2011 | url-status = dead }}</ref>

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

У таквој анализи је неопходно прецизирати модел рачунара који се користи за израчунавање. Уобичајено је да се претпостави да је рачунар [[детерминистичко израчунавање|''детерминистички'']] (за дато тренутно стање рачунара и за дати било који улаз, постоји само једна могућа акција коју рачунар може да предузме) и ''секвенцијалан'' (акције спроводи једну по једну). Данас (2008. година), ове претпоставке су задовољене за практично све рачунаре који постоје, чак и за оне који практикују [[паралелно израчунавање]].<ref name="poll"/><ref name="poll2">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The Second '''P'''=?'''NP''' poll|journal=SIGACT News|volume=74|url=http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf}}</ref><ref name="poll3">{{cite web |url=https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf |title=Guest Column: The Third P =? NP Poll1}}</ref>

У овој теорији, класа [[П (комплексност)|П]] се састоји од свих оних ''[[проблем одлучивања|проблема одлучивања]]'' који могу да буду решени коришћењем детерминистичке секвенцијалне машине у времену које је [[полиномијално време|полиномијално]] у односу на величину улаза; класа [[НП (класа комплексности)|НП]] се састоји од свих оних проблема одлучивања чија позитивна решења могу да се верификују у полиномијалном времену ако је дата права информација, или еквивалентно, чије решење може да се нађе у полиномијалном времену помоћу [[Недетерминистичка Тјурингова машина|недетерминистичке]] машине.<ref>-{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.}-</ref> Једно од највећих, ако не и највеће отворено питање [[теоријско рачунарство|теоријског рачунарства]] се тиче односа између ове две класе:
:Да ли је П једнако НП?
2002. године је спроведена анкета међу 100 стручњака и 61 је рекао да верује да је одговор не, 9 је сматрало да је одговор да, 22 није било сигурно а 8 је веровало да је питање можда независно у односу на тренутно прихваћене аксиоме, па би га стога било немогуће ни потврдити нити оповргнути.<ref name="poll">{{cite journal| last = Gasarch| first = William I.| title = The P=?NP poll.| journal = SIGACT News| volume = 33| issue = 2| pages = 34–47| year=2002| url = http://www.cs.umd.edu/~gasarch/papers/poll.pdf| doi = 10.1145/1052796.1052804| format = PDF}}</ref>

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

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

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

а детерминистичка полиномијална Тјурингова машина је детерминистичка Тјурингова машина -{M}- која задовољава следећа два услова:
# -{M}- се зауставља за сваки улаз -{w}-; и
# постоји <math>k \in N</math>, такво да <math>T_{M}(n)\in\; </math> -{[[велико О|''O'']]}-<math>(n^{k})</math>,
::где је <math>T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \left|w\right| = n \}</math>
::и <math>t_{M}(w)</math> = број корака који су потребни да би се -{M}- зауставила за улаз -{w}-.

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

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

<math>L\in\mathbf{NP}</math> ако и само ако постоји [[бинарна релација]] <math>R\subset\Sigma^{*}\times\Sigma^{*}</math> и позитиван цео број <math>k</math>, такав да су следећа два услова задовољена:
# За свако <math>x\in\Sigma^{*}</math>, <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> тако да <math>(x,y)\in R\;</math> и <math>\left|y\right|\in\;</math> [[Нотација великог O|''O'']]<math>(\left|x\right|^{k})</math>; и
# Језик <math>L_{R} = \{ x\# y:(x,y)\in R\}</math> над <math>\Sigma\cup\{\#\}</math> је одлучив помоћу Тјурингове машине.

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

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

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

На основу саме дефиниције, није очигледно да постоје НП-комплетни проблеми. Тривијалан НП-комплетан проблем би могао да се дефинише на следећи начин: ако је дат опис Тјурингове машине -{M}-, за који се гарантује да ће стати у полиномијалном времену, да ли постоји улаз полиномијалне дужине који ће -{M}- прихватити?<ref name="Scott">{{cite web| author = Scott Aaronson| title = PHYS771 Lecture 6: P, NP, and Friends| url = http://www.scottaaronson.com/democritus/lec6.html | accessdate=27. 8. 2007}}</ref> Овај проблем је у НП, јер за дати улаз је једноставно проверити да ли ће га -{M}- прихватити простим симулирањем рада -{M}- (пустимо машину да изврши израчунавање); НП-тежак је, јер верификатор за сваку појединачну инстанцу проблема у НП може да се кодира у полиномијалну машину -{M}- која узима решење као верификован улаз. Онда се питање да ли је инстанца има решење или не решава одговором на питање да ли постоји валидан улаз.

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

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

Нека је -{L}- језик над коначном азбуком <math>\ \Sigma</math>.

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

== Тежи проблеми ==
{{See also|Класа сложености}}

Иако није познато да ли је П&nbsp;=&nbsp;НП, познати су проблеми изван П. Као што је класа П дефинисана у терминима полиномског времена рада, класа [[EXPTIME]] је скуп свих проблема одлучивања који имају ''експоненцијално'' време рада. Другим речима, било који проблем у EXPTIME се може решити [[deterministic Turing machine|детерминистичком Тјуринговом машином]] у [[big O notation|O]](2<sup>''p''(''n'')</sup>) времену, где је ''p''(''n'') полиномска функција од ''n''. Проблем одлуке је [[EXPTIME#EXPTIME-complete|EXPTIME-потпун]] ако се налази у EXPTIME, а сваки проблем у EXPTIME има [[polynomial-time many-one reduction|полиномску вишеструку редукцију]]. Познато је да су бројни проблеми EXPTIME-комплетни. Пошто се може показати да је П&nbsp;≠&nbsp;EXPTIME, ови проблеми су изван П, и стога захтевају више од полиномског времена. У ствари, према [[time hierarchy theorem|теореми о хијерархији времена]], они се не могу решити за знатно мање од експоненцијалног времена. Примери укључују проналажење савршене стратегије за [[шах]]овске позиције на ''N'' × ''N'' табли<ref name="Fraenkel1981">{{Cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for ''n'' × ''n'' chess requires time exponential in ''n''| journal = [[Journal of Combinatorial Theory]] | series=Series A | volume = 31| issue = 2| year = 1981| pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9| doi-access = }}</ref> и сличне проблеме за друге друштвене игре.<ref>{{Cite web|title=Computational Complexity of Games and Puzzles |url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |author=[[David Eppstein]]}}</ref>

Проблем одлучивања о истинитости исказа у [[Presburger arithmetic|Пресбургеровој аритметици]] захтева још више времена. [[Michael J. Fischer|Фишер]] и [[Michael O. Rabin|Рабин]] су 1974. године<ref>{{cite journal | first1=Michael J. | last1=Fischer | author-link1=Michael J. Fischer | first2=Michael O. | last2=Rabin | author-link2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41| access-date=15 October 2017 | archive-url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | archive-date=15 September 2006 }}</ref> доказали да сваки алгоритам који одлучује о истинитости Пресбургерових изјава дужине ''n'' има време извођења од најмање <math>2^{2^{cn}}</math> за неку константу ''c''. Дакле, познато је да проблему треба више од експоненцијалног времена рада. Још тежи су [[undecidable problem|неодлучни проблеми]], као што је [[halting problem|проблем заустављања]]. Они се не могу у потпуности решити било којим алгоритмом, у смислу да за било који одређени алгоритам постоји бар један улаз за који тај алгоритам неће дати тачан одговор; или ће произвести погрешан одговор, завршити без давања коначног одговора, или ће на неки други начин трајати заувек без икаквог одговора.

Такође је могуће разматрати и друга питања осим проблема одлучивања. Једна таква класа, која се састоји од проблема са бројањем, зове се [[Sharp-P#P|#П]]: док НП проблем пита „Има ли решења?”, одговарајући проблем #П пита „Колико решења има?”. Јасно је да #П проблем мора бити бар исто толико тежак као и одговарајући НП проблем, пошто број решења одмах говори да ли постоји бар једно решење, ако је број већи од нуле. Изненађујуће, неки #П проблеми за које се верује да су тешки одговарају лаким (на пример, у линеарном времену) П проблемима.<ref>{{cite journal |author=Valiant, Leslie G. |title=The complexity of enumeration and reliability problems |journal=SIAM Journal on Computing |volume=8 |issue=3 |year=1979 |pages=410–421 |doi=10.1137/0208032}}</ref> За ове проблеме је врло лако рећи да ли постоје решења, али се сматра да је веома тешко рећи колико их је. Многи од ових проблема су [[Sharp-P-complete|#П-потпуни]], и стога међу најтежим проблемима у #П, пошто би полиномско временско решење за било који од њих омогућило полиномно временско решење за све друге #П проблеме.

== Проблеми у НП за које се не зна да су у П или НП-потпуни ==
{{Main article|НП-средњи|l1=НП-средњи}}

Године 1975, [[Richard E. Ladner|Ричард Е. Ладнер]] је показао да ако је П&nbsp;≠&nbsp;НП, онда постоје проблеми у НП који нису ни у П ни НП-потпуни.<ref name="Ladner75" /> Такви проблеми се називају НП-средњи проблеми. [[graph isomorphism problem|Проблем изоморфизма графа]], [[discrete logarithm problem|проблем дискретног логаритма]] и [[integer factorization problem|проблем факторизације целог броја]] су примери проблема за које се верује да су НП-средњи. Они су неки од ретких НП проблема за које се не зна да су у П или да су НП-потпуни.

Проблем изоморфизма графа је рачунарски проблем одређивања да ли су два коначна [[Graph (discrete mathematics)|графа]] [[graph isomorphism|изоморфна]]. Важан нерешен проблем у теорији сложености је да ли је проблем изоморфизма графа у П, НП-комплетан или НП-средњи. Одговор није познат, али се верује да проблем барем није НП-потпун.<ref name="AK06">{{cite journal
 | first1 = Vikraman
 | last1 = Arvind
 | first2 = Piyush P.
 | last2 = Kurur
 | title = Graph isomorphism is in SPP
 | journal = Information and Computation
 | volume = 204
 | issue = 5
 | year = 2006
 | pages = 835–852
 | doi = 10.1016/j.ic.2006.02.002
 | doi-access = 
 }}</ref> Ако је изоморфизам графа НП-потпун, [[polynomial time hierarchy|хијерархија полинома времена]] пада на свој други ниво.<ref>{{cite journal | last1 = Schöning | first1 = Uwe | author-link = Uwe Schöning | year = 1988 | title = Graph isomorphism is in the low hierarchy | journal = Journal of Computer and System Sciences | volume = 37 | issue = 3| pages = 312–323 | doi=10.1016/0022-0000(88)90010-4| doi-access =  }}</ref> Пошто је широко распрострањено веровање да се полиномска хијерархија не урушава ни на један коначни ниво, верује се да изоморфизам графа није НП-потпун. Најбољи алгоритам за овај проблем, због [[László Babai|Ласла Бабаја]], ради у [[quasi-polynomial time|квази-полиномском времену]].<ref>{{cite conference|last=Babai|first=László|contribution=Group, graphs, algorithms: the graph isomorphism problem|mr=3966534|pages=3319–3336|publisher=World Sci. Publ., Hackensack, NJ|title=Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures|year=2018}}</ref>

[[integer factorization problem|Проблем факторизације целог броја]] је рачунски проблем одређивања [[prime factorization|основне факторизације]] датог целог броја. Изражен као проблем одлуке, то је проблем одлучивања да ли улаз има фактор мањи од ''k''. Није познат ефикасан алгоритам за факторизацију целог броја и ова чињеница чини основу неколико савремених криптографских система, као што је [[RSA (algorithm)|RSA]] алгоритам. Проблем факторизације целог броја је у НП и у [[co-NP|ко-НП]] (те чак и у [[UP (complexity)|УП]] и ко-УП<ref>[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). Ако је проблем НП-потпун, хијерархија полинома времена ће се срушити на свој први ниво (тј. НП = ко-НП). [[algorithmic efficiency|Најефикаснији]] познати алгоритам за целобројну факторизацију је [[general number field sieve|сито општег поља бројева]], за које је потребно очекивано време
:<math>O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )</math>

да чини ''n''-битни цео број. Најпознатији [[quantum algorithm|квантни алгоритам]] за овај проблем, [[Shor's algorithm|Шоров алгоритам]], ради у полиномском времену, иако то не указује где лежи проблем у односу на [[quantum complexity theory|неквантне класе сложености]].

== Да ли П значи „лако”? ==
[[File:KnapsackEmpComplexity.GIF|thumb|310 px|Графикон приказује време рада у односу на величину проблема за [[knapsack problem|проблем ранца]] са најсавременијим, специјализованим алгоритмом. [[Curve fitting|Квадратно уклапање]] сугерише да је алгоритамска сложеност проблема O((log(''n''))<sup>2</sup>).<ref name=Pisinger2003>Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark</ref>]]

Сва горња дискусија претпоставља да П значи „лако“, а „не у П“ значи „тешко“, претпоставка позната као ''[[Cobham's thesis|Кобамова теза]]''. То је уобичајена претпоставка у теорији сложености; али постоје упозорења.

Прво, то у пракси може бити лажно. Теоријски полиномски алгоритам може имати изузетно велике константне факторе или експоненте, што га чини непрактичним. На пример, проблем [[decision problem|одлучивања]] да ли граф ''G'' садржи ''H'' као [[graph minor|минор]], где је ''H'' фиксно, може се решити у времену рада од ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{cite journal |last1=Kawarabayashi | first1=Ken-ichi |last2=Kobayashi | first2=Yusuke |last3=Reed | first3=Bruce | authorlink3=Bruce Reed (mathematician) |year=2012 |title=The disjoint paths problem in quadratic time |journal=[[Journal of Combinatorial Theory]] | series=Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> где је ''n'' број врхова у ''G''. Међутим, [[big O notation|велика О нотација]] крије константу која суперекспоненцијално зависи од ''H''. Константа је већа од <math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (користећи [[Knuth's up-arrow notation|Кнутову нотацију стрелице нагоре]]), и где је ''h'' број врхова у ''H''.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>

С друге стране, чак и ако се покаже да је проблем НП-комплетан, па чак и ако је П = НП, и даље могу постојати ефикасни приступи проблему у пракси. Постоје алгоритми за многе НП-потпуне проблеме, као што су [[knapsack problem|проблем ранца]], [[traveling salesman problem|проблем трговачког путника]] и [[Boolean satisfiability problem|проблем Булове задовољивости]], који могу оптимално да реше многе стварне случајеве у разумном времену. Емпиријска [[average-case complexity|сложеност просечног случаја]] (време у односу на величину проблема) таквих алгоритама може бити изненађујуће ниска. Пример је [[simplex algorithm|симплекс алгоритам]] у [[linear programming|линеарном програмирању]], који изненађујуће добро функционише у пракси; упркос томе што има [[time complexity|експоненцијалну временску]] сложеност у најгорем случају, он ради упоредо са најпознатијим алгоритмима полиномског времена.<ref>{{cite book|last1=Gondzio|first1=Jacek|last2=Terlaky|first2=Tamás|chapter=3 A computational view of interior point methods |mr=1438311 |title=Advances in linear and integer programming|pages=103–144|editor=J. E. Beasley|location=New York|publisher=Oxford University Press|year=1996|series=Oxford Lecture Series in Mathematics and its Applications |volume=4 |chapter-url=http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps|id=[http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps Postscript file at website of Gondzio] and [http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz at McMaster University website of Terlaky]}}</ref>

Коначно, постоје типови прорачуна који нису у складу са моделом Тјурингове машине на којем су дефинисани П и НП, као што су [[quantum computation|квантно израчунавање]] и [[randomized algorithm|рандомизовани алгоритми]].

== Разлози за веровање P ≠ NP или P = NP==

Кук поново наводи проблем у ''П против НП'' као „Да ли је П&nbsp;=&nbsp;НП?“<ref name="Official Problem Description"/> Према анкетама,<ref name="poll"/><ref>{{cite journal |title=P vs. NP poll results |journal=Communications of the ACM |date=May 2012 |volume=55 |issue=5 |page=10 |first= Jack|last=Rosenberger |url=http://mags.acm.org/communications/201205?pg=12}}</ref> већина компјутерских научника верује да је П&nbsp;≠&nbsp;НП. Кључни разлог за ово уверење је што после деценија проучавања ових проблема нико није успео да пронађе алгоритам полиномског времена за било који од више од 3000 важних познатих НП-потпуних проблема (погледајте [[List of NP-complete problems|Списак НП-потпуних проблема]]). Ови алгоритми су тражени дуго пре него што је концепт НП-потпуности уопште дефинисан ([[Karp's 21 NP-complete problems|Карпов 21 НП-потпун проблем]], међу првима пронађеним, сви су били добро познати постојећи проблеми у време када се показало да су НП-потпуни). Штавише, резултат П&nbsp;=&nbsp;НП би имплицирао многе друге запањујуће резултате за које се тренутно верује да су погрешни, као што су НП&nbsp;=&nbsp;[[co-NP|ко-НП]] и П&nbsp;=&nbsp;[[PH (complexity)|ПХ]].

Такође се интуитивно тврди да постојање проблема које је тешко решити, али за које је решења лако проверити, одговара искуству из стварног света.<ref>{{Cite web |url=http://scottaaronson.com/blog/?p=122 |author=Scott Aaronson |title=Reasons to believe |date=4 September 2006 }}, point 9.</ref>
{{Blockquote|Ако би П <nowiki>=</nowiki> НП, онда би свет био потпуно другачије место него што обично претпостављамо да јесте. Не би било посебне вредности у „креативним скоковима“, нема суштинског јаза између решавања проблема и препознавања решења када се нађе.| [[Scott Aaronson|Скот Аронсон]], [[UT Austin|УТ Остин]]}}

С друге стране, неки истраживачи верују да постоји претерано самопоуздање у веровању у П&nbsp;≠&nbsp;НП и да би истраживачи такође требало да истраже доказе о П&nbsp;=&nbsp;НП. На пример, 2002. су дате ове изјаве:<ref name="poll" />
{{Blockquote|Главни аргумент у корист П&nbsp;≠&nbsp;НП је потпуни недостатак фундаменталног напретка у области исцрпног претраживања. Ово је, по мом мишљењу, веома слаб аргумент. Простор алгоритама је веома велик и тек смо на почетку његовог истраживања. [...] Резолуција [[Fermat's Last Theorem|Фермаове последње теореме]] такође показује да се врло једноставна питања могу решити само веома дубоким теоријама.|[[Moshe Y. Vardi|Моше И. Варди]], [[Rice University|Универзитет Рајс]]}}

{{quote|Везаност за спекулације није добар водич за планирање истраживања. Увек треба покушати у оба смера сваког проблема. Предрасуде су довеле до тога да познати математичари нису успели да реше чувене проблеме чије је решење било супротно њиховим очекивањима, иако су развили све потребне методе.| [[Anil Nerode|Анил Нерод]], [[Cornell University|Универзитет Корнел]]}}

===DLIN vs NLIN===

Када се „линеарно време на Тјуринг машини са више трака” замени "полиномским временом" у дефиницијама П и НП, добијају се класе [[DLIN]] и [[NLIN]]. Познато је<ref>{{cite book |last1=Balcazar |first1=Jose Luis |last2=Diaz |first2=Josep |last3=Gabarro |first3=Joaquim |title=Structural Complexity II |date=1990 |publisher=Springer Verlag |isbn=3-540-52079-1}}, Theorem 3.9</ref> да је DLIN≠NLIN.

== Референце ==
{{reflist|refs=
<ref name="Ladner75">{{cite journal |first=R.E. |last=Ladner  |title=On the structure of polynomial time reducibility |journal=[[Journal of the ACM]] |volume=22 |pages=151–171 See Corollary&nbsp;1.1 |year=1975 |doi=10.1145/321864.321877 |s2cid=14352974 |doi-access=free }}</ref>
<ref name="Official Problem Description">{{Cite web |last=Cook |first=Stephen |author-link=Stephen Cook |title=The P versus NP Problem |website=[[Clay Mathematics Institute]] |date=April 2000|url=
https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf|archive-url=https://web.archive.org/web/20131216004059/http://www.claymath.org/sites/default/files/pvsnp.pdf |archive-date=2013-12-16 |url-status=live |access-date=18 October 2006}}</ref>
}}

== Литература ==
{{refbegin|30em}}
* {{cite book | last = Cormen | first = Thomas | title = Introduction to Algorithms | publisher = [[MIT Press]] | location = Cambridge | year = 2001 | isbn = 978-0-262-03293-3 | title-link = Introduction to Algorithms }}
* {{cite book | last1 = Garey | first1 = Michael | last2 = Johnson | first2 = David | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = [[W. H. Freeman and Company]] | location = San Francisco | year = 1979 | isbn = 978-0-7167-1045-5 }}
* {{cite book | last = Goldreich | first = Oded | title = P, NP, and NP-Completeness | publisher = Cambridge University Press | location = Cambridge | year = 2010 | isbn = 978-0-521-12254-2 }} [http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html Online drafts]
* {{Cite journal | last1 = Immerman | first1 = N. | title = Languages which capture complexity classes | pages = 760–778 | year = 1987 | journal=SIAM Journal on Computing | volume=16 | issue = 4 |doi=10.1137/0216051| citeseerx=10.1.1.75.3035 }}
* {{cite book | last = Papadimitriou | first = Christos | title = Computational Complexity | publisher = Addison-Wesley | location = Boston | year = 1994 | isbn = 978-0-201-53082-7 }}
*{{cite web
| url = https://www.scientificamerican.com/article/the-top-unsolved-questions-in-mathematics-remain-mostly-mysterious/
| title = The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved
|author =  Rachel Crowell 
|date = 28 May 2021
| work = www.[[scientificamerican.com]]
|archive-url=
|archive-date=
| access-date = 21 June 2021
|quote = This problem concerns the issue of whether questions that are easy to verify (a class of queries called NP) also have solutions that are easy to find (a class called P).}}
* {{cite encyclopedia
| url = https://www.britannica.com/science/P-versus-NP-problem
| last1 = Hosch 
| first1 = William L 
| title = P versus NP problem mathematics
| date = 11 August 2009 
| encyclopedia =[[Encyclopædia Britannica]]
| access-date = 20 June 2021}}
*{{cite web
| url = https://www.claymath.org/millennium-problems/p-vs-np-problem
| title = P vs NP Problem
| work = www.claymath.org (Cook, Levin)
| archive-url = https://web.archive.org/web/20210618205159/https://www.claymath.org/millennium-problems/p-vs-np-problem/
| archive-date = 18. 06. 2021
| access-date = 20 June 2021
| quote = "Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem..."
| url-status = 
}}

{{refend}}

== Спољашње везе ==
{{Commons category|P versus NP problem}}
* [http://www.politika.rs/rubrike/spektar/Nauka/Glavolomka-od-milion-dolara.sr.html Главоломка од милион долара („Политика“, 21. август 2010)]
* {{cite web | last1= Fortnow | first1 = L. | last2 = Gasarch | first2 = W. | title = Computational complexity | url =  http://weblog.fortnow.com }}
* -{[https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-146.pdf Aviad Rubinstein's ''Hardness of Approximation Between '''P''' and '''NP'''''], winner of the [[Association for Computing Machinery|ACM]]'s [https://awards.acm.org/about/2017-doctoral-dissertation 2017 Doctoral Dissertation Award].}-
* {{cite web |title=P vs. NP and the Computational Complexity Zoo |work= |date=26. 8. 2014 |url=https://www.youtube.com/watch?v=YX40hbAHx3s |via=[[YouTube]] }}

{{Нормативна контрола}}
{{портал бар|Информатика}}

{{СОРТИРАЊЕ:НП проблем}}
[[Категорија:Класе комплексности]]
[[Категорија:Математичка оптимизација]]
[[Категорија:Нерешени проблеми у математици]]
[[Категорија:Нерешени проблеми у рачунарству]]
[[Категорија:Конјектуре]]