P != NP
Raziskovalec Vinay Deolalikar iz HP Labs je na 102 straneh objavil dokaz, da velja trditev P != NP. Problem P proti NP je eden izmed sedmih milenijskih problemov iz področja matematike, ki jih je leta 2000 objavil Clay Mathematics Institute.
Za rešitev vsakega izmed problemov je inštitut razpisal milijon ameriških dolarjev nagrade, doslej pa ni podelil še nobene, saj je ruski matematik Grigori Perelman, ki je edini rešil katerega izmed problemov (Poincaréjevo domnevo), nagrado zavrnil.
Kaj je sploh poblem P proti NP? V računalništvu lahko probleme uredimo po zahtevnosti (kompleksnosti) rešitve zanje. Z oznako P proti NP označujemo vprašanje, ali je za vse probleme, za katere lahko računalnik hitro oz. v polinomskem času (P) ugotovi pravilnost rešitve, možno tudi poiskati rešitev hitro.
Zaenkrat še nepreverjen dokaz v New Delhiju rojenega raziskovalca trdi, da to ni mogoče.
www.hpl.hp.com/personal/Vinay_Deolalikar/
