П = НП проблем

Дијаграм класа комплексности под претпоставком да је П ≠ НП. Постојање проблема који су изван обе класе (и П и НП) је показао Ладнер.

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

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

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

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

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

Историја

О питањима у основи овог проблема први пут се водила дискусија током 1950-их, у писмима Џона Форбса Наша млађег упућеним Агенцији за националну сигурност, и писмима Курта Гедела послатих Џону фон Нојману. Прецизну тврдњу о проблему P насупрот NP увео је 1971. године Стивен Кук у свом семиналном раду с насловом „Комплексност процедура доказивања теорема” (а независно се јавља у раду Леонида Левина из 1973.) и многи га сматрају најважнији отворени проблем у рачунарској науци.

Контекст проблема

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

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

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

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

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

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

Проблем одлучивања се може посматрати као проблем који као улаз узима неку ниску (реч), а као излаз даје да или не. Ако постоји алгоритам (рецимо Тјурингова машина, или рачунарски програм са неограниченом меморијом) који је у стању да да тачан одговор за било коју улазну ниску дужине $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 прихватити? Овај проблем је у НП, јер за дати улаз је једноставно проверити да ли ће га 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$.

Тежи проблеми

Види још: Класа сложености

Иако није познато да ли је П = НП, познати су проблеми изван П. Као што је класа П дефинисана у терминима полиномског времена рада, класа EXPTIME је скуп свих проблема одлучивања који имају експоненцијално време рада. Другим речима, било који проблем у EXPTIME се може решити детерминистичком Тјуринговом машином у O(2^p(n)) времену, где је p(n) полиномска функција од n. Проблем одлуке је EXPTIME-потпун ако се налази у EXPTIME, а сваки проблем у EXPTIME има полиномску вишеструку редукцију. Познато је да су бројни проблеми EXPTIME-комплетни. Пошто се може показати да је П ≠ EXPTIME, ови проблеми су изван П, и стога захтевају више од полиномског времена. У ствари, према теореми о хијерархији времена, они се не могу решити за знатно мање од експоненцијалног времена. Примери укључују проналажење савршене стратегије за шаховске позиције на N × N табли и сличне проблеме за друге друштвене игре.

Проблем одлучивања о истинитости исказа у Пресбургеровој аритметици захтева још више времена. Фишер и Рабин су 1974. године доказали да сваки алгоритам који одлучује о истинитости Пресбургерових изјава дужине n има време извођења од најмање $2^{2^{cn}}$ за неку константу c. Дакле, познато је да проблему треба више од експоненцијалног времена рада. Још тежи су неодлучни проблеми, као што је проблем заустављања. Они се не могу у потпуности решити било којим алгоритмом, у смислу да за било који одређени алгоритам постоји бар један улаз за који тај алгоритам неће дати тачан одговор; или ће произвести погрешан одговор, завршити без давања коначног одговора, или ће на неки други начин трајати заувек без икаквог одговора.

Такође је могуће разматрати и друга питања осим проблема одлучивања. Једна таква класа, која се састоји од проблема са бројањем, зове се #П: док НП проблем пита „Има ли решења?”, одговарајући проблем #П пита „Колико решења има?”. Јасно је да #П проблем мора бити бар исто толико тежак као и одговарајући НП проблем, пошто број решења одмах говори да ли постоји бар једно решење, ако је број већи од нуле. Изненађујуће, неки #П проблеми за које се верује да су тешки одговарају лаким (на пример, у линеарном времену) П проблемима. За ове проблеме је врло лако рећи да ли постоје решења, али се сматра да је веома тешко рећи колико их је. Многи од ових проблема су #П-потпуни, и стога међу најтежим проблемима у #П, пошто би полиномско временско решење за било који од њих омогућило полиномно временско решење за све друге #П проблеме.

Проблеми у НП за које се не зна да су у П или НП-потпуни

Главни чланак: НП-средњи

Године 1975, Ричард Е. Ладнер је показао да ако је П ≠ НП, онда постоје проблеми у НП који нису ни у П ни НП-потпуни. Такви проблеми се називају НП-средњи проблеми. Проблем изоморфизма графа, проблем дискретног логаритма и проблем факторизације целог броја су примери проблема за које се верује да су НП-средњи. Они су неки од ретких НП проблема за које се не зна да су у П или да су НП-потпуни.

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

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

$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)$

да чини n-битни цео број. Најпознатији квантни алгоритам за овај проблем, Шоров алгоритам, ради у полиномском времену, иако то не указује где лежи проблем у односу на неквантне класе сложености.

Да ли П значи „лако”?

Графикон приказује време рада у односу на величину проблема за проблем ранца са најсавременијим, специјализованим алгоритмом. Квадратно уклапање сугерише да је алгоритамска сложеност проблема O((log(n))²).

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

