Velká záhada vyřešena: P != NP

Velká záhada vyřešena: P != NP
« kdy: 10. 08. 2010, 15:47:50 »
Vypada to ze velka zahada byla vyresena, jestli tam pan Vinay nema chybu, ovsem. Pokud ne tak blahopreji k vyhre 1M$.

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf


« Poslední změna: 10. 08. 2010, 19:46:24 od Petr Krčmář »


Havis

Re: P!=NP
« Odpověď #1 kdy: 10. 08. 2010, 18:10:38 »
nejake dalsie linky:
1.) http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
2.) http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p≠np/

Kazdopadne to vyzera velmi zaujimavo, aj ked podla mna by vacsia senzacia bola keby sa
P=NP  :)
« Poslední změna: 10. 08. 2010, 20:02:32 od Petr Krčmář »

Jarda Kočí

Re: P!=NP
« Odpověď #2 kdy: 10. 08. 2010, 19:45:44 »
Dá se vysvětlit totálnímu laikovi, o co jde a co ten důkaz vlastně znamená?

BubakB

Re: P!=NP
« Odpověď #3 kdy: 10. 08. 2010, 20:15:19 »
Dá se vysvětlit totálnímu laikovi, o co jde a co ten důkaz vlastně znamená?

Jedná se o problémy teoretické informatiky - velice jednoduše řečeno je to napsáno na wikipedii. Pokud hledáte trošku rozsáhlejší výklad, pak navštivte stránky doktora Sawy a pročtěte si jeho přednášky, případně skripta na stránce uvedené.

JS

Re: P!=NP
« Odpověď #4 kdy: 10. 08. 2010, 20:24:13 »
Dá se vysvětlit totálnímu laikovi, o co jde a co ten důkaz vlastně znamená?

Velmi zhruba receno to znamena, ze existuji problemy, u kterych je pomerne snadne overit spravnost reseni (pokud ho uz znate), ale je nepomerne tezsi to spravne reseni najit.


Jarda Kočí

Re: Velká záhada vyřešena: P != NP
« Odpověď #5 kdy: 10. 08. 2010, 20:54:16 »
Jako třeba takový ten obchodní cestující? Co musí projet všemi městy co nejefektivnější cestou? To je která varianta?

BubakB

Re: Velká záhada vyřešena: P != NP
« Odpověď #6 kdy: 10. 08. 2010, 21:01:15 »
Jako třeba takový ten obchodní cestující? Co musí projet všemi městy co nejefektivnější cestou? To je která varianta?

Jedná se o NP úplný problém.

Jarda Kočí

Re: Velká záhada vyřešena: P != NP
« Odpověď #7 kdy: 10. 08. 2010, 22:36:45 »
Aha, čili z toho plyne, že pokud má ten pán pravdu a P != NP, pak neexistuje způsob, jak NP převést na P a vymyslet pro něj tedy jednoduché řešení. Musí se na něj jít jedině hrubou silou. Je tak?

jehovista

Re: Velká záhada vyřešena: P != NP
« Odpověď #8 kdy: 10. 08. 2010, 23:33:10 »
Aha, čili z toho plyne, že pokud má ten pán pravdu a P != NP, pak neexistuje způsob, jak NP převést na P a vymyslet pro něj tedy jednoduché řešení. Musí se na něj jít jedině hrubou silou. Je tak?
Podle me to jen dokazuje, ze prevoditelnost NP ulohy na P neni zarucena.

-klusacek-

Re: Velká záhada vyřešena: P != NP
« Odpověď #9 kdy: 11. 08. 2010, 00:44:40 »
``Aha, čili z toho plyne, že pokud má ten pán pravdu a P != NP, pak neexistuje způsob, jak NP převést na P a vymyslet pro něj tedy jednoduché řešení. Musí se na něj jít jedině hrubou silou. Je tak?''

Ano, presne tak (pokud to chapu tak, ze jste chtel rict 'nelze prevest NP-uplnou ulohu na P ulohu' --- definice trid NP a P je totiz takova, ze pokud je neco v P je to automaticky taky v NP, cili nektere z NP uloh na P prevedete tim ze nedelate nic).

V pripade NP!=P se vsechny ty problemy jako jestli je formule vyrokove logiky splnitelna nejakym ohodnocenim, jestli existuje v grafu hamiltonovska kruznice (tedy posloupnost vrcholu tak ze kazdy vrchol grafu navstivime prave 1 a jdeme vzdy po sipkach mezi vrcholy tak jak jsou nakresleny v grafu --- to je ten obchodni cestujici), jestli je nejaky konkretni graf obarvitelny k barvami (barvi se vrcholy tak aby ty co jsou spojene hranou dostaly ruznou barvu) nebo jestli je v grafu podmnozina vrcholu velikosti k, ktere mezi sebou nemaji zadnou hranu (s ostatnimi vrcholy grafu hranu mit muzou) daji resit jen v exponencialnim case v zavislosti na velikosti konkretniho zadani.  Jeste kdybyste nahodou nevedel co se mysli tim grafem: predstavte si puntiky (konecne mnoho) pospojovane carami (mezi 2ma puntiky muze byt bud zadna nebo 1 cara, na krizeni nezalezi, jde jen o tu relaci). Puntikum se rika vrcholy, caram se rika hrany (terminologie pochazi z toho ze v pocatcich se ta teorie pouzivala na zakreslovani teles jako je treba krychle nebo 4sten v `rozvalcovanem' tvaru na papir --- slo o to ktery vrchol souvisi se kterymi hranami a jaky je vztah mezi poctem vrcholu, sten a hran --- tim se zabyval uz Euler).

Ty problemy co jsem uvedl jsou NP uplne, to znamena nejslozitejsi mozne ve tride NP, a daji se na sebe prevadet transformaci tech dat co dostavaji (kde ta transformace se da udelat v polynomialnim case). Takze kdyby nekdo o libovolnem z nich ukazal ze je v P tak by okamzite bylo NP=P.


Pokud P!=NP pak to znamena ze nejlepsi zpusob jak resit tyto problemy je zkusit vsechny moznosti. Tech je ale exponencialne. Dobra zprava je ze by se na tom asi dalo zalozit sifrovani o kterem bude dokazano ze ho neni mozne hrubou silou prolomit (pokud tedy nahodou neplati NP=BQP (coz je trida problemu resitelnych na kvantovych pocitacich) --- to se jeste nevi). Dosavadni sifry pokud vim jsou zalozeny na problemech o kterych se vi ze nejsou NP-uplne, pokud plati NP!=coNP.

Formalne je P definovano jako trida problemu na ktere je odpoved ano/ne a existuje algoritmus a polynom p tak ze ten algoritmus bezi v case mensim nez p(n) kde n je pocet bitu ktere v pameti zabralo zadani problemu (tedy napriklad toho grafu).  NP je trida problemu resitelnych v nedeterministicky polynomialnim case, tj. opet problem na ktery je odpoved ano/ne a zajima nas jestli existuje algoritmus, ktery kdyz dostane zadani + `spravnou radu' (coz je typicky treba to obarveni o kterem ma zjistit jestli existuje) tak z techto 2 udaju v polynomilanim case velikosti zadani spocte ano/ne (overi ze rada je spravne). Nedeterministicky se mu rika proto ze tu `radu' dostane jakoby z vnejsku (nekdy se rika z orakula (=vestirny)) a to tak ze pokud reseni existuje tak je rada spravna. Muzete si predstavovat ze orakulum hodne penez ze si muze dovolit provozovat 2^n pocitacu a kouzelnou moc ktera mu umozni rozsirit zadani problemu do vsech pocitacu v polynomialnim case radu generuje tak ze spusti vsech 2^n pocitacu tak ze na kazdem zkousi overit nasim algoritmem jeden z  moznych bitovych retezcu delky n jako `radu' pro danne zadani a ten co uspeje pak orakulum vyda. Kdyz neuspeje zadny, preda libovolny.

Jeste vam mozna prijde divny ze chci jen odpoved ano/ne, to je takove zjednoduseni aby se s tim teoretikum lip pracovalo --- urcite si dovedete predstavit ze je mozne z algoritmu ktery vraci i polynomialne velky vysledek udelat polynomialne mnoho rozhodovacich uloh typu `je x-ty bit vystupu roven 1?'. Kdyz spustim polynomialne mnoho vypoctu polynomialne dlouho trvajicich tak jsem porad v P. Takze pro ucely teorie se nemusim zatezovat s obecnymi vystupy (alepson v zacatku, v pokrocilejsich partiich se tez uvazuji).

Jeste jsou dalsi otevrene problemy, zajimavy je treba jestli co-NP=NP, kdyby ano tak by pak vsechny kratke matematicke vety mely i kratke (rozumej polynomialne dlouhe) dukazy. Trida co-NP je trida vsech problemu jejihz doplnek je v NP, kde doplnek znamena prehozeni odpovedi ano/ne. Napriklad: misto abych se ptal 'je v tento graf obarvitelny k-barvami?'(+) tak se budu ptat 'je pravda ze kazdy pokus obarvit graf k-barvami selze?'(*). Rozdil je v tom ze v NP tride se da rychle overit ze plati 'ANO' pokud vam nekdo poskytne dukaz (tedy tu radu co dava orakulum). Kdyz nekdo tvrdi ze graf je obarvitelny, a obarvi ho, tak ja snadno zkontroluju ze v nem neni hrana spojujici vrcholy stejne barvy. Naopak kdyz tvrdi ze graf neni obarvitelny, tak zadny takovy rychly zpusob znam neni.  To je prave pripad co-NP tridy, kde odpoved 'ANO' na otazku (*) znamena vlastne odpoved NE na otazku (+). Kdyby vsak co-NP=NP tak by takovy rychly zpusob existoval i zde.

S dukazy to souvisi (zhruba) takto. Logicka formule F(x) s volnymi promennymi x (berte to jako vektor vsech promennych) je slpnitelna prave kdyz existuje x takove ze F(x)=1. Negace tohoto je `pro vsecha x: F(x)=0'. Toto je coNP uloha. Kdyby NP=coNP tak bych ji mohl resit pomoci NP stroje a tim padem by existovala kratka
rada z orakula, ktera by se dala chapat jako dukaz formule !F (protoze formule se povazuje za platnou pokud =1 nezavisle na ohodnoceni volnych promennych).  Ta rada pochopitelne musi mit polynomialne omezenou delku, jinak by ji overovaci algoritmus nemohl precist v polynomilanim case.

Mozna to takhle nevyznelo, ale je to podle meho nazoru jeden z nejzajimavejsich otevrenych problemu informatiky, kdyz uz ted nemame NP=?=P.

PS: jeste jsem se dival na stranku toho objevitele a ma tam nejaky clanek o tom ze P je odlisne od coNP prunik  NP, a jelikoz rozklad na prvocisla je v coNP prunik NP tak by to znamenalo ze se uz dnesni sifrovani RSA neni
polynomialne napadnutelne.

Vojtěch Havel

Re: Velká záhada vyřešena: P != NP
« Odpověď #10 kdy: 14. 08. 2010, 14:06:02 »
PS: jeste jsem se dival na stranku toho objevitele a ma tam nejaky clanek o tom ze P je odlisne od coNP prunik  NP, a jelikoz rozklad na prvocisla je v coNP prunik NP tak by to znamenalo ze se uz dnesni sifrovani RSA neni
polynomialne napadnutelne.

Pozor, autor dokazoval P≠NP∩coNP pro infinite time TM.
Navíc dokazoval, že P je vlastní podmnožinou NP∩coNP, což u problémů z NP∩coNP neříká nic o jejich příslušnosti do P. Jen že v NP∩coNP existují problémy, které do P nepatří (pro infinite time TM).

-klusacek-

Uz mi taky doslo, ze jsem napsal blbost
« Odpověď #11 kdy: 15. 08. 2010, 16:16:10 »
tak se sem vracim abych to uvedl na pravou miru, avsak koukam ze jste byl rychlejsi. Diky za opravu.