Problém P versus NP vyřešen

Pravděpodobně byl vyřešen jeden z problému teoretické infomatiky. P!=NP. A Proof That P Is Not Equal To NP?, Issues In The Proof That P≠NP.

10.8.2010 22:32 | faha | Zajímavý článek

Komentáře

[Roger]

Vyresen? VYRESEN? Ach jo, AbcBlesku.cz?

Pokus o dukaz, navic prvni (unikla) verze. Chapu nadseni, taky jsem velice zvedavy (sam bohuzel nemam dost vedomosti, abych to pochopil), ale tyhle unahlene zavery me zacinaji docela stvat.

Napriklad u Poincareho trvalo sedm let, nez Perelmanovi priznali zisk Millenium prize (a o nejake dva roky mene, nez mu obecne uverili - a to jeste vyzadovalo od zverejneni spoustu prace na doplneni toho dukazu). Takze trochu mene ukvapenosti a vic soudnosti, prosim...

[Martin]

Taky bych uvítal, kdyby někdo zprávičku trochu přeformuloval.

[Martin]

Ono se totiž hned ve druhém uvedeném odkazu hovoří o nedostatcích onoho důkazu (který je navíc pouhým draftem), což je trochu v rozporu se zněním zprávičky.

[disorder]

no, s tym uverenim zase nebude problem, kedze predpokladame, ze P != NP

[Marek Bernát]

Kto vy? Ak si pozrieš mnou citovaný odkaz nižšie, tak máš desiatky článkov pre oba prípady. Tak isto aj dnes je kopa ľudí, ktorí veria, že P = NP. Ja osobne sa tiež prikláňam k P != NP, ale bez dôkazu je to len o viere

[disorder]

tak napriklad cela asymetricka kryptografia?

[Marek Bernát]

Blbosť. Aj keby sa dokázalo P = NP, tak to predsa neznamená, že okamžite budeme všetko vedieť riešiť efektívne. V skutočnosti, či už sa už dokáže = alebo !=, tak sa nezmení vôbec nič

[Marek Bernát]

Samozejme, výnimkou by bolo, keby niekto našiel polynomiálny algoritmus na riešenie NP-úplných úloh. Ale keď si človek pozrie tie predchadzajúce pokusy o dôkazy P = NP, tak vidí, že obvykle ide o prístupy pomocou nejakých teórií a existenčných viet; algoritmy moc ľudí nehľadá

Btw, sú aj také názory, že P != NP je nezávislé na axiómoch teórie množín, že je to nedokázateľné, neoveriteľné, nerozhodnuteľné, ... Zaujímavosťou je napr. aj Relativization barrier pri prístupe k riešeniu, kde sú možné obe odpovede P=NP aj P!=NP, podľa toho, v akom svete presne žiješ. V skutočnosti to ukazuje len toľko, že isté metódy sa nedajú použiť na rozhodnutie tej otázky.

[disorder]

neznamena to, ze budeme vediet riesit, ale ze riesenie existuje

moje tvrdenie plati

[Marek Bernát]

A čo z toho? Existenčné vety si môžeš maximálne tak strčiť za klobúk V praxi by sa nezmenilo vôbec nič, pokiaľ by to riešenie skutočne niekto nenašiel.

Ktoré tvrdenie? To s otáznikom o kryptografii? Som nevedel, že opytovacou vetou sa dá niečo tvrdiť Alebo to, že predpokladáte (ty a možno ešte niekto), že P != NP?

[disorder]

We would know from the proof that such algorithms would exist, and possibly get a method from the proof as to how formulate them.

[Marek Bernát]

Possibly budú o pár rokov fungovať kvantové počítače, ktoré vedie rýchlo faktorizovať aj počítať diskrétne logaritmy. Podobných possibly existuje milión, ale nezdá sa mi, že by to niekoho trápilo

[disorder]

podla mna je to celkom dost jasne, ze ked ti niekto vymysli dokaz, tak bude vediet ako a preco funguje

inak Magic quantum wand does not vanish hard math, pan vseveduci

