Fórum Root.cz

Ostatní => Odkladiště => Téma založeno: David Klusacek 10. 08. 2010, 15:47:50

Název: Velká záhada vyřešena: P != NP
Přispěvatel: 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


Název: Re: P!=NP
Přispěvatel: Havis 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/ (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  :)
Název: Re: P!=NP
Přispěvatel: Jarda Kočí 10. 08. 2010, 19:45:44
Dá se vysvětlit totálnímu laikovi, o co jde a co ten důkaz vlastně znamená?
Název: Re: P!=NP
Přispěvatel: BubakB 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 (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é.
Název: Re: P!=NP
Přispěvatel: JS 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.
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: Jarda Kočí 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?
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: BubakB 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.
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: Jarda Kočí 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?
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: jehovista 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.
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: -klusacek- 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.
Název: Re: Velká záhada vyřešena: P != NP
Přispěvatel: Vojtěch Havel 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).
Název: Uz mi taky doslo, ze jsem napsal blbost
Přispěvatel: -klusacek- 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.