Problem P = NP ostaja nerešen

Eden izmed najprivlačnejših matematičnih problemov, katerega rešitev bi pomembno vplivala na tudi na računalništvo, je vprašanje ali je P enako NP. Gre za enega izmed sedmih tako imenovanih tisočletnih problemov v matematiki, z rešitvijo katerega lahko od Clay Mathematics Instituta dobimo milijon dolarjev nagrade (kar je nekoliko več od Nobelove nagrade). Doslej je bil rešen samo eden izmed sedmerice problemov. Problem P proti NP sprašuje, ali za vsak problem, katerega rešitev lahko preverimo v polinomskem času, v polinomskem času tudi rešimo. O tovrstnih vprašanjih so se pogovarjali že Nash, Gödel in von Neumann, rigorozno formulacijo pa je leta 1971 postavil Stephen Cook.

Trenutno prevladujoče mnenje v znanosti je, da velja P ≠ NP ali z drugimi besedami, da obstajajo problemi, ki jih lahko preverimo v polinomskem času, rešiti pa jih ne moremo. Takih težkih nalog je precej, denimo potujoči trgovec, barvanje grafov in še več tisoč podobnih. Napisano je seveda poenostavitev, saj ne smemo predvidevati, da so vsi problemi P (rešljivi v polinomskem času) tudi v praksi hitro rešljivi, saj so lahko konstante enostavno previsoke. Prav tako obstajajo algoritmi za sorazmerno hitro reševanje nekaterih NP problemov za določene vhodne podatke.

Poizkusov dokaza v eno ali drugo smer smo videli že mnogo, a doslej si še nihče ni zaslužil milijona dolarjev, saj so vsi vsebovali napake. Enega izmed najnovejših je nemški matematik Norbert Blum predstavil ta mesec. Po sprva pozitivnih reakcijah matematične skupnosti se je vnovič pokazalo, da je dokaz luknjičast. Scott Aaronson z Univerze v Teksasu pravi, da bi upal celo staviti 200.000 dolarjev, da Blumov dokaz ne bo prestal temeljite preveritve. Analiza širše matematične srenje pritrjuje njegovemu mnenju.

Resnica za zdaj ostaja neznana, pri čemer niti ni znano, ali je samo vprašanje P proti NP rešljivo. V aksiomatični matematiki je prav mogoče skonstruirati vprašanje, ki ima rešitev, a je nikakor ne moremo izvedeti. Upamo lahko, da vprašanje ali je P = NP ni te vrste. Če bo komurkoli uspelo rešiti katerikoli NP-poln problem v polinomskem času, bo dokaz s tem že končan, saj so vsi NP-polni problemi ekvivalentni in jih lahko v polinomskem času pretvarjamo enega v drugega. Še najslabši izid bi bil nekonstruktiven dokaz, ki bi samo povedal, da so NP problemi rešljivi v polinomskem času, ne pa tudi kako. Seveda pa je povsem mogoče - če dopustimo demokracijo v matematiki, celo bolj verjetno - da NP-polni problemi v polinomskem času pač niso rešljivi.