NP-´ uplnost
TGH12 - Probl´em za milion dolar˚ u Jan Bˇrezina Technical University of Liberec
7. kvˇetna 2013
NP-´ uplnost
Sloˇzitost probl´emu
Co je to probl´em?
NP-´ uplnost
Sloˇzitost probl´emu
Co je to probl´em? K dan´ym vstupn´ım dat˚ um (velk´emu bin´arn´ımu ˇc´ıslu) X, naj´ıt v´ystupn´ı data Y splˇ nuj´ıc´ı nˇejakou vlastnost: F (X, Y ) = 1
. . . F je “logick´y obvod”
NP-´ uplnost
Sloˇzitost probl´emu
Co je to probl´em? K dan´ym vstupn´ım dat˚ um (velk´emu bin´arn´ımu ˇc´ıslu) X, naj´ıt v´ystupn´ı data Y splˇ nuj´ıc´ı nˇejakou vlastnost: F (X, Y ) = 1 Co je sloˇzitost probl´emu?
. . . F je “logick´y obvod”
NP-´ uplnost
Sloˇzitost probl´emu
Co je to probl´em? K dan´ym vstupn´ım dat˚ um (velk´emu bin´arn´ımu ˇc´ıslu) X, naj´ıt v´ystupn´ı data Y splˇ nuj´ıc´ı nˇejakou vlastnost: F (X, Y ) = 1
. . . F je “logick´y obvod”
Co je sloˇzitost probl´emu? Nejmenˇs´ı sloˇzitost algoritmu, kter´y pro X najde Y , aby platilo F (X, Y ) = 1.
NP-´ uplnost
pˇr´ıklady
NP-´ uplnost
Lehk´e a tˇeˇzk´e probl´emy Zvl´adnuteln´e velikosti probl´emu: n= n2 n3 n6 n1 0 2n
1 corehour 106 15000 123 18 41
106 corehours 109 106 103 71 61
109 coreweeks (exascale) 1011 108 104 239 79
Pro seriov´y poˇc´ıtaˇc s frekvenc´ı 1GHz (109 operac´ı za sekundu) Z´avˇer: prakticky zvl´adnuteln´e jsou probl´emy se sloˇzitost´ı max. O(n6 ). teoreticky jsou zvl´adnuteln´e problm´emy s polynomi´aln´ı sloˇzitost´ı O(nk )
NP-´ uplnost
Probl´emy nemoˇzn´e - halting probl´em
Pro dan´y program (reprezentovan´y ˇc´ıslem X) rozhodni, zda pro data A v´ypoˇcet X(A) skonˇc´ı v koneˇcn´em ˇcase. Existuje program Y (i, j), kter´y pro kaˇzd´e X a A v koneˇcn´em ˇcase zjist´ı zda X(A) skonˇc´ı? Tedy: Y (X, A) = 1, pokud X(A) skonˇc´ı Y (X, A) = 0,
pokud X(A) neskonˇc´ı v koneˇcn´em ˇcase
NP-´ uplnost
Halting probl´em
1. Necht’ Z(i, j) je libovoln´y program, kter´y skonˇc´ı v koneˇcn´em ˇcase pro vˇsechna i, j. 2. Program W (i): W (i) =
0 pokud Z(i, i) = 0 undef ined, loop pokud Z(i, i) = 1
3. Y (W, W ) se nem˚ uˇze rovnat Z(W, W ) pro ˇz´adn´e Z: • bud’ W (W ) = Z(W, W ) = 0, tedy W je koneˇ cn´y a Y (W, W ) = 1 • nebo W (W ) neskonˇ c´ı, Z(W, W ) = 1 a Y (W, W ) = 0
NP-´ uplnost
Putov´an´ı po hran´ach
Probl´em: Pro dan´y neorientovan´y graf s n vrcholy najdi kruˇznici, kter´a projde haˇzdou hranu pr´avˇe jednou (Eulerovsk´a kruˇznice). Zn´ame algoritmus (stupnˇe vrchol˚ u a DFS), kter´y to zvl´adne v ˇcase O(V + E) = O(n2 ). Probl´em je ve tˇr´ıdˇe P probl´em˚ u ˇreˇsiteln´ych v polynomi´aln´ım ˇcase. Existuje program X, kter´y pro vstup (graf) A najde v´ystup (kruˇznici) B = X(A), tak aby platilo F (A, X(A)) = 1, pokud kruˇznice existuje. Program (funkce) F (i, j) verifikuje, ˇze j je Eulerovsk´a kruˇznice na grafu i. Sloˇzitost tak´e O(n2 ).
NP-´ uplnost
Putov´an´ı po vrcholech Hamiltonova kruˇznice - je kruˇznice na grafu G, kter´a proch´az´ı kaˇzd´y vrchol pr´avˇe jednou. Verifikaˇcn´ı probl´em: Pro graf i a posloupnost vrchol˚ u j zjisti zda je to Hamiltonova kruˇznice, tj. vypoˇcti F (i, j): 1 pokud j je Hamiltonovsk´a kruˇznice na grafu i F (i, j) = 0 j nen´ı Hamiltonovsk´a Sloˇzitost O(n). Zjist´ıme zda se vrcholy neopakuj´ı a existuj´ı pˇr´ısluˇsn´e hrany. Tˇr´ıda N P nedeterministicky polynomi´aln´ı probl´em, verifikovateln´y v polynomi´aln´ım ˇcase. Pˇr´ım´y probl´em: Najdi Hamiltonovu kruˇznici. !! Nezn´ame polynomi´aln´ı algoritmus i pˇres velkou podobnoust s pˇredchoz´ı snadnou u ´lohou.
NP-´ uplnost
Tˇr´ıdy probl´em˚ u
P :u ´lohy ˇreˇsiteln´e v polynomi´aln´ım ˇcase O(nk ) NP : u ´lohy jejichˇz ˇreˇsen´ı je verifikovateln´e v polynomi´aln´ım ˇcase. N P -hard : u ´lohy nejm´ıˇ n tak tˇeˇzk´e jako N P , tj. vˇsechny N P jsou na nˇe redukovateln´e N P -´ upln´e : nejtˇeˇzˇs´ı z N P probl´em˚ u, tj. N P ∩ N P -hard Za milion dolor˚ u: Je N P = P nebo N P 6= P ?
NP-´ uplnost
• optimalizaˇ cn´ı probl´em - pˇr. najdi optim´aln´ı obarven´ı grafu, probl´em
obchodn´ıho cestuj´ıc´ıho, typicky N P -hard • rozhodovac´ı probl´ em - najdi k-obarven´ı grafu (rozhodni, zda takov´e
existuje), najdi Hamiltonovu kruˇznici, typicky N P -´ upln´y • Rozhodovac´ı probl´ em A je redukovateln´y na B pokud:
Existuje polynomi´alnˇe sloˇzit´a transformace vstupu a na vstup b tak, ˇze A(a) pr´avˇe kdyˇz B(b) tj. pokud B je v P pak A je taky v P tj. pokud A nen´ı v P ani B nen´ı v P tj. probl´em B je nejm´enˇe tak teˇzk´y jako probl´em A • Chceme naj´ıt nˇ ejak´y N P -´ upln´y probl´em. • Mnoho probl´ em˚ u je ve tˇr´ıdˇe N P -´ upln´ych, jsou na sebe navz´ajem
redukovateln´e - jsou ekvivalentn´ı. Hamiltonova kruˇznice, nejdelˇs´ı cesta v grafu, optim´aln´ı skl´ad´an´ı do batohu, ...
NP-´ uplnost
NP-´upln´y probl´em I
Rozhodovac´ı probl´em je N P -´ upln´y pokud • je v N P , tj. ˇreˇsen´ı je verifikovateln´ e v polynomi´aln´ım ˇcase • kaˇ zd´y probl´em v N P je na nˇej redukovateln´y (je nejtˇeˇzˇs´ı v N P )
Uvaˇzujme mnoˇzinu M program˚ u X ze tˇr´ıdy P , kter´e pro kaˇzd´y vstup x d´avaj´ı v´ystup ano nebo ne. Probl´ em B: Pro dan´y program X ∈ M zjisti, zda existuje vstup x d´avaj´ıc´ı v´ystup ano. Prakticky: Pro logick´y obvod X najdi vstup x, tak aby na v´ystupu byla jedniˇcka.
NP-´ uplnost
NP-´upln´y probl´em II • Probl´ em je z N P . Pro dan´y vstup x urˇc´ıme v polynomi´aln´ım ˇcase
zda vyhovuje. B 0 (X, x) = X(x) • Probl´ em je teˇzˇs´ı neˇz vˇsechny probl´emy A ∈ N P .
Pro A najdeme zobrazen´ı f vstup˚ u a na vstupy X probl´emu B, tak aby A(a) ⇔ B(X). 1. A ∈ N P , takˇze existuje poly verifikaˇcn´ı program A0 (a, a0 ) tak, ˇze A(a) = 1 pr´ avˇe kdyˇz ∃a0 : A0 (a, a0 ) = 1 2. poloˇzme f (a) = X = Fa , kde Fa (a0 ) = A0 (a, a0 ) 3. program X je program A0 s pˇredprogramovan´ym vstupem a, takˇze je polynomi´ aln´ı 4. A(a) ⇔ ∃a0 : Fa (a0 ) = 1 ⇔ ∃x : X(x) = 1 ⇔ B(X)
Z´avˇer: Na probl´em B je redukovateln´y kaˇzd´y N P probl´em, tj. problem B (tzv. probl´em nasytitelnosti Boolovsk´ych forem), je NP-´ upln´y
NP-´ uplnost
zero-knowledge proof D˚ ukaz, ˇze nˇejak´e (matematick´e) tvrzen´ı je pravdiv´e bez odhalen´ı vlastn´ıho d˚ ukazu.
V kaˇzd´em kole klesne pravˇepodobnost, ˇze Peggy nem´a kl´ıˇc na polovinu.
NP-´ uplnost
ZKP pomoc´ı graf˚ u Peggy zn´a Hamiltonovu kruˇznici v rozs´ahl´em grafu G a chce tuto znalost dok´azat Viktorovi, aniˇz by j´ı prozradila. Oba provedou nˇekolik iterac´ı postupu: 1. Peggy sestroj´ı graf H isomorfn´ı s G. 2. Peggy zap´ıˇse tajnˇe graf H, kaˇzdou hranu zvl´aˇst’. (Zaˇsifruje sv´ym veˇrejn´ym kl´ıˇcem.) 3. Viktor n´ahodnˇe urˇc´ı zda chce odhalit, isomorfismus, nebo kruˇznici na H 4. V prvn´ım pˇr´ıpadˇe Peggy odhal´ı cel´y graf H a isomorfn´ı zobrazen´ı na G. 5. V druh´em pˇr´ıpadˇe Peggy odhal´ı jen hrany kruˇznice na H. V kaˇzd´em kole klesne pravˇepodobnost, ˇze Peggy kruˇznici nezn´a na polovinu.
NP-´ uplnost
Probl´em obchodn´ıho cestuj´ıc´ıho
´ Uloha: Jak si m´a napl´anovat cestu po N mˇestech, aby str´avil na cest´ach nejm´enˇe ˇcasu. Grafovˇe: Najdi nejkratˇs´ı Hamiltonovsk´a kruˇznice v (´ upln´em) ohodnocen´em grafu. (NP-hard) Praktick´y pˇredpoklad. Plat´ı troj´ uheln´ıkov´a nerovnost: d(i, j) ≤ d(i, k) + d(k, j) . . . st´ale NP-´ upln´y probl´em. ⇒ Aproximace.
NP-´ uplnost
Aproximace pomoc´ı MST
1. Zvol poˇc´ateˇcn´ı vrchol v. Najdi z nˇej MST pomoc´ı Primova algoritmu. 2. Z koˇrene v proch´azej kostru pomoc´ı DF S algoritmu. Urˇci poˇrad´ı uzl˚ u podle previzit. Tato aproximace d´av´a kruˇznici po vˇsech uzlech, kter´a je max. dvakr´at delˇs´ı neˇz optim´aln´ı ˇreˇsen´ı.
