Gyorshir: P nem egyenlő NP ?
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.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16517184-6ae1dd275571a' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16517184&origin=www.orulunkvincent.hu&obj_id=192691293-16517184-6ae1dd275571a&n=1' data-name='like-post-frame-192691293-16517184-6ae1dd275571a' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>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.
Ha jó lenne esetleg a bizonyítás, akkor azért lenne azért néhány számítástudós, aki hirtelen értelmetlennek érezné az életét, azt hiszem..
De szerintem nem lesz jó..
Ez nagyon érdekes – kár, hogy nem értem. 😉
(Tényleg kár. 🙁 )
Egyáltalán van rá esély, hogy matematikusokon kívül ezt valaki megértse?
De ha már a blogba került, akkor kérdezek:
– Arról van szó, hogy a P-be olyan eldöntési problémák tartoznak, amiket egy Turing-gép meg tud oldani?
– A Turing-gép szekvenciálisan dolgozik. Az általad leírt „baktériumtenyészet-számítógép” ellenben tulajdonképpen tekinthető egyfajta PDP alapon működő gépnek, nem? (Parallel Distributed Processing)
– Ha az előző két kérdésre igen a válasz: akkor ha az indiai fazonnak igaza lenne (a neve alapján gondolom, indiai), az azt jelentené, hogy bizonyos dolgokban egy Turing-gép nem érheti utol a PDP-elven működő számítógépet, ugye?
Elnézést, ha netán fárasztó butaságokat kérdeztem: nem vagyok matematikus, de ha már idetetted ezt a blogba, akkor vállaltad ezt a kockázatot… (Örülj, amíg nem lesz Index-címlapos a poszt! :-))
Remek, de ebből senki nem érti meg.
Talán, ha beleírnád, hogy mit jelent az, hogy egy probléma P-beli, vagy NP-beli, illetve a polinom időt.
Polinom idő: a számításhoz szükséges lépések száma a probléma méretének valamilyen polinom függvénye (pl. N pontos gráfnál N^2+3*N^5) és nem mondjuk exponenciálisan nő vele
P: Amiről tudjuk, hogy lehetséges megoldani polinom idő alatt
NP: Amiről nem tudjuk, hogy lehetséges-e megoldani polinom idő alatt, de azt igen, hogy ha tudjuk a választ, akkor azt letudjuk ellenőrizni polinom idő alatt.
Lefordítva a cikket:
Egy fazon azt állítja, hogy bebizonyította, hogy abból, hogy valamit le tudunk ellenőrizni polinom idő alatt nem következik, hogy meg is lehet oldani polinom idő alatt
Köszönöm, hogy kora reggel beleköthettem valamibe 🙂
„A P=NP probléma azt jelenti, hogy az NP (polinomiálisan ellenőrizhető) problémák P-k (azaz polinomiálisan megoldhatóak). „:
Vincent drága te hogy a fenébe vizsgáztál le ebből? Jó hogy nem érti senki, amikor ilyen sületlenségeket beszélsz!
Az NP az a ‘nem determinisztikus automatával polinom idő alatt eldönthető’, a P pedig a ‘determinisztikus automatával polinomiális idő alatt eldönthető’ konyhenyelven[1].
A probléme meg nem P = NP, hanem P neq NP (P nem egyenlő NP) módon volt mindig is megfogalmazva, ami egy sejtés, csak senki nem tudta bebizonyítani. Ami most a csókának sikerült. Ez azt jelenti, hogy van olyan probléma, amire NP megoldás adható (nem-determinisztikus géppel megoldható polinomiális időben), de P -ben nem (azaz biztosan nincs olyan megoldása, ami determinisztikus automatával, polinomiális időben végrehajtható).
(Annyit persze még érdemes tudni, hogy az összes gyakorlati számítógépünk determinisztikus és a nem polinomiális időben végrehajtható programokat a legtöbb esetben nem győzzük kivárni. Vagyis a bizonyítás azt jelenti, hogy ha sikerül nem determinisztikus számítógpet építenünk, akkor több dolgot tudunk vele eldönteni mint a maiakkal.)
[1] en.wikipedia.org/wiki/NP_%28complexity%29
Egyszer kivágtak szigorlatról, mert nem tudtam, hogy az NP-beli nyelveket a nemdeterminisztikus turing gépek polinom időben ismerik fel.
Azóta tudom, most jobb nekem…? 🙂
nincs azzal semmi baj ha mezei matametikus végzettségűek (én) nem értjük a bizonyítást. ha a tudományos világ elismeri, akkor én el fogom hinni. egyébként pár éve mondta az egyik tanárom, aki DNS informatikát tanított, hogy szerinte a DNS segítségével fogják megoldani a probélmáat.
Akkor itt egy működő link is: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
megprobalom a parasztoknak is erthetove tenni
adott egy labirintus, a kerdes az hogy kepes vagy e kijutni belole mig ehen nem halsz ez a P
es kepes vagy e kijutni e egy olyan labirintusbol ami kifele novekedik? na ez az NP
@$pi$: Elarulnad, mi olyan nagy kulonbseg van Jotunder „polinomiálisan ellenőrizhető” megfogamlazasa es a te „nem determinisztikus automatával polinom idő alatt eldönthető”-d kozott? Foleg az, hogy az elsot van eselye nem-matematikusnak megertenie, a masodikat nincs, de amugy szerintem ugyanaz.
Jotunder, az sulyos eufemizmus, hogy a „számitógéptudomány messze legfontosabb nyitott kérdése”. A teljes eddigi emberi kultura legnagyobb elmeleti kerdese, nem? Wikipediarol idezek, amint Scott Aaronsont (MIT) idez:
If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…
Stiluskritikai alapon tuti nem jo a ficko megoldasa, primitiv az emailje.
Pontosan ez a fogalmi tisztázatlanság járja csárdás macabre-ját azoknak a matematikusoknak a fejében, akik időről időre „eldöntik”, P=NP vagy sem. Tavaly pl. egyenlő volt.
A Kolmogorov-Arnol’d-Moser-elméletről is kisült, hogy vélekedés.
Ahogy Mark Twain mondja: amíg a hazugság háromszor körbeszaladja a földet, az igazság felhúzza a csizmáját.
@egerészölyv:
„A Kolmogorov-Arnol’d-Moser-elméletről is kisült, hogy vélekedés.”
Hogy mi van ??? Naaaa….
@jotunder: nem tűnt még fel neked, hogy nincs bizonyítva? Más kérdés, hogy sok okos ember tesz úgy mély pislantások közepette, mintha ismerné a bizonyítást, sőt, triviálisnak tartaná.
@tanarseged ur: Itt csak olyan kérdésekről van szó amit Turing géppel meg lehet oldani. Az simán azt jelenti, hogy lehet írni rá egy programot. Az a kérdés milyen gyorsan lehet megoldani. A Parallel Distributed algoritmus nem jelenti azt, hogy a processzorok szaporodni tudnak. Úgy képzeld el, hogy a csúcsokra processzorokat ültetsz, azok egymással kommunikálnak, és így próbálják megoldani a feladatot. Mivel polinomiálisan modellezhető egy ilyen helyzet, ez a P=NP ügyön nem változtat.
@egerészölyv:
Arnol’d, V. I. „Proof of a Theorem of A. N. Kolmogorov on the Preservation of Conditionally Periodic Motions under a Small Perturbation of the Hamiltonian.” Uspehi Mat. Nauk 18, 13-40, 1963.
Ez a bizonyítás szerinted hibás ? Meg az a száz cikk ami ezt általánosítja ?
ezzel a mozartos wikis cikkel nem ertek egyet, mert a kreativitas algoritmizalhato
csak megfelelo mintakeszletre es kifejlodott algoritmusra van szukseg
kulonben ha igazi np problema lenne nagy valoszinuseggel csak egy jo alkotast tudna csinalni barki egy emberi elet alatt
ugyanugy ahogy a profi sakkozok verik a gepeket
vagy leforditva a labirintusos peldara ha noveljuk a dimenzio szamot es folulrol nezzuk az algoritmust elobb megleljuk a kiutat
@version: A kreativitás (intuició) algoritmizálhatatlansága alapszinten már a Hilbert féle Entscheidungsproblem bukásából következik. Ennek egy finomitása Aronson maximája.
@jotunder: Arnol’dnak ez az ismert alapcikke csak viszonylag laza kapcsolatban áll az általad is emlegetett „általánosításokkal”, köztük a „KAM”-mal. Utóbbi bizonyítása nem befejezett.
@jotunder: ne vedd a dolgokat tul komolyan , einstein is hibazott, heisenberg meg meg annal is nagyobbat
@version: Rákosi elvtiről nem is beszélve.
@egerészölyv: http://www.scholarpedia.org/article/Kolmogorov-Arnold-Moser_theory
légyszives legalább érintőlegesen mutass rá, hogy miről beszélsz :)))
Sokat javítana a cikk érthetőségén, ha nem lennének benne vesszőhibák. Egy ilyen témánál ez kiemelten fontos.
Egyébként gratulálok a gyors poszthoz a témában.
@version: Hilbert nem hibázott, hanem volt egy sejtése amiről kiderült (mondjuk Gödel vagy Turing miatt), hogy nem igaz. A hiba azt jelenti, hogy valaki megsejt valamit ami triviálisan igaz vagy hamis :))))
@version: „ugyanugy ahogy a profi sakkozok verik a gepeket”
Fordítva. Ma már a gépek verik a profi sakkozókat.
Lehet, hogy a sakkot előbb-utóbb meg fogják oldani. A dámajátékot gyengén már megoldották. (Bizonyították, hogy a kezdőállásból tökéletes játékkal bármelyik fél biztosíthat magának egy döntetlent.)
@jotunder: persze ezek a verziók már helyesek. A nyolcvanas években a nemrezonancia-feltételekkel nagyon szabadon bántak (azaz az eredeti KAM-elméletben). Így aztán szivárgásokba ütközött már maga Arnol’d is.
@jotunder: az biztos a fogalmazas nem az erosseged,
arra meg gyurni kell 🙂
bar alairom a logika sok idegsejtet von el az egyeb felesleges
dolgoktol, de azert nem artana ha a gondolataidat
erthetoen is letudnad irni hogy az egyszeru emberek is
megertsek, mert a matematikus nevekkel
valo vagdalkozas minden, csak nem kifejezo
Ne Turing gépezzetek meg gráfozzatok itt össze-vissza, abból senki nem fogja megérteni, aki eddig nem ismerte.
Inkább egy példa: nyílt kulcsú titkosítás. A titkosítást el tudjuk végezni rövid idő alatt (P), és a kulcs birtokában vissza is tudjuk fejteni rövid idő alatt (P). A kulcsot megfejteni viszont baromi nehéz (NP), sokezer év egy átlag gépnek, szóval biztonságban van az adat. Legalábbis ezt hisszük, de egzaktul bizonyítani mostanáig nem sikerült.
Ha netán P=NP, akkor ez a titkosítás semmit nem ér, mert simán megfejthető a kulcs, mi meg kidobhatjuk a mobiltelefont és a netbankot. És ez csak a jéghegy csúcsa, nagyjából minden mást is kidobhatunk.
@version: ne bántsd. Gyanúm szerint jotunder nem szakmabeli, de lelkes és szeretetre méltó amatőr.
@tanarseged ur: ez nem mond ellent az en allitasomnak
ha az emberi agy algoritmizalja a sakkot , megy az matematikai alapon is , elobb utobb
Elég a hülyéskedésből, jotunder.
Mindvégig csak húztalak ezzel a Kolmogorov-Arnol’d-Moserrel, hogy kiugrasszam a nyulat a bokorból.
🙂
Sikerült, kösz.
@egerészölyv: Gyanúm szerint te nem tudod, miről beszélsz.
@Kettes: Nem tudja. Valahogy azt hiszik menni fog és nem :))))
van ezer ember az orszagban aki melyen erti ezeket a dolgokat
ez becsulendo, nem kell egymasnak ugrani,
ezek nem olyan dolgok amit pistike reggel kifingik,
bar tudom hogy az emberekben tulteng a bizonyitasi kenyszer
@stefan75: Én azért az AKS algoritmus után azt gondolom, hogy a prímfaktorizáció polinomiális csak rohadt nehéz.
@jotunder: Lehetne más példát hozni, én csak arra próbáltam rámutatni, hogy akinek magyarázni kell az NP mibenlétét, az aligha fogja érteni a nemdeterminisztikus automatákat. Aki meg érti, annak fölösleges magyarázni.
Nem kell ezt a hírt annyira azért komolyan venni, eddig is sok próbálkozás volt, itt pl közel 60-at csodálhat meg az érdeklődő:
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
@Kettes: it’s just a conjecture, friend.
Mindenesetre köszönöm, hogy kerülted a „szánalmas vagy”, „nem akarod érteni”, „elgurult a gyógyszered”, „mennyit fizet a központ?”, „végetért az ápolónő műszakja?” stb. kifejezéseket. Ezektől ugyanis elalszom.
Kedves Vincent,
Örülnünk igazából annak kellene, ha az jött volna ki bizonyítottan, hogy P = NP.
Így legfeljebb Deolalikar bácsinak lez jobb, tudtommal a remélhetőleg jó bizonyítással nem kicsi pénzdíjat nyer el…
geomblog.blogspot.com/2004/04/meta-proof.html
@veny: Deolalikar bácsi bizonyítása téves.
még szerencse, hogy idén leszigorlatoztam cs-ből és nem kell megtanulni ennek a bizonyítását. 🙂
@egerészölyv: Deolalikar nem ez a tipus. A végtelen Turing gépre egy osztrák logikus csinálta meg a P nem egyenlő NP-t, ami valamilyen rafinált alkalmazása annak a ténynek, hogy vannak analitikus-nemBorel halmazok és utána az erősebb állítást már Deolalikarral együtt csinálták meg. Ez nem crackpot. Én sem hiszem, hogy jó a bizonyítás, de érdekes dolgokra hívja fel a figyelmet. Ez amúgy NEM a cikk, hanem egy magyarázat. Azt állítja, hogy hamarosan kirakja a végleges verziót.
P = menő
NP = nem menő
@egerészölyv: Ne hibázz többet. 🙂
Egy kis tananyag….
http://www.inf.u-szeged.hu/tanszekek/szamitastudomanyalapjai/szamtudalapjai.pdf
@szamtud:
olyan egyetemi tanagyagban ne higgy ,
ahol meg a quicksortot tanitjak
Vicces, amikor a bölcsészek okoskodnak a bonyolultságelméletről 🙂
@Mister Gumpy: „Elarulnad, mi olyan nagy kulonbseg van Jotunder „polinomiálisan ellenőrizhető” megfogamlazasa es a te „nem determinisztikus automatával polinom idő alatt eldönthető”-d kozott?”
Az a különbség, hogy a „polinomiálisan ellenőrizhető” változat a tanú-tétel, a másik (ndtg) pedig a definíció. A tanú tétel pont azt mondja ki, hogy ez a két dolog ekvivalens, így pl felesleges NP-beliség bizonyítására ndtg-t csinálni, elég tanúval bizonyítani.
Egyébként egy közkeletű tévhit (néhány kommentben is előjön):
Az, hogy valami NP-ben van, NEM azt jelenti, hogy nehéz! Ugyanis minden P-beli automatikusan NP-ben van.
Másik ilyen tévhit, hogy a NPsetminus P -beli problémák (ha léteznek ilyenek) nem megoldhatók. Ez nincs így, aki NP-beli, arra garantáltan létezik exponenciálisnál nem rosszabb algoritmus. Persze az más kérdés, hogy egy exponenciális algo-val mit tudunk kezdeni…
@version: btw mi a baj a quicksort tanításával?
@stefan75: „A kulcsot megfejteni viszont baromi nehéz (NP), sokezer év egy átlag gépnek, szóval biztonságban van az adat.”
P az, csak jó esetben jó nagy értékeket ad az a polinom…
„Ha netán P=NP, akkor ez a titkosítás semmit nem ér”
Erről sincs szó.
Pont mint a nyílt kódú titkosításnál is látszik, sokszor elég a „praktikus megoldhatatlansághoz” az, ha a számításigény ugyan polinomiális, csak kellően nagy.