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* -> 0*, 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.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
2/17
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.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE 3/17
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 4/17
polynomiální redukce a složitostní třídy
Věta	
Nechí A <p B.	
m Be P ==>■	AeP
■ B e NP —	> AeNP
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
5/17
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
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
7/17
SAT je NP-úplný
SAT = {((f) | cp je splnitelná výroková formule} je NP-úplný.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
8/17
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.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE
9/17
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
10/17
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 11/17
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
12/17
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
13/17
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
14/17
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
15/17
SAT je NP-úplný
4> = <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
16/17
SAT je NP-úplný
4> = 4>cell A <t>start 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 = 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
17/17