[Marek Bernát]

Je jasné, že bude vedieť ako funguje ten dôkaz. Ale už nie je jasné, že sa podľa neho bude dať skonštruovať nejaký algoritmus. To závisí od konkrétnej formy dôkazu.

Dík za zaujímavý článok. Takže jedno possibly je asi von z hry

[Bilbo]

Ne kazdy dukaz je konstruktivni - je celkem dost dukazu, ktere dokazuji, ze neco existuje, ale ani v nejmensim nenaznacuji jak to aspon priblizne vypada. Vcelku casty pripad u dukazu sporem - dokazu treba, ze neexistence neceho nutne nekde vede ke sporu, tedy ze to musi existovat, nicmene tim nedam zadny navod jak danou vec sestrojit.

Takze i kdyby nekdo dokazal, ze P = NP (osobne si spis myslim, ze plati P != NP, ale dukaz na to nemam :), tak od takoveho dukazu k nejakemu aspon trochu pouzitelnemu algoritmu na prevod NP problemu na P by mohla byt jeste hooodne dlouha cesta.

[Marek Bernát]

Presne tak.

[egg]

On snad někdo dokázal, že faktorizace je NPC?

[Marek Bernát]

Hehe, tiež pravda. Dokázanie P != NP nehovorí vôbec nič o tom, kam konkrétne v NP faktorizácia patrí

[Marek Bernát]

Som čakal kedy sa to tu objaví Ten problém rozhodne vyriešený nie je. Čo je už takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje Samozrejme, za tých pár dní nie je možné 100-stranový článok kompletne overiť, ale už teraz je jasné, že má poriadne slabiny na niekoľkých úplne rôznych miestach.

Ale inak je to moc fajn článok, lebo autorovi sa podarilo prepojiť na pohľad nie veľmi súvisiace obory (logika, model theory, complexity theory, štatistika). Ja som napr. zistil, že problémy z teórie komplexity k-COL a k-SAT sa po novom riešia pomocou metód štatistickej fyziky z modelov spinových skiel, ktorým som sa trochu venoval. Takže ak nič iné, tak je to príjemný úvod do rôznych matematicko/informaticko/fyzikálnych oblastí

[jehovista]

Ja jsem cumel jak puk. Na pochopeni toho "dukazu" sice nemam, ale kdyz jsem si to prosel, tak jsem tam nasel snad vetsinu oboru, do kterych jsem v prubehu studia FELu nahledl.

[Jakub Suchy]

To, jestli ten problem vyreseny je nebo neni, bych rozhodne nesoudil. Odkazy, na ktere linkujes, mluvi o "issues" v tom paperu. Tzn. potencialni problemy, ktere samozrejme probelmy ve skutecnosti byt nemusi. Takze bych si pockal (par let)

[Marek Bernát]

To isté som predsa napísal aj ja. Čo tak sa naučiť trochu čítať?

[nikdo]

Ne, píšeš, že důkaz nefunguje.

[Marek Bernát]

Naozaj odporúčam naučiť sa čítať. Nie je to tak ťažké. Začni šlabikárom a potom rozpravkovými knižkami. Časom to pôjde

[nikdo]

cit: Čo je už takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje.

cit: Samozrejme, za tých pár dní nie je možné 100-stranový článok kompletne overiť

Kromě jistého rozporu ("takmer vyriešené" versus "nie je možné 100-stranový článok kompletne overiť" - jaký je přesně význam slova "takmer" a "kompletně"?) v první větě čtu, že "tento dôkaz, podobne ako desiatky pred ním, nefunguje". Zvlášť doporučuju soustředit pozornost na přirovnání tohoto důkazu k již vyvráceným předchozím pokusům ("podobne ako desiatky pred ním, nefunguje").

Je možné, že jsi svá slova myslel trošku jinak. Ale pak piš buď jasněji, nebo si odpusť svoje poněkud arogantní poznámky o čtení. Děkuju.

[Marek Bernát]

