IB107 Vyčíslitelnost a složitost
polynomiální redukce a NP-úplné problémy
Jan Strejček
Fakulta informatiky Masarykova univerzita
polynomiální redukce
Definice 1.22 (polynomiální redukce)
Necht A c Z* a B c <t>* /sol/ jazyky. Řekneme, že A se polynomiálně redukuje na B, píšeme A <p B, právě když existuje totální funkce f: Z* -> <t>*, /cterá ye vyčíslitelná deterministickým Turingovým strojem pracujícím v polynomiálním čase a taková, že
w g A <=^> f(w) g B.
Funkci f nazveme polynomiální redukcí A na B.
Platí A <p B        /A <p B.
Platí A<p B a B <p C        /A <p C (tj. <p je tranzitivní).
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 2/24
polynomiální redukce a složitostní třídy
Věta 1.24
Necht A <p B. m B e P ^ Ae P m B e N P       A e N P
Důkaz: Nechí f je redukce A na B v polynomiálním čase a M b je TM rozhodující B. Stroj Ma rozhodující A na vstupu w
spočítá f(w) a
spustí M b na vstupu f(w) a vrátí stejný výsledek jako Mb-
Je-li A^e deterministický, pak je i Ma deterministický. Krok 1 lze provést v polynomiálním čase vzhledem k \ w\, krok 2 v polynomiálním čase vzhledem k \f(w)\, což je polynomiální i vzhledem k \ w\. Ma tedy pracuje v polynomiálním čase.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
polynomiální redukce a složitostní třídy
Definice 1.26 (těžká a úplná množina ve složitostní třídě)
NechtC je složitostní třída splňující N P c C. Jazyk L nazveme C-těžký, právě když pro každý jazyk U e C platí U <p L. Je-li navíc L e C, pak L nazýváme C-úplný nebo úplný ve třídě C.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
4/24
SATje NP-úplný
Věta 1.29 (Cookova-Levinova věta)
SAT = {(cp) | cp je splnitelná výroková formule} je NP-úplný.
Důkaz: SAT e NP jsme již dokázali.
Ukážeme, že SAT je NP-těžký, tj. A e NP       A <p SAT.
Nechí M je nedeterministický TM rozhodující A v čase p(n), kde p je polynom. Pro každé slovo w sestrojíme výrokovou formuli O, která je splnitelná, právě když stroj M má akceptující výpočet na w.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
5/24
SATje NP-úplný
Každý výpočet stroje M pracujícího v čase p(ri) na slově w délky n lze reprezentovat tabulkou:
Vytvoříme 0, aby platilo:
0 je splnitelné <=^> existuje tabulka reprezentující
akceptující výpočet na w
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 6/24
SAT je NP-úplný
0   = 0
cell
A 0
start
A 0
move
A 0
accept
0cen = "každé Xjj^s platí <=^> v tabulce na pozici i J je symbol s, kde s g C = Quru{#}"
Oceli =       A       [( VX'V>*) A ( A ^feA*/^))
1 </<p(n)+1 1 <y<p(n)+3
seC
s,teC
0ce„|go(p2(a7))
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
7/24
SATje NP-úplný
<D = <t>cell A <t>start A <t>
move A ^accept
0start = "na prvním řádku je iniciální konfigurace pro w =    ... wn"
^start   = A X1?2,Qo A Xi,3,> A
^1,4,^ A *i,5,w2 A ... A X-|?n+3?M/n A
*1,n+4,u A X-|,n+5,u A ... A Xi?p(n)+2,u A X1?p(n)+3?#
^startl e C?(p(n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
8/24
SATje NP-úplný
<t> = Ocel, A Ostart A 4>
move A ^accept
^move = "každé dva po sobě jdoucí řádky odpovídají kroku výpočtu" popíšeme pomocí "legálních oken" 2x3
příklady legálních oken pro S(q^, b) = {((fe, c, L), (g2ja, /?)}:
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
9/24
SAT je NP-úplný
* = <t>cell A <t>start A <t>
move A ^accept
^move = "každé okno 2 x 3 v tabulce je legální" (okna se překrývají)
0
move
A
1 </<p(n)+1 1 <y<p(n)+3
v
legální okno
i—i—i—i
x/,y-l,ai A xiJ,a2 A x/',y+l,a3 A x/+1,y—1,a4 A x/+1,y,a5 A x/+1,y+1,a6
ai	a2	a3
a4	a5	a6
<t>move| £ C(P2("))
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
10/24
SAT je NP-úplný
4> = <t>ceii A 0start A <t>
move A ^accept
^accept = "v tabulce je stav qacc"
4>
accept
V
l,J,Qacc
1 </<p(n)+1 1 <y<p(n)+3
^acceptl e 0{p2{n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
11/24
SATje NP-úplný
<D = <t>cell A <t>start A <t>
move A ^accept
<D| = 0{p2{n)) + 0{p{n)) + 0{p2{n)) + 0{p2{n)) = 0{p2{n))
Počet proměnných x/J?s je 0(p2(n)), tedy závisí na n = |w|. Proměnnou lze zakódovat do binární abecedy 0(\ogn) znaky. Tedy |(ct>)| = 0(p2(n) • log n), což znamená |(<t>}| = 0(p2(n) • n).
0} má polynomiální délku vzhledem k n = \ w\ a lze spočítat v polynomiálním čase. Tedy A <p SAT.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
12/24
konjunktivní normální forma (cnf) výrokových formulí
literal = je proměnná nebo její negace
klauzule = disjunkce literálů
formule v cnf = konjunkce klauzulí
formule v 3cnf = formule v cnf, kde každá klauzule má 3 literály
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 13/24
problém 3SAT
Definice (problém 3SAT)
Problém 3SAT je problém rozhodnout, zda je daná výroková formule v 3cnf splnitelná.
3 S AT = {((p) | (p je splnitelná formule v 3cnf]
3 S AT je N P-ú plný.
Důkaz: 3SAT e NP
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
14/24
3SATje NP-úplný
3SAT je NP-těžký, tj. A e NP       A <p 3 S AT: □ zkonstruujeme <t> jako v důkazu NP-těžkosti SATu
B O převedeme na ekvivalentní <t>' v cnf pomocí ekvivalence
(<p A ^) V p = ((p V p) A (tp V p)
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 15/24
3SAT\e NP-úplný
<t>' převedeme na <t>" v 3cnf pomocí vztahů
h v/2 /1 v l2 v /3 /i V/2V/3V/4
/! V ^ V ... V /,
<í>" je splnitelná <^> <t>' je splnitelná <^> <t> je splnitelná
|<D"| g 0(p2(a7)). Tedy /\ <p 3S/\7. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 16/24
redukce a C-těžkost ^^^^^^^^^^^^^
NechtC je složitostní třída splňující NP c C.
A je C-těžký a A<PB =^ B je C-těžký
Důkaz:
Věta 1.28
Je-li A NP-úplný, A <p B a B e NP, pak B je také NP-úplný.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
problém CLIQUE
Definice (/c-klika)
Neorientovaný graf G má k-kliku, pokud v něm existuje úplný podgraf s k vrcholy.
Definice (problém CLIQUE)
Problém CLIQUE je problém rozhodnout, zda daný graf G má k-kliku pro dané k.
CLIQUE = {(G,k)\Gje graf s k-klikou}
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
18/24
CLIQUE je NP-úplný
Věta
CLIQUE je NP-úplný. Důkaz: CLIQUE e NP:
CLIQUE je NP-těžký: 3SAT <p CLIQUE
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
19/24
CLIQUE je NP-úplný
Nechí cp = fa v fy v d) a (a2 v b2 v c2) a ... a (a* v bk v C/c). Zkonstruujeme graf G = (V, E), kde
■ \/ =    , b[, oi, a2, fc>2, c2,..., a/c, í^, ej a
■ E = {{v^i, v2} | ví, v2 nejsou ze stejné klauzule a
ví není negací v2 nebo naopak}.
<p = (x v y v z) a (->x v^yv -.z) a (x v ^y v -i/)
c^> je splnitelná <=^> existuje splňující přiřazení ^=^> Gmá/c-kliku Zároveň |G| = 0(|^|2) a tedy 3S/A7 <p CLIQUE. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 20/24
problém VERTEX-COVER
Definice (vrcholové pokrytí)
Necht G je neorientovaný graf. Podmnožina jeho vrcholů se nazývá vrcholové pokrytí grafu G, pokud obsahuje alespoň jeden vrchol každé hrany grafu G.
Definice (problém VERTEX-COVER)
Problém VERTEX-COVER je problém rozhodnout, zda daný graf G má vrcholové pokrytí obsahující právě daný počet vrcholů k.
VERTEX-COVER = {(G, k) \ G je graf s vrcholovým pokrytím
obsahujícím právě k vrcholů }
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
21/24
VERTEX-COVER je NP-úplný
Věta
VERTEX-COVER je NP-úplný. Důkaz: VERTEX-COVER e NP:
VERTEX-COVER je NP-těžký: 3SAT <p VERTEX-COVER
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
22/24
VERTEX-COVER je NP-úplný
Nechí (p = (ai v ^ v c\) a (a2 v b2 v c2) a... a (a/ v ď/ v q) používá množinu proměnných X. Zkonstruujeme graf G = (V, E), kde
■ V = {a-i, />i, c-i, a2, b2, c2,..., a/, Ď/, c/} u {x, ^x | x e X} a
■ E ={{a/, Ď/}, {a/? C/}, {ib/5 c/} | 1 < / < /} u {{x, -x} | x g X} u
u "hrany mezi literálem a shodným vrcholem x nebo -ix"
y? = (x v y v z) a (-.x v -iy v ->z) a (x v -.y v -y)
(p je splnitelná        G má vrcholové pokrytí s k = 21+ |X| vrcholy Zároveň |G| = 0(\<p\) a tedy 3SAT <p VERTEX-COVER. M
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy 23/24
další NP-úplné problémy
■ problém hamiltonovské cesty HAMPATH
■ problém obchodního cestujícího
(rozhodovací problém: existuje cesta do dané velikosti?)
■ problém okáchličkování (tiling problém)
Eternity II
■ 256 dílků (16x16)
■ 2.000.000 dolarů za řešení
■ během 3 a půl roku nenalezeno
Lemma
Pokud je nějaký NP-úplný problém v P, pak P = N P.
IB107 Vyčíslitelnost a složitost: polynomiální redukce a NP-úplné problémy
24/24