Dokaz, najsi bo odgovor da ali ne, bi imel pomembne posledice za računalništvo.
V pozitivnem primeru, če je P = NP, bi bile posledice izjemne: v kriptografiji bi se sicer morali vrniti k uporabi one-time padov (ali morda h kaki meni neznani eksotiki), kar se pa tiče drugih področij... pa je le za odtenek pretirano reči, da bi postali praktično bogovi.
Polinomski algoritem za NP-polne probleme bi prinesel preprosto avtomatizacijo celotne matematike, učinkovito, splošno iskanje vzorcev v ogromnih količinah podatkov, kar bi povsem približalo realnosti tudi 'pravo' umetno inteligenco. Hitro sestavljanje urnikov za pristajanje letal in podobne aplikacije, ki se običajno omenjajo, so samo drobtinice. Se pa tega dejstva zaveda le peščica - zaradi česar ga tudi omenjam tule...
Najočitnejši primer je šifriranje, ki se trenutno opira na nedokazano predpostavko, da P ni enako NP.
Dejansko kriptografija počiva na močnejših predpostavkah kot je P != NP, ker je na žalost nihče še ne zna bazirati na NP-polnih problemih. Dokaz, da je P != NP torej ne bi bil dovolj za zagotovitev varnosti današnjih kriptografskih sistemov (z izjemo one-time pada).
Mimogrede, težavnost faktorizacije na kateri je osnovan RSA ni enaka težavnosti NP-polnih problemov - splošno prepričanje v krogih teoretičnega računalništva je, da je faktorizacija eden izmed tistih problemov, ki ležijo med NP-polnimi/težkimi in P problemi.
Če bi uspeli dokazati, da to ne velja, bi to pomenilo, da so šifrirni algoritmi bistveno manj varni, kot smo mislili.
RSA razbijejo že kvantni računalniki, ki sicer niso sposobni učinkovitega reševanja NP-polnih problemov - pri čemer se ob vsem tem opiramo na (zelo trdno) hipotezo P != NP. V nasprotnem primeru pa RSA odpihne že na klasičnih računalnikih, kakor tudi vse druge kriptografske protokole (z že omenjeno izjemo). Torej, ne le da bi bili bistveno manj varni, če velja P = NP, bili bi povsem ne-varni - in hkrati bogovi. :)
V zvezi s P vs. NP dokazi bi še omenil, da bo preteklo še mnogo vode dokler bo sploh mogoča neka realistična možnost za uspešen napad na dokaz. Doslej se je pojavilo kup dokazov raznih crackpotov, peščica resnejših, vendar daleč od pravilnosti in takšno stanje bomo skoraj zagotovo spremljali še mnogo let.
(Nekaj o tem pove tudi nedavna izjava Scotta Aaronsona (theoretical CS wiz-kid), da je pripravljen nagraditi Deolalikarjev P != NP dokaz, v primeru, da bi se izkazal za pravilnega, z 200k$ iz lastnega žepa. Pričakovano se je izkazal za napačnega, pove pa takšna izjava nekaj o tem, kako daleč naj bi po pričakovanjih stroke še bili od pravega dokaza.)