Прво, то у пракси може бити лажно. Теоријски полиномски алгоритам може имати изузетно велике константне факторе или експоненте, што га чини непрактичним. На пример, проблем одлучивања да ли граф G садржи H као минор, где је H фиксно, може се решити у времену рада од O(n²), где је n број врхова у G. Међутим, велика О нотација крије константу која суперекспоненцијално зависи од H. Константа је већа од $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ (користећи Кнутову нотацију стрелице нагоре), и где је h број врхова у H.

С друге стране, чак и ако се покаже да је проблем НП-комплетан, па чак и ако је П = НП, и даље могу постојати ефикасни приступи проблему у пракси. Постоје алгоритми за многе НП-потпуне проблеме, као што су проблем ранца, проблем трговачког путника и проблем Булове задовољивости, који могу оптимално да реше многе стварне случајеве у разумном времену. Емпиријска сложеност просечног случаја (време у односу на величину проблема) таквих алгоритама може бити изненађујуће ниска. Пример је симплекс алгоритам у линеарном програмирању, који изненађујуће добро функционише у пракси; упркос томе што има експоненцијалну временску сложеност у најгорем случају, он ради упоредо са најпознатијим алгоритмима полиномског времена.

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

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

Кук поново наводи проблем у П против НП као „Да ли је П = НП?“ Према анкетама, већина компјутерских научника верује да је П ≠ НП. Кључни разлог за ово уверење је што после деценија проучавања ових проблема нико није успео да пронађе алгоритам полиномског времена за било који од више од 3000 важних познатих НП-потпуних проблема (погледајте Списак НП-потпуних проблема). Ови алгоритми су тражени дуго пре него што је концепт НП-потпуности уопште дефинисан (Карпов 21 НП-потпун проблем, међу првима пронађеним, сви су били добро познати постојећи проблеми у време када се показало да су НП-потпуни). Штавише, резултат П = НП би имплицирао многе друге запањујуће резултате за које се тренутно верује да су погрешни, као што су НП = ко-НП и П = ПХ.

Такође се интуитивно тврди да постојање проблема које је тешко решити, али за које је решења лако проверити, одговара искуству из стварног света.

Ако би П = НП, онда би свет био потпуно другачије место него што обично претпостављамо да јесте. Не би било посебне вредности у „креативним скоковима“, нема суштинског јаза између решавања проблема и препознавања решења када се нађе.

—  Скот Аронсон, УТ Остин

С друге стране, неки истраживачи верују да постоји претерано самопоуздање у веровању у П ≠ НП и да би истраживачи такође требало да истраже доказе о П = НП. На пример, 2002. су дате ове изјаве:

Главни аргумент у корист П ≠ НП је потпуни недостатак фундаменталног напретка у области исцрпног претраживања. Ово је, по мом мишљењу, веома слаб аргумент. Простор алгоритама је веома велик и тек смо на почетку његовог истраживања. [...] Резолуција Фермаове последње теореме такође показује да се врло једноставна питања могу решити само веома дубоким теоријама.

— Моше И. Варди, Универзитет Рајс

Везаност за спекулације није добар водич за планирање истраживања. Увек треба покушати у оба смера сваког проблема. Предрасуде су довеле до тога да познати математичари нису успели да реше чувене проблеме чије је решење било супротно њиховим очекивањима, иако су развили све потребне методе.

—  Анил Нерод, Универзитет Корнел

DLIN vs NLIN

Када се „линеарно време на Тјуринг машини са више трака” замени "полиномским временом" у дефиницијама П и НП, добијају се класе DLIN и NLIN. Познато је да је DLIN≠NLIN.

Литература

• Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 978-0-262-03293-3. 
• Garey, Michael; Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. ISBN 978-0-7167-1045-5. 
• Goldreich, Oded (2010). P, NP, and NP-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2.  Online drafts
• Immerman, N. (1987). „Languages which capture complexity classes”. SIAM Journal on Computing. 16 (4): 760—778. CiteSeerX 10.1.1.75.3035 . doi:10.1137/0216051. 
• Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 978-0-201-53082-7. 
• Rachel Crowell (28. 5. 2021). „The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved”. www.scientificamerican.com. Приступљено 21. 6. 2021. „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).” CS1 одржавање: Формат датума (веза)
• Hosch, William L (11. 8. 2009). „P versus NP problem mathematics”. Encyclopædia Britannica. Приступљено 20. 6. 2021. CS1 одржавање: Формат датума (веза)
• „P vs NP Problem”. www.claymath.org (Cook, Levin). Архивирано из оригинала 18. 06. 2021. г. Приступљено 20. 6. 2021. „"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..."” CS1 одржавање: Формат датума (веза)

Спољашње везе

• Главоломка од милион долара („Политика“, 21. август 2010)
• Fortnow, L.; Gasarch, W. „Computational complexity”. 
• Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation Award.
• „P vs. NP and the Computational Complexity Zoo”. 26. 8. 2014 — преко YouTube.