Žiadny rozpor tam nie je. Z toho, čo je zatiaľ známe (napr. aj z tej odkazovanej wiki, ktorú vedie jeden z expertov, ktorí ten dôkaz skúmajú), to zatiaľ vyzerá skôr tak, že ten dôkaz nefunguje, než funguje (veľmi pravdepodobne nefunguje v súčasnej podobe a je veľká otázka, či sa dajú tie spomínané problémy opraviť). Tiež za pozornosť stojí, že autor ten dôkaz stiahol zo svojej stránky

Tak či onak, rozhodne som nenapísal, že ten dôkaz nefunguje, len jak to s ním momentálne vyzerá (preto slovíčko takmer a preto osvetľujúca veta o overovaní veľkých dokumentov). Ja ťa teda poprosím, aby si mi do úst (podobne ako tvoji kolegovia), nevkladal niečo, čo som nepovedal (totiž že prezentujem ako fakt, že ten dôkaz nefunguje). Neviem, či si to urobil preto, lebo nevieš čítať, alebo to mal byť zámerný útok (a je mi to jedno), ale nesnaž sa mi tu podsúvať niečo o tom, jak mám ja písať, keď to ty aj tak poriadne nečítaš (či už zámerne, alebo omylom)

[podlesh]

No, nezbývá než závidět. To musí být krásný život, být tak arogantní.

[Marek Bernát]

Tak prepáč, že mi vadí, keď mi ľudia vkladajú do úst vety, ktoré som nepovedal a bránim sa proti tomu. Ak si myslíš, že je to prejav arogancie, tak už neviem...

[Bedňa]

Marek ty píšeš:

Čo je už takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje

Nikto píše:

Ne, píšeš, že důkaz nefunguje.

Ty píšeš:

Naozaj odporúčam naučiť sa čítať. Nie je to tak ťažké. Začni šlabikárom a potom rozpravkovými knižkami. Časom to pôjde

[Marek Bernát]

Ale tá veta obsahuje viac než jedno slovo. Špecificky je tam slovíčko takmer, ktoré úplne mení význam a ktoré tu z mne neznámeho dôvodu každý ignoruje. Z pravdepodobnosti P=1 (čo mi vkladajú všetci do úst) na p < P < 1, kde p je rozumne veľká pravdepodobnosť (povedzme 0.5). To tu fakt nikto nie je schopný pochopiť?

[Bedňa]

Od teórie ktorá aj tak dokazuje ... sme sa dostali k teórií o zložení vety. To mi pripomína "skoro tehotná" proti tomu obchodný cestujúci je hadr.

[Marek Bernát]

Ten dôkaz je pochopiteľne buď platný alebo nie, takže je to binárny stav. Ale názor komunity na stav toho dôkazu, ten už patrí do podstatne väčšej množiny Podobne by sa dala spraviť anketa o tom, či je Zuza tehotná a ak by si 80% opýtaných myslelo, že áno, tak by určite bolo správne použiť výraz skoro tehotná

[Bedňa]

Ako si vedel ako sa moja volá, kurňa

[Marek Bernát]

To nechám na tvojej fantázii

[nikdo]

Doba na ověření toho důkazu je rozhodně mnohem delší, než je pár dní od leaku. Sám to podle všeho víš. Nicméně předkládáš jako fakt, že "possible issues" z citovaného zdroje znamenají, že "takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje.". To není korektní. Possbile issues neznamená "takmer vyriešené". Zvlášť v kombinaci s tím přirovnáním k předchozím pokusům o důkaz, kde to již vyřešené je.

Změkčení v další větě na tom nic nemění, zvlášť když v ní říkáš "kompletne overiť", jako by snad ta věc byla již ověřena aspoň z podstatné části, když máš potřebu dodat "kompletne". Měl jsi to naformulovat jinak. Například: "Je jisté, že linkovaný pokus o důkaz má mnohá sporná místa, jejichž ověření bude trvat delší dobu a proto bychom o této práci neměli ještě hovořit jako o důkazu, zláště když se dle mého názoru zdá, že ona slabá místa budou pro důkaz fatální". Pak by nikdo nic nenamítal a nemuseli bychom se tady dohadovat o významu tvých slov.

