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/20
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/20
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/20
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/20
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/20
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/20
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/20
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/20
SAT je NP-úplný
4> = 4>cell A <t>start 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/20
SATje NP-úplný
0 = <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 |(<t>}| = 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/20
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/20
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/20
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/20
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/20
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/20
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/20
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/20