Ako ste proučavali prve početke razvoja računala, ili naročito ukoliko ste učili informatiku formalno u nekoj instituciji, velike su šanse da ste bili obasipani s podosta teorije. Koncept bitova kao osnovnih nositelja informacije, von Neumannova arhitektura računala, logički sklopovi, uvod u instrukcije i slične teoretske teme formirane sredinom prošlog stoljeća poslužile su kao čvrsta osnova razvoju hardvera, kao i novim konceptima sagrađenima na tim fundamentalnim temeljima.

I, uzevši u obzir do koje su se razine računala otada razvila, logično je pomisliti da je isto tako i sva teorija do sad već morala biti odavno riješena i poznata. U nekim segmentima ona to i jest, ali suprotno intuiciji na prvu loptu, postoji i podosta neriješenih problema. Naravno, nisu svi jednako složeni niti jednako važni, no ovdje ćemo se pozabaviti onim koji se smatra najtežim i najvažnijim, u smislu da bi njegovo rješenje imalo najveći efekt na ostale probleme iz ovog područja. Kao i većina važnih problema, dobio je i svoje općeprihvaćeno ime ― P versus NP.

Srećom, unatoč težini njegovog rješavanja, ovaj problem nije nerazumno teško shvatiti ― čak bi se moglo reći da je u svojoj pojednostavljenoj verziji zavaravajuće trivijalan. U toj skraćenoj verziji, pitanje otprilike glasi: je li za probleme kojima se ponuđeno rješenje može brzo provjeriti, rješenje jednako brzo moguće i pronaći? No problematika ipak zaslužuje da je istražimo malo detaljnije.

Koliko truda i koliko rezultata?

U računalnoj odnosno teoriji algoritama, točno i jasno definirani problemi ili zadaci imaju svoju razinu kompleksnosti (u pravilu nazivanu vremenskom kompleksnošću). Ona govori koliko broj koraka, tj. operacija potrebnih za pronalaženje rješenja problema raste ovisno o količini ulaznih podataka. Zvuči pomalo apstraktno, ali se može lako predočiti nekim praktičnim primjerima.

Zamislite zadatak, inače klasičan računalni problem, u kojem morate poredati po veličini zadanu količinu nasumičnih brojeva ― za primjer, pretpostavimo da ih ima stotinu. Čak i ukoliko se poslužite nekim vrlo neefikasnim algoritmom, kao što je zamjena mjesta svakih dvaju susjednih brojeva ukoliko su krivo poredani, sve dokle se tako ne poreda svih stotinu (poznato i kao bubble algoritam), u najgorem slučaju za to će vam trebati 4.950 takvih operacija zamjena, u prosjeku daleko manje, ali nikad više od toga.

Taj se prag može poopćiti: za bilo koji broj ulaznih elemenata n, nikad vam neće trebati više od (n²-n)/2 operacija kako biste ih sortirali prema bubble algoritmu. Primijetili ste da formula sadrži n², radi čega i broj potrebnih operacija otprilike raste proporcionalno kvadratu broja ulaznih elemenata koje treba sortirati. U praksi bismo stoga rekli: bubble sortiranje je u klasi kvadratne kompleksnosti. Naravno, postoje i razni drugi problemi čiji algoritmi rješavanja traže broj koraka proporcionalan kvadratu broja ulaznih elemenata. Gotovo svi problemi među kojima treba nešto izvesti sa svakim mogućim parom elemenata, npr. izračunati udaljenost između svih mogućih parova gradova neke države, spadaju u tu kategoriju.

Malo više, malo manje

I dok je bubble sortiranje dakle kvadratne kompleksnosti, postoje i druge varijante. Primjerice, trebamo li provjeriti u skupu ulaznih brojeva koliko je njih neparno, potrebno nam je toliko koraka (toliko operacija provjere parnosti svakog elementa) koliko elemenata nam je i zadano, i prema tome kompleksnost je ovdje linearna. Postoje i problemi gdje kompleksnost raste s trećom, pa i višim potencijama broja ulaznih elemenata ― i time smo se počeli približavati srži stvari.