Pokud máš nějaké informace, které my nemáme (tedy že je skutečně téměř jisté, že důkaz nefunguje), měl jsi linkovat zdroj (a to není ona wiki), který ti ty informace dodal.

[Marek Bernát]

A ty si myslíš, že každý môj komentár je sloh, ktorý si pripravujem 10 hodín, následne formálne dokazujem každú vetu a potom ešte proof-readujem? Bol to preboha len jeden rýchly komentár, v ktorom nie je žiadna kvalitatívna chyba, len sa dal formulovať trochu inak (s väčšou mierou neistoty).

Btw, keď už chceš kritizovať štýl písania -- čo tak začať od seba? Lebo tvoj prvý komentár mi vložil do úst niečo, čo som nepovedal a horší štyl argumentácie si predstaviť neviem. Sa potom nečuduj, že sa s tebou bavím tak, ako sa bavím Keby si napísal hneď na začiatku niečo duchu tohoto najnovšieho príspevku, tak by som uznal chybu. Aj keď by som si zaklopal na čelo, že prečo má niekto potrebu exaktne validovať moje komentáre na abíčku...

[rainman]

... Ten problém rozhodne vyriešený nie je. Čo je už takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje ...

Obávám se že tobě, stejně jako drtivé většině čtenářů, chybí tak hluboké a komplexní znalosti matematiky, aby's dokázal "posoudit" že tento důkaz "nefunguje" a vydával to za "fakt". Koukám na tomhle webu spolu s "důkaz" hodně zprovanovaná slova.

Ten draft teprve bude po typografické korektuře bude publikován v odborném tisku a bude podroben peer-review, které může trvat několik let. Ty odkazované "issues" zatím vůbec nic neznamenají.

[Marek Bernát]

Ja neviem, či ľudia už fakt nevedia čítať, ale pre istotu to sem napíšem znovu a vysvetlím, lebo ma to prestáva baviť:

Čo je už takmer vyriešené je fakt, že tento dôkaz, podobne ako desiatky pred ním, nefunguje Samozrejme, za tých pár dní nie je možné 100-stranový článok kompletne overiť, ale už teraz je jasné, že má poriadne slabiny na niekoľkých úplne rôznych miestach.

Sústredťe sa prosím na tučne vyznačený text. Až dokážete týchto pár viet vstrebať a pochopiť, tak snáď konečne prestane písať tieto hlúpe reakcie (nielen Vy, ale aj ostatní). Ospravedlnenie nečakám, ale pre budúcnosť sa naučte čítať...

[Jardík]

Já jsem to vyřešil. Vesmír je konečný, jeho tvar je dokonalá čtyřrozměrná koule, která je vepsaná pětirozměrné krychli, která je vepsaná dodecahedronu. Ten má na provázku vymotaného z klubíčka přivázána amigapowerova kočka a až se klubíčko rozmotá úplně, tak ji zašlápne mravenec ve formě prasete od koryta jménem dosaďsisvéhopolitika. Za politikem už není nikdo, on je konec i začátkem všeho. A Jardík je kretén.

[Mrkva]

Ale, kolik jsi toho zas vypil?

[Zopper]

Pokud je na tom jako já, tak nemusel pít nic. Já jsem schopný takovéto krásné žblepty tvořit zcela střízlivý :D

[tsLnox]

Jardo dík Sem se v práci aspoň pobavil :-P

[Šangala]

¡Super!, to je tvůj první příspěvek, kterému rozumím. Teď vím, že dnes bude super den - dík :)

[Bedňa]

Ale to platí len pre 32 šmejďárny :) V reálnom svete sú tam politici dvaja jeden sa volá začiatok a druhý koniec, len stále neviem ktorý je ktorý.

[jos]

podle Edgara Malroye je zase docela dost dobře možný, že vesmír má tvar vagíny

[Zdenek.Z]

Titulek: Problém vyřešen.

Obsah: Ono se vlastně neví, jestli byl vyřešen nebo ne.

