``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.