Augusztus hatodikán egy Vinay Deolalikar nevű matematikus szétküldött egy emailt, amelyben azt állítja, hogy megoldotta a P=NP problémát.
Ez a probléma a számítógéptudomány messze legfontosabb nyitott kérdése, és ha most elég gyors vagyok, a Vincent lesz az első olyan magyar blog, amelyben írunk erről.
Miről van szó? Egy döntési problémát úgy kell elképzelni, hogy valaki leír nekünk egy struktúrát, és arról el kell döntenünk, hogy megfelel-e bizonyos feltételeknek.
Példa. Megad valaki nekünk egy gráfot, aminek n csúcsa van, és el kell döntenünk, hogy kiszínezhetők-e a csúcsai három színnel úgy, hogy a gráfban ne legyen két, azonos színű szomszédos csúcs. Ez a probléma akkor van P-ben, ha van egy olyan programunk, amelynek a gráfok a lehetséges inputjai, és Q(n) lépés után megmondja nekünk, hogy a gráf 3-színezhető-e vagy sem. Itt a Q valamilyen polinom. Ezt nem tudjuk. (Én nem tudom, Deolalikar azt mondja, hogy ő tudja) . Amit tudunk, az az, hogy a probléma az NP osztályban van, azaz ha valaki azt állítja, hogy létezik 3-színezés, akkor azt polinomiális időben ellenőrizni tudjuk. Ez világos, hiszen minden csúcsnál megnézzük a szomszédos csúcsokat, és így n a négyzeten lépésben tudni fogjuk, hogy jó-e a a megadott színezés.
A P=NP probléma azt jelenti, hogy az NP (polinomiálisan ellenőrizhető) problémák P-k (azaz polinomiálisan megoldhatóak).
Számos problémáról sikerült bizonyitani, hogy NP teljes, azaz bármely NP probléma P-ben van, ha ő maga P-ben van (a fenti, 3-színezési probléma is ilyen).
Az NP osztály egyébként pontosan azokból a problémákból áll, amelyeket egy biológiai számítógép polinomiális időben meg tud oldani. Képzeljünk el egy baktériumot, amelynek a DNS-ében ott van a gráfunk, amiről el akarjuk dönteni, hogy kiszínezhető-e három színnel. A baktérium kiválaszt egy csúcsot a gráfban, és három részre osztja magát. Az első utód DNS-e a gráfot tartalmazza, de úgy, hogy a kiválasztott csúcs piros — a második utódnál kék, a harmadiknál zöld. Ezek után a három baktérium elindul, és kiválaszt egy új csúcsot. Ahogy a csúcshoz érnek, osztódnak. Az első utód első utódja a következő DNS-t fogja tartalmazni: az első csúcs piros, a második is piros. Az első utód második utódjában a második csúcs kék, az első utód harmadik utódjában a harmadik utód zöld. A szaporodó baktériumok sorban adják át utódaiknak az információt, és DNS-ükben átörökítik az addigi színezéseket. Ha egy baktérium DNS-e rossz színt kap, tehát szomszédos csúcsok azonos színűek lesznek benne, a baktérium elpusztul. Könnyen látható, hogy ha n idő múlva lesz még élő baktérium, a gráf 3-színezhető (és lesz olyan baktérium, amelynek a DNS-e tartalmazza a színezési információt).
Vinay Deolalikar azt állitja: bebizonyitotta, hogy P nem egyenlő NP-vel, tehát van olyan NP probléma, ami nem oldható meg polinomiális időben.
www.scribd.com/doc/35539144/pnp12pt
Ez a "preliminary version". Belenéztem, valóban elég preliminary, de elvileg elképzelhető, hogy a végső bizonyitás jó (nagyon-nagyon kicsi esélyt látok rá). Alant olvasható Deolalikar emailje.
Dear Fellow Researchers,
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
Comments and suggestions for improvements to the paper are highly welcomed.
