Vinay Deolalikar, znanstvenik iz HP-a koji radi na mrežama i teoriji složenosti, napisao je znanstveni rad u kojem tvrdi da P nije jednak NP. Problem "P naprama NP" postavlja pitanje postoje li problemi čiju istinitost rješenja je lako provjeriti, no sam problem nije lako rješiti.
Matematički problemi koji se nalaze u klasi P su takozvani lagani problemi za koje postoji algoritam s polinomijalnom složenošću, što znači da možemo napisati brzi program koji će rješavati taj problem. Jedan od primjera problema iz klase P je provjera je li neki broj prost. S druge strane, postoje problemi koje je teško riješiti. Ti problemi spadaju u klasu koju matematičari zovu NP. Za njih do sada nismo znali postoji li brzi algoritam kojim ih možemo riješiti.
Čak i ako zanemarimo značaj koji ovaj rezultat ima za znanost, ovo rješenje je i dalje velika vijest jer je "P naprama NP" jedan od Milenijskih problema i rješenje će autoru donijeti nagradu od milijun dolara.
Deolaliker je na problemu radio u svoje slobodno vrijeme i kad je bio zadovoljan rezultatom, dokaz je poslao mnogim vodećim autoritetima za ovaj problem. Dokaz je procurio na internet i njegova točnost još nije povjerena. Međutim, prijašnji Deolalikerovi radovi u kojima je dokazao da je P manji od NP za beskonačne Turingove strojeve nam daju nadu da je dokaz u redu.
Većina računalnih znanstvenika već dugo vjeruje da su P i NP različite klase problema. Stephen Cook i Leonid Levin formulirali su problem P naprama NP davne 1971. godine, iste godine kad je rođen Vinay Deolalikar.
