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-6ae1d16a32d46' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16517184&origin=www.orulunkvincent.hu&obj_id=192691293-16517184-6ae1d16a32d46&n=1' data-name='like-post-frame-192691293-16517184-6ae1d16a32d46' 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.
@V8: csak az hogy 15 eve elavult
@version: miért avult volna el? Egyszerűen implementálható, átlagosan nagyon jól viselkedő rendezés.
@veny: Azt azért megnézem hogy bontasz egy számot prímekre polinom idő alatt.
@version: És a jegyzet mely részében is olvastad?
@Sadist: Ez komoly? 🙂
@Sadist: szerintem siman
a 6 primtenyezoi:
az 1
a 2
a 3
ha ez nem polinomialis ido szerinted akkor tanulj meg:)
@V8: a quicksort egy szemet, minden vele valo idotoltes , implementalas , rola valo tanulas csak idopocsekolas
esetleg csak azert jo megtanulni hogyan NE programozzunk
@version: ez elég off, de igazán kifejthetnéd, hogy ezt a véleményedet mire alapozod (és az átlagos 2n ln n + O(n) lépés miért is olyan szörnyű). Valamint helyette milyen rendezést kéne szerinted tanítani.
@veny: Szerintem a prímtényezőre bontás igenis NP, márpedig bizonyos kulcsfejtéshez pont ez kell.
@veny: @version:
Ha ilyen kis butuskák vagytok, miért nem maradtok inkább csöndben? Kevésbé égetnétek magatokat 🙂
Attól, hogy pl. egy TSP-t kiszámolsz egy 5-6 pontú gráfra papíron pár másodperc alatt, attól ugyanúgy NP-teljes marad.
Sőt, vannak olyan problémák, ahol kis inputra még egy exponenciális algoritmus is adhat elfogadható eredményt.
Na, de lássuk milyen fasza gyerkőcök vagytok, bontsátok fel prímtényezőkre 🙂
3782033
Az első három tényező az is elég, onnan már lehet tudni, hogy értitek. Óra indul.
@version: Ha szerinted az 1 primszam, akkor tanulj meg 🙂
Elnézést, én vagyok a hülye, tényleg nincs ismert polinomiális algoritmus a prímfelbontásra (csak kvantumgépre, de ezt most hagyjuk).
@Sadist: 1511 és 2503 a két faktor
@Sadist: arról nem is beszélve, hogy ha az input méretét korlátozod, akkor jó eséllyel konstans időben lehet megoldást adni 🙂
pl ha a probléma az, hogy adott max 1000 pontú gráfban van-e H-kör, akkor azt ellenőrizni, hogy a gráf max 1000 pontú-e, az konstans, majd megvizsgálni az összes lehetőséget szintén konstans (igaz, jó nagy, és használhatatlan, de bonyolultságelméleti szempontból nézzük).
@regression: Jaj, most minek kell ilyen poéngyilkosnak lenni. Olyan vicces lett volna, hogy teleírnak 20 A4-es lapot és tépik a hajukat, hogy nem megy.
@Sadist: Lassan jött le a kávém…
Várom a bizonyításod, hogy a faktorizáció nem P-beli… 😛
(Ezt állítani ugyanis pont akkora butaság, mint az ellenkezőjét.)
@veny: valószínűleg egy szám prímségének eldöntésével keverted. Egyébként ez sokáig egy híres probléma volt, ugyanis az NP-belisége és a coNP-belisége is régóta ismert volt, de a P-beliséget nem is olyan régen bizonyították (ugye van az a kérdés is, hogy NP metszet coNP =? P)
@V8: Az is számít milyen Turing gépet használunk, és mi számít számítási időnek. Ha pl. minden egyes utasítás végrehajtását számoljuk egynek, akkor semmi sem akadályozza meg, hogy definiáljunk egy „keresd meg a Hamilton-kört” utasítást, és ezzel O(1)-es algoritmust kapjunk.
@Sadist: akkor 3782039-et kellett volna írnod, mert az prím.
@regression: Ja és az inputok definiálása sem mindegy. Pl ha úgy definiálunk egy gráfot, hogy minden körét (az összeset) megadjuk, aztán felsorolunk minden maradék élt, akkor az egyértelműen leírja a gráfot. Ugyanakkor a Hamilton-kör probléma triviális lesz, mert csak végiggyaloglunk a leghosszabb megadott körön és megnézzük minden pont benne van-e. (persze itt van pár technikai részlet amit elhagytam, de lényegében O(n) lesz a vége)
@tanarseged ur:
Jelenleg a go a kihívás ha jól látom, de nyilván ez is csak idő és teljesítménynövelés kérdése.
en.wikipedia.org/wiki/Computer_Go#Recent_results
@regression: a Turing-gép nem utasításokkal működik, ezért ilyen „utasítást” nem is definiálhatunk. A lépés definíciója a Turing-gépben egyébként egy állapotváltás (és az ezzel járó írás/fejmozgtás). Az input megadás természetesen nem mindegy.
@V8: „valószínűleg egy szám prímségének eldöntésével keverted”
Ez történt, túl vagyok rajta, bocs + kösz!
@stefan75: Errrr. Hiba. Azt tudjuk, hogy a kulcsfejtés NP beli. De nincs Karp-redukciónk egyetlen NP-teljes problémára sem, ami azt jelenti, hogy hiába igaz a P=NP, még nem tudunk rövid idő alatt RSA-t törni, egyelőre ezek a titkosítások biztonságosak.
Hasonló a helyzet a gráf-izomorfizmussal, vagyis annak az eldöntésével, hogy két gráf azonos-e, csak a csúcsaikat máshogy számozták. Ez is NP-beli, de nem tudjuk, hogy NP-teljes-e. (Ha jól emlékszem.)
@Ianas: egyébként a gráfizo-ra van olyan sejtés, hogy P-beli (meg valahol láttam is róla egy vitatott bizonyítást)
@jotunder: mindenesetre az, hogy Mártonfia tege kétségeket táplál, sokat elárul…
@regression: Az „n” nem mindegy, mi. Ha megadod egy gráf minden körét, akkor egy valódi véletlen gráfnál O(n!) bit információra van szükséged, hogy leírd a gráfot. A Hamilton-kör keresés emiatt sajnos nem redukálódik O(n)-re, mert fel kell dolgoznod az adathalmazt (kivéve, ha mindjárt az első kör a H-kör, de akkor ez egy megkötés az adathalmazra, így meg nyilván triviális a megoldás. Ezzel az erővel azt is mondhatod, hogy ha az input az, hogy van-e H-kör a gráfban, akkor ennek az eldöntése O(1) :D)
@V8: Egy univerzális Turing gépen futtatva egy másik Turing gépet viszont értelmezhető az utasítás fogalma, legalábbis a futtatott Turing gép szempontjából.
@V8: hogy sárga lapú történelemkönyvekbe kívánkozik.
@version: ezt még gyúrd át.
@rg: a kérdés nem eldöntött
@Ianas: Az n az input hossza és nem a gráf pontjainak a száma. Mindig az input hossza számít. Egyébként a problémák pontos megfogalmazásánál erre oda is figyelnek: pl: „Hamilton-kör keresése éllistával megadott gráfon”. Ha még ki is fejtik a pontos kódolást, akkor itt nem lehet mismásolni.
@Ianas: Hozzáteszem, érdekes módon a kulcsfejtés megoldható kvantumszámítógéppel polinom időben, míg az NP-teljes problémák lehetséges, hogy még azzal is exponenciális nehézségűek (sőt, akár a gráfizomorfizmus is.)
Ebből nem következik, hogy a prímtényezős felbontás (ami a kódfejtés alapja) polinom idejű. Lehet, hogy ez egy kivételesen szerencsés NP-beli nem-P probléma. (Lehet, hogy P QP-nek valódi részhalmaza, vagyis a kvantumszámítógéppel polinom időben megoldható problémák között van olyan, ami nem P-beli, de emellett az is igaz lehet, hogy QP pedig NP valódi részhalmaza.)
@regression: A polinomitás szempontjából mindegy, hogy n a pontok száma, vagy a mátrix elemeinek a száma. Ha viszont azt mondod, hogy n a körmátrix elemeinek a száma, akkor valóban van polinomiális megoldás, csak a körmátrix mérete O((n+1)!)…
@Ianas: arról nem is beszélve, hogy a „polinomiális” és „exponenciális” nem teljes eseményrendszer.
@Ianas: Ugyanarról beszélünk. Amikor egy eldöntési problémát megfogalmazunk akkor az input hossza számít, ezért kell odafigyelni a probléma definíciójánál az input pontos formátumának megadására. Ellenkező esetben lehet ilyen bugyuta inputokat megadni mint amit én is meg te is mutattunk.
@version: A primtényezős felbontás nem polinomiális idejű probléma. Végig kell ugyanis nézni az összes prímet a szám négyzetgyökéig, hogy megnézd, osztója-e a számnak. Most ne ilyen számokra gondolj, hogy 15.
Pl. egy 1024 bites szám négyzetgyöke 512 bites. Ennek megfelelően meg kell nézned 2^512 ~= 10^154 szám közt található prímekkel való oszthatóságot. Namost elvileg ugyan a prímek száma N-ig ln(N), ha létezne egy algoritmus, amelyik felsorolja a prímeket polinom időben, lehetne polinom idejű prímtényezős felbontást csinálni, ilyen algoritmus még nincs.
@Ianas: MÉG nincs – tehát bizonyítás nincs reá, miért ne lenne polinomiális a prímfelbontás.
@Ianas: Bocsánat. Hülyeséget mondtam. 🙂
„Namost elvileg ugyan a prímek száma N-ig ln(N), ha létezne egy algoritmus, amelyik felsorolja a prímeket polinom időben, lehetne polinom idejű prímtényezős felbontást csinálni, ilyen algoritmus még nincs. „
Ez NEM igaz. 🙂 A prímek száma kb. N/ln(N), vagyis akkor sem lenne ilyen elven működő polinom idejű algoritmus, ha polinom időben lehetne generálni egy prím után következő prímet.
@egerészölyv: Ld. következő kommentem. Amúgy senki sem mondta, hogy nem lehet polinom időben prímtényezős felbontani, csak az a sejtés, hogy valószínűleg hagyományos géppel nem lehet polinom időben. Mint fentebb írtam, kvantumszámítógéppel lehet, úgyhogy 10-15 év múlva a ma használt titkosítások elavulttá válnak.
@Ianas: Azt polinomiális időben el lehet dönteni hogy egy szám prím.
en.wikipedia.org/wiki/AKS_primality_test
A felbontásról ugye könnyű látni, hogy NP
en.wikipedia.org/wiki/Integer_factorization
ergo nem állíthatsz olyat, hogy nincs rá polinomiális algoritmus, hiszen akkor tudnád, hogy P nem NP.
@Ianas: Biztos vagy benne hogy az egyetlen lehetoseg minden primet vegigprobalni?
@jotunder: MÉG nincs. De nem úgy volt igaz, amit írtam, ld. következő kommentem.
Amúgy abból, hogy polinom időben eldönthető, hogy egy szám prím-e, nem következik semmi a prímtényezős felbontásra nézve, legfeljebb annyi, hogy nem LEHETETLEN, hogy P-beli legyen.
@xstranger: Nem, én is gondolkodtam már más megoldáson, de sajnos jelenleg nem ismerünk más lehetőséget.
De mivel a P=NP kérdés nem eldöntött (ha igaz lenne, biztosan lenne más megoldás), sajnos sokat nem lehet mondani még. (Amúgy, ha az igaz, hogy P!=NP, sajnos még mindig nyitott a kérdés, hogy P=QP, vagy specifikusabban, hogy a prímfelbontás P-beli-e. Vagy nem sajnos, ha azt akarjuk, hogy a számításelmélészek ne haljanak éhen.)
@Ianas: Azt tudják, hogy a faktorizáció BQP és azt gondolják, hogy nemcsak P de még BQP sem egyenlő NP-vel.
@Ianas: Azért attól sem kell mindjárt apokalipszist jósolni, ha NP=P igaz lenne. Attól még mert valami P-beli, nem jelenti azt, hogy praktikus a gyakorlatban. Egy n^(10^100000) rendű algoritmus is P-beli, de attól még nem biztos, hogy örülünk neki. Gyakorlatban már egy köbös rend is eléggé elszomorító. Arról nem is beszélve, hogy egy konstans tényező is ott van. Nem féltem a számításelmélészeket az éhenhalástól.
Egy érdekes cikk ami egyben rávilágít az O(.) visszásságaira is indirekte:
„The Fastest and Shortest Algorithm for All Well-Defined Problems”
http://www.hutter1.net/ai/pfastprg.ps
@Ianas:
„Azt tudjuk, hogy a kulcsfejtés NP beli. De nincs Karp-redukciónk egyetlen NP-teljes problémára sem, ami azt jelenti, hogy hiába igaz a P=NP, még nem tudunk rövid idő alatt RSA-t törni, egyelőre ezek a titkosítások biztonságosak.”
Hogy lehet ilyet leírni ? :))) Ez hihetetlen, valaki a gondolat patternjével tudja magát azonosítani. Némo kapitány, ugye….
@jotunder: Kicsit fáradt vagyok, lehet, már azt sem értem, amit én magam leírtam. De hogy Némó kapitány hogy úszott ide, azt most tényleg nem vágom 😀
@regression: Ez így van, gyakorlati jelentősége még a P=NP-nek sem feltétlenül lenne.