Na Živě mě to nepřekvapilo. Tady ano. Trochu serióznosti by neuškodilo, zvlášť když zatím nikdo (včetně autora důkazu) neví, jestli není důkaz chybný.

[Zdenek.Z]

A mimochodem, P != NP už dávno bylo dokázáno hlasováním http://www.cs.umd.edu/~gasarch/papers/poll.pdf

[yac]

To je pravý inženýrský důkaz :)

[kralyk z abclinuxu]

Důkaz davem?

[Bedňa]

To je rovnaká blbosť, ako aj celý "akože" problém Ako by sa "dôkaz davom" dal implementovať v programovacích jazykoch?

[default]

Ako by sa "dôkaz davom" dal implementovať v programovacích jazykoch?

To už je dávno naimplementovaný: zadáš vývoj do Indie.

[Bedňa]

India CAPTCHA OCR

[Piškot]

Lepší než tam chobotnice ne ?

[Anino]

Jéééj, dôkaz davom. To už tu dávno nebolo. Kedysi dávno sme organizovali podpisovú akciu za platnosť veľkej Fermatovej vety a vidíte, ako to dopadlo. :) (Inak aj o nej sa svojho času špekulovalo, že bude nezávislá na axiómach.)

[yac]

W T F ?! Nadpis i obsah zprávičky jsou lživé. Problém není ani vyřešen ani pravděpodobně vyřešen (stejně pravděpodobně jako u všech důkazů na toto téma za posledních 40 let). *znechuceně si odplivnul*

[Petr]

Problem vyresen nebyl

[jikos]

Wiki prubezne shrnujici aktualni poznatky o dukazu je na http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper

[yl]

chuck norris spravne riesenie davno pozna

[Marek Bernát]

Malý update, ak to niekoho zaujíma. Prof. Terence Tao tvrdí, že ten dôkaz v súčasnej podobe takmer určite nefunguje a je otázne, či sa z neho podarí zachraniť aspoň niečo (tj., či vôbec tá stratégia vedie k cieľu).

Ďalej podľa viacerých ľudí, ten článok v súčasnej podobe nemá šancu prejsť cez peer-review odborného časopisu kvôli množstvu problémov, ktoré má (a ktorých za posledné dni výrazne pribudlo).

Daolalikar publikoval ďalšiu verziu, ale žiadny z uvedených problémov v ňom nie je adresovaný, opravil len drobnosti. Napriek tomu ale ten článok Daolalikar chce publikovať v prakticky neznemenej podobe. Veľmi zaujímavý vývoj

[Marek Bernát]

Ospravedlňujem sa, posledný link je nesprávny. Správna adresa.

[EFi Yunah]

Ja teda fakt nechapem co preboha je na tom take tazke dokazovat... Raz ked mam NP-tazku ulohu (tento slovensky preklad je fakt nemozny), nemoze existovat riesenie polynomialnym algoritmom. Ked je uloha NP-tazka, da sa povedat, ze najdenie jedneho pripustneho riesenia, nijako nepomoze pri hladani lepsieho pripustneho riesenie. Akokolvek by sa mohlo zdat, ze ked uz mam pripustne riesenie, tak snad vidim, ze ci upravou premennych dostanem alebo nedostanem lepsie riesenie, stale zostava nevyriesena otazka, ze ako moc dobre riesenie je to startovacie... Suma sumarum, chcem tym povedat, ze problemom NP-tazkych uloh je, ze su NP-tazke, a teda nemoze existovat polynomialny algoritmus na ich riesenie... miesto zlozitych matematickych konstrukcii a rekonstrukcii treba zapojit bacovsku indukciu a mozog priemerneho delfina. NP != P a axioma... pomaly aby sme sa pokusali dokazat ze 1+1=2...

[Marek Bernát]

Opdporúčam ujasniť si pojmy NP, NP-ťažký a NP-úplný. NP-ťažká úloha sa dá riešiť polynomiálnym algoritmom, ak je zároveň v NP (tj. je NP-úplná) a ak platí, že P = NP (čo je práve nevyriešená otázka).