Problem P ≠ NP za zdaj ostaja nerešen

Relativno neznani matematik Vinay Deolalikar, ki je zaposlen v Hewlett-Packardu, je prejšnji konec tedna osupnil svet s povsem resno objavo, da je dokazal milenijski matematični problem, da P ni NP. Domnevni dokaz obsega 102 strani in ni le potegavščina, marveč zaresen poizkus dokaza tega problema. Žal po nekaj dneh pregledovanja internetne skupnosti lahko skoraj gotovo zaključimo, da neuspešen.

Clay Mathematics Institute of Cambridge iz Massachusettsa je na prelomu tisočletja razpisal nagrado milijon dolarjev za rešitev vsakega izmed sedmih največjih nerešenih (poimenovanih milenijski) problemov v matematiki. Ti so Swinnerton-Dyerjeva domneva, Hodgeova domneva, Navier-Stokesove enačbe, problem P = NP, Riemannova hipoteza, Yang-Millsova teorija in Poincaréjeva domneva. Od teh čaka na rešitev še prvih šest, medtem ko je zadnjega rešil ekstravagantni ruski matematik Grigorij Pereljman. Ali je P enako NP poenostavljeno povedano vprašuje, ali lahko vsak problem, katerega pravilno rešitev lahko preverimo v polinomskem času, tudi rešimo enako hitro. (Primeri takih problemov so potujoči krošnjar in barvanje grafov.) V matematiki prevladuje mnenje, da to ne drži, a dokaza še ni. Eno izmed področij, ki uporablja prav to vejo matematike, je kriptografija, saj današnji šifrirni algoritmi implicitno privzemajo, da v polinomskem času ni mogoče rešiti nekaterih problemov. Če bi se izkazalo nasprotno, bi bil tu hud udarec za varnost šifriranja, medtem ko bi z dokazom laže spali.

Z objavo novice o omenjenem dosežku smo nekoliko počakali, da se je začetna vznesenost polegla in da so si dokaz ogledali ljudje po vsem svetu. Objava je bila v nasprotju z utečenimi smernicami v matematičnem svetu, saj avtor članek poslal neposredno na internet, ne da bi ga poprej pokazal kolegom (peer review). To samo po sebi seveda ne pomeni nič. V starih časih bi čakali nekaj mesecev, da bi se matematiki po svetu prebili skozi članek, a medmrežje je v 21. stoletju te postopke precej pospešilo in tudi poostrilo. Klasični pregled bi se osredotočil na idejo dokaza. Ključna bi bila njena pravilnost in možnost luknje in pomanjkljivosti v realizaciji popraviti.

Na internetu je vse skupaj mnogo ostreje in v le nekaj dneh so matematiki z vsega sveta preštudirali dokaz ter našteli vse najdene pomanjkljivosti. Deolalikar je že dejal, da bo ta konec tedna objavil popravljeno verzijo, in poudaril, da je že prej povedal, da je trenutna verzija delovna. Usoda tega dokaza ostaja nejasna, a na obzorju se rišejo temni oblaki. Toda spomnimo se Wilesovega dokaza Fermatovega izreka, ki je bil objavljen junija 1993. Kasneje se je pokazalo, da ima resne luknje, a se Wiles ni vdal in je septembra prihodnje leto vsem pričakovanjem navkljub objavil popravljeno verzijo, ki je prestala rigorozen pregled.