IB107 Vyčíslitelnost a složitost
polynomiální redukce, SAT, 3 S AT, CLIQUE
Jan Strejček
Fakulta informatiky Masarykova univerzita
polynomiální redukce
Definice (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>*, která je 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, SAT, 3SAT, CLIQUE 2/21
polynomiální redukce a složitostní třídy
Věta
Necht A <p B. m B e P ^ Ae P m Be 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)
spustí M b na vstupu f(w) a vrátí stejný výsledek jako M b
Je-li Mb 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, SAT, 3SAT, CLIQUE
3/21
polynomiální redukce a složitostní třídy
Definice (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, SAT, 3SAT, CLIQUE
4/21
SAT je NP-úplný
Věta (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, SAT, 3SAT, CLIQUE
5/21
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, SAT, 3SAT, CLIQUE 6/21
SAT je NP-úplný
0   = 0
cell
A 0
start
A 0
move
A 0
accept
0cen = "každé XjjjS platí <=^> v tabulce na pozici /,/je symbol s, kde seC = Quru{#}"
*cell=       A       [( VX'V>*) A ( /\ ^(%A%))
1 </<p(n)+1 1 <y<p(n)+3
s,řeC
0ce„|go(p2(A7))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
7/21
SAT je NP-úplný
4> = <Dcen A 0start 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 Xi,n+5,u A ... A X1?p(n)+2?u A X1?p(n)+3?#
^startl e C?(p(n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
8/21
SAT je NP-úplný
<t> = Ocel, A Ostart A 4>
m o ve 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, SAT, 3SAT, CLIQUE
9/21
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
^moveI e 0(p2{n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
10/21
SAT je NP-úplný
<t> = <Dcen 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, SAT, 3SAT, CLIQUE
11/21
SAT je NP-úplný
4> = <t>ceii a 0start a <t>
move a 0accept
<D| = 0{p2{n)) + 0{p{n)) + 0{p2{n)) + 0{p2{n)) = 0{p2{n))
Počet proměnných x/J?s závisí 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) • logn), 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, SAT, 3SAT, CLIQUE
12/21
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, SAT, 3SAT, CLIQUE 13/21
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 SAT je N P-ú plný.
Důkaz: 3SAT e NP
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
14/21
3SATje NP-úplný
3SAT je NP-těžký, tj. A e NP       A <p 3SAT: d zkonstruujeme 0 jako v důkazu NP-těžkosti SATu
b 0 převedeme na ekvivalentní 0; v cnf pomocí ekvivalence
(<p A ip) V p = ((f v p) A (ip v p)
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE 15/21
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, SAT, 3SAT, CLIQUE 16/21
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:
Důsledek
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, SAT, 3SAT, CLIQUE
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, SAT, 3SAT, CLIQUE
18/21
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, SAT, 3SAT, CLIQUE
19/21
CLIQUEjeNP-úplný
Nechí cp = (ai v ď1 v ci) a (a2 v ď2 v c2) a ... a (a* vď^v c^). Zkonstruujeme graf G = (V, E), kde
■ V = {ai, 61, oi, a2, ffc, c2,..., a*, f^, C/<} a
■ E = {{ v-i, v2} | v-i, v2 nejsou ze stejné klauzule a
vi není negací v2 nebo naopak}
^ = (x v y v z) a (-.x v-n/v -.z) a(xv^yv -.y)
c^> je splnitelná       existuje splňující přiřazení <=4> Gmá/c-kliku Zároveň \G\ = 0(M2) a tedy 3SAT <p CLIQUE. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE 20/21
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, SAT, 3SAT, CLIQUE
21/21