Ako je kompleksnost zadanog problema i algoritma takva da se maksimalan broj operacija potrebnih za njegovo rješavanje uvijek može izraziti korištenjem jedne ili više potencija broja ulaznih elemenata, kao što su to ovi prethodno spomenuti, nazivamo ih rješivima u polinomijalnom vremenu i zato označavamo slovom P. Možda se sjećate, najvjerojatnije još iz škole, polinomi su matematički izrazi koji sumiraju razne potencije zadane varijable, svaku uz svoji koeficijent ― nešto poput ax³+bx²+cx+d. Rješenje problema može tražiti i broj koraka proporcionalan broju elemenata na tisućitu, ili milijuntu, ili bilo koju višu potenciju, ali radi se i dalje o polinomijalnoj kompleksnosti, dakle o P problemu. Velik udio problema iz svakodnevne prakse spada upravo u ovu kategoriju.

Legenda o NP-u

Apsolviravši koncept P problema, nije teško naslutiti i shvatiti u kojem se smjeru priča razvija dalje. Postoji, naime, čitava masa problema čiji broj koraka, prema danas poznatim algoritmima, potrebnih za rješavanje raste brže od broja ulaznih elemenata na bilo koju potenciju, tj. od bilo koje polinomijalne kompleksnosti.

Klasičan udžbenički primjer je tzv. problem naprtnjače (u literaturi doslovno knapsack problem). Zadan nam je proizvoljan broj predmeta, svaki sa svojom točnom masom, te uz njih, maksimalna masa koju smo u naprtnjači spremni nositi. Cilj je pronaći kombinaciju predmeta koja će biti točno jednaka maksimalnoj dozvoljenoj masi (ili joj najbliža moguća bez da je premaši, što je sad manje važno).

Premisa je jednostavna, no prema današnjem shvaćanju ovog problema, on nema rješenja s polinomijalnom kompleksnošću. Ovdje broj operacija potrebnih za rješenje raste eksponencijalno, tj. proporcionalno određenoj konstanti potenciranoj toliko puta koliko ulaznih elemenata nam je zadano (npr. 2ⁿ ili 4ⁿ), i time naravno raste drastično brže od polinoma.

Opet, u praksi ovakve probleme nalazimo na raznim mjestima, naročito tamo gdje treba promotriti sve moguće podskupove određenog skupa. Premda za mnoge od njih, uključivo problem naprtnjače, postoje algoritmi koji ne traže doista punu 2ⁿ kompleksnost već su nešto efikasniji, i dalje ne toliko da bi im se broj koraka mogao zadati polinomom.

No uočite drugu važnu stvar: kad bi vam netko ― nakon svoje eksponencijalne avanture ― ponudio rješenje problema naprtnjače, provjera točnosti rješenja (odgovara li suma masa željenoj) je trivijalno jednostavna, definitivno P problem. Probleme čija se rješenja mogu provjeriti unutar polinomijanog vremena nazivamo NP problemima.

Točka konvergencije

I sad smo spremni za treći korak, postaviti to ključno P versus NP pitanje oko kojeg se cijelo vrijeme šuljamo. Ono glasi: je li svaki problem kojemu se točnost rješenja može provjeriti u polinomijalnom vremenu isto tako i sâm rješiv u polinomijalnom vremenu? Dakle, je li P=NP?

U prvi mah, zacijelo vam intuicija čvrsto tvrdi da nije, i da nikako to ni ne bi mogao biti. U svakodnevnom životu posvuda imamo situacije gdje je lakše provjeriti da je rješenje točno nego do njega doći. Tako se "po sluhu" čini i u našem probemu naprtnjače.

Usprkos intuiciji, ovo se pitanje pokazalo zapanjujuće teškim. Objavljene su čitave biblioteke radova, kako na području teorije algoritama, tako i primjene u praksi, koji upućuju da je odgovor ― ne. No nitko nije uspio to i konkretno dokazati, kao niti naći neki protudokaz koji bi tu tezu srušio. Već i radi same činjenice da se o ovom problemu ozbiljno i naširoko razmišlja još otkad su postavljeni temelji računalne teorije, a nitko nije uspio naći primjer koji bi tu tezu oborio, mnogi smatraju problem praktično riješenim. Ali zapravo su u pravu oni koji tvrde da to ne treba smatrati dokazom, jer u matematici postoje razni drugi slučajevi problema za koje je trebalo vrlo dugo da se matematički formalno i strogo riješe, katkad i s rješenjem drukčijim od onog koje je većina očekivala. Pojednostavljeno rečeno, i dalje nema garancije da ne postoji algoritam koji bi mogao riješiti neki od ključnih problema u polinomijalnom vremenu. Dokle se on ne pronađe, ili dokle se ne dokaže da on niti ne može postojati, ovo važno pitanje ostaje neodgovoreno.

Uloga u široj slici

Treba priznati da, ovako postavljen, problem može djelovati pomalo opskurno, i nije očito zašto bi njegovo rješenje bilo smatrano važnim, kamoli najvažnijim u modernoj računalnoj teoriji. Ili zašto bi se radilo doslovno o pitanju od milijun dolara; naime, to je iznos nagrade koji je Clay institut ponudio za njegovo formalno rješenje, tj. rješenje sa strogim matematičkim dokazom.

Razloga ima mnogo, jer koji god odgovor na ovaj problem bio, imao bi razne implikacije kako za teoriju tako i za praksu. Jedan primjer koji ima velik svakodnevan utjecaj na nas je kriptografija. Gigantski udio moderne kriptografije temelji se, naime, na RSA konceptu javnih ključeva koji se oslanja upravo na pretpostavku da P nije NP.

Konkretnije, oslanja se na pretpostavku da je faktorizacija (rastavljanje složenih brojeva na prim-faktore) problem nerješiv u polinomijalnom vremenu iako je, očito i naravno, u obrnutom smjeru množenja faktora daleko jednostavniji i polinomijalan. Kad bi netko smislio algoritam koji unutar polinomijalnog vremena može rastaviti gigantske brojeve na dva prim-faktora, vjerojatno bi probio većinu današnje egzistirajuće kriptografije, osim što bi to bio ogroman korak u teoretskom smislu. Naglasak na vjerojatno, jer bi rješenje svejedno moglo ispasti izuzetno nepraktično, tj. polinom bi još uvijek mogao imati previsoke eksponente, ili jednostavnije rečeno, rasti prebrzo za suvremenu tehnologiju.

Ako ste iznenađeni da se apsolutno esencijalan element suvremene kriptografije temelji na pretpostavci koja zapravo nije strogo dokazana, zasad možete nastaviti mirno spavati. Velik udio današnje teorije razvija se s pretpostavkom da a priori P nije jednak NP.

Potencijalni kaos

Stoga, ukoliko bi se ta pretpostavka i dokazala, to bi dalo potvrdu da je naša kriptografija doista sigurna i s teoretske strane. Isto tako, to bi pokazalo da sama teorija tzv. asimetričnih funkcija drži vodu. Radi se o funkcijama poput spomenute faktorizacije, gdje je daleko jednostavnije obaviti transformaciju podataka u jednom nego drugom smjeru. I to ne zato što nismo dovoljno pametni naći neki efikasan algoritam, nego zato što bi taj dokaz potvrdio i da takav algoritam uopće ne može postojati. Uglavnom, većina naših načela i pretpostavki dobili bi i formalni dokaz, i svijet bi uglavnom ostao sličan onome kakvim ga znamo.

Nasuprot tome, dokaz da je P=NP bi bez sumnje izazvao šok, ne samo radi trenutačne tendencije vjerovati u suprotno na osnovi iskustava i prakse, nego i jer bi tako nešto pokazalo da mnogi od naših trenutačnih teoretskih računalnih problema imaju daleko efikasnija rješenja nego što mislimo. Pronalaženje najkraćeg puta koji prolazi kroz sve proizvoljno smještene zadane točke, optimalno rješavanje Rubikove kocke proizvoljne veličine, što je neki od brojnih takvih problema, bili bi definitivno rješivi brže i jednostavnije. Zanima li vas konkretan red veličine, računalni teoretičari imaju nekoliko tisuća takvih realnih problema koji bi izravno bili afektirani dokazom.

Teoretski dokaz ne bi nužno morao izazvati instantno okretanje svijeta naopako, jer on ne bi trebao dati i sam algoritam za ove teške probleme, već "samo" ukazati na to da takav algoritam postoji. Kriptografska zaštita bi možda ostala još sigurna dokle se ne nađe konkretan algoritam efikasne faktorizacije gigantskih brojeva. No ono što bi se dokazom P=NP sasvim sigurno dogodilo je masovni rast istraživanja tih novih algoritama, koji bi isto tako kroz nekoliko godina vjerojatno izazvao svojevrsnu revoluciju računalne teorije ― a potom i tehnologije u širem smislu.

Slijedom svega rečenog, nikog ne treba čuditi što je P versus NP problem predmet velike pažnje znanstvene zajednice. Svakih nekoliko godina negdje iskrsne rad koji tvrdi da je našao dokaz, ali zasad je svima pronađena neka mana, te pitanje ostaje otvoreno (a milijun dolara neuplaćeno). Napredak je spor, i zapravo nema mnogo indikacija jesmo li od rješenja udaljeni tjedan dana, godinu ili milenij.