Fórum Root.cz
Ostatní => Odkladiště => Téma založeno: David Klusacek 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
-
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/ (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 :)
-
Dá se vysvětlit totálnímu laikovi, o co jde a co ten důkaz vlastně znamená?
-
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 (http://cs.wikipedia.org/wiki/Problém_P_versus_NP) napsáno na wikipedii. Pokud hledáte trošku rozsáhlejší výklad, pak navštivte stránky doktora Sawy (http://www.cs.vsb.cz/sawa/uti/) a pročtěte si jeho přednášky, případně skripta na stránce uvedené.
-
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.
-
Jako třeba takový ten obchodní cestující? Co musí projet všemi městy co nejefektivnější cestou? To je která varianta?
-
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.
-
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?
-
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.
-
``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.
-
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).
-
tak se sem vracim abych to uvedl na pravou miru, avsak koukam ze jste byl rychlejsi. Diky za opravu.