Januarski poizkus dokaza problema P = NP neuspešen

Propadel je še en poizkus dokaza slavnega problema P = NP?, za katerega je razpisana nagrada milijon dolarjev in ki vprašuje, ali so vsi problemi, za katere je moč dane rešitve preveriti v polinomskem času, tudi rešljivi enako hitro. Ruski matematik Vladimir Romanov je svoj dokaz objavil januarja letos in na prvi pogled je kazalo, da utegne biti korekten. Izkazalo se je, da milijona dolarjev še ne bo dobil.

Napako je v dokazu po enomesečnem seciranju priznal kar sam avtor, a puške še ni vrgel v koruzo. Zapisal je namreč tudi, da dokaz potrebuje dopolnilo in namignil, da ga bo predložil. Za zdaj pa dodajamo njegov dokaz v dolgo vrsto neuspelih poizkusov, ki smo jih zadnjih 30 let videli že nekaj.

Problem si lahko v tipični slovenski maniri predstavljamo takole. Na banket želimo povabiti 100 gostov, ki jih lahko izberemo iz na primer množice 1000 ljudi. Vsak izmed teh je navedel pogoje, ob katerih se bo banketa udeležil. Ti pogoji so obvezna prisotnost ali odsotnost nekaterih oseb (z nekaterimi so dobri kolegi, z drugimi so sprti) na pogostitvi. Za vsako množico ljudi lahko hitro preverimo, ali ustreza vsem pogojem, medtem ko je poiskati tako množico, ki bo pogojem ustrezala, bistveno teže.

Dokaz, najsi bo odgovor da ali ne, bi imel pomembne posledice za računalništvo. Najočitnejši primer je šifriranje, ki se trenutno opira na nedokazano predpostavko, da P ni enako NP. Če bi uspeli dokazati, da to ne velja, bi to pomenilo, da so šifrirni algoritmi bistveno manj varni, kot smo mislili.