Čtení: 55 minHodnotí se: zápočtový test, úloha 4 (12 b), ústní zkouška

4 Důkaz NP-úplnosti redukcí

Po přečtení umíš

napsat důkaz NP-úplnosti ve stejné šestibodové kostře
vybrat vhodný zdrojový problém
dokázat obě implikace a polynomiálnost
poznat tři nejčastější chyby v redukcích

Tahle úloha je nejtěžší v testu, ale kvůli zápočtu ji úplně vyřešit nemusíš. Body se dají získat i po částech. Kostra z této kapitoly ti dá část bodů, i když gadget nevymyslíš celý.

4.1 Ukázka: redukce na jeden řádek

Chceme ukázat, že Clique je NP-těžký a víme, že Independent Set je NP-těžký.

Vezmi graf $G$ a udělej doplněk $\overline{G}$ , hrany prohoď. Množina $S$ je nezávislá v $G$ právě tehdy, když je klikou v $\overline{G}$ . Algoritmus na kliku by tedy vyřešil i nezávislou množinu, takže klika je aspoň stejně těžká.

To je celá myšlenka redukce: známý těžký problém přeložíš na ten nový.

4.2 Co přesně dokazujeme

Definice 4.2 (Polynomiální redukce)

$A \le_p B$ znamená, že existuje funkce $f$ počitatelná v polynomiálním čase, pro kterou $x \in A \iff f(x) \in B$ .

Definice 4.3 (NP-těžký a NP-úplný)

$Q$ je NP-těžký, pokud $L \le_p Q$ pro všechna $L \in$ NP. NP-úplný je, pokud je navíc v NP.

Varování 4.4 (Směr redukce)

Vždy ze známého těžkého problému na svůj: $A \le_p Q$ . Opačný směr nedokazuje nic.

4.3 Kostra důkazu

Tahák (Kostra, kterou opiš do testu)

$Q \in$ NP. Co je certifikát a proč ho ověříš v polynomiálním čase.
Zdroj. „Redukujeme z problému $A$ .“
Konstrukce. Z instance $A$ popiš instanci $Q$ včetně všech čísel.
Polynomiálnost. Kolik vrcholů, hran a jak velká čísla.
⇒ Z řešení $A$ sestav řešení $Q$ . Většinou snadné.
⇐ Z řešení $Q$ přečti řešení $A$ . Tady je nejvíc práce: musíš ukázat, že řešení nemůže gadgety obejít.

Každý bod je samostatně obodovatelný.

4.4 Katalog zdrojových problémů

Mapa redukcí z přednášek a cvičení. Šipka vede od známého těžkého problému k novému.

Problém	Vstup	Otázka	Vyber ho, když tvůj problém
3-SAT	CNF, klauzule se 3 literály	je splnitelná?	má rozhodnutí ano/ne, gadgety
Clique	$G$ , $k$	existuje $k$ navzájem spojených vrcholů?	hledá hustý podgraf
Independent Set	$G$ , $k$	existuje $k$ vrcholů bez hran mezi nimi?	vybírá bez konfliktů
Vertex Cover	$G$ , $k$	pokryje $k$ vrcholů všechny hrany?	pokrývá nebo zasahuje
3-Coloring	$G$	lze obarvit 3 barvami?	přiřazuje do tříd
Hamiltonian Cycle	$G$	existuje kružnice přes všechny vrcholy?	řeší cestu nebo pořadí
X3C	$U$ , trojice	lze přesně pokrýt trojicemi?	přesně dělí prvky
Subset Sum	čísla, $T$	má podmnožina součet přesně $T$ ?	pracuje s čísly
Knapsack	váhy, ceny, $W$ , $C$	jde váha $\le W$ a cena $\ge C$ ?	má dvě kritéria proti sobě
3-Partition	$3q$ čísel, $B$	lze rozdělit na trojice se součtem $B$ ?	je silně těžký s čísly

Vertex Cover je často nejlepší volba. Je jednoduchý a blízko mnoha problémů. Proseminář 4 ukazuje, že dobrá volba zdroje promění složitou konstrukci v jednoduchou.

4.5 Řešené příklady ze cvičení

U každého příkladu si nejdřív zkus napsat kostru sám, klidně pět minut. Teprve pak si rozklikni nápovědu a řešení. Čtení hotového důkazu tě na test nepřipraví, tvoření ano.

Příklad 4.6 (Subgraph Isomorphism, cvičení 3.1)

Dokaž NP-úplnost: jsou dány grafy $G$ a $H$ . Obsahuje $G$ podgraf izomorfní s $H$ ?

Nápověda

Jaký speciální případ $H$ odpovídá známému problému?

Řešení

NP: certifikát je zobrazení $f$ , ověříme ho přes hrany.

Redukce z Clique: pro $(G, k)$ polož $H = K_k$ .

⇒ i ⇐: $G$ obsahuje podgraf izomorfní s $K_k$ právě tehdy, když má kliku velikosti $k$ .

Polynomiální, protože pro $k > n$ rovnou odpovíme NE, jinak má $K_k$ polynomiálně velikost.

Příklad 4.7 (Half-Clique, cvičení 3.2)

Dokaž NP-úplnost: je dán graf na $n$ vrcholech. Obsahuje kliku velikosti aspoň $n/2$ ?

Nápověda

Velikost kliky z Clique je obecná, tady je pevně daná. Přidej vrcholy, aby $k$ vyšlo přesně na polovinu.

Řešení

NP: certifikát je množina vrcholů.

Redukce z Clique. Máme $(G, k)$ a $n$ vrcholů.

Pokud $2k \ge n$ : přidej $2k - n$ izolovaných vrcholů. Nový graf má $2k$ vrcholů a hledáme kliku $k$ .
Pokud $2k < n$ : přidej $n - 2k$ vrcholů spojených se všemi. Nový graf má $2n - 2k$ vrcholů a hledáme kliku $n - k$ .

⇒ V prvním případě klika zůstává. Ve druhém ji doplníme všemi univerzálními vrcholy: $k + (n - 2k) = n - k$ .

⇐ Izolované vrcholy v klice velikosti aspoň 2 nejsou. Ve druhém případě odeber z kliky univerzální vrcholy, je jich $n - 2k$ , a zbude aspoň $k$ původních.

Příklad 4.8 (Set Cover, cvičení 3.3)

Dokaž NP-úplnost: je dáno $U$ , systém podmnožin a číslo $k$ . Lze vybrat nejvýše $k$ množin, jejichž sjednocení je $U$ ?

Nápověda

Hledej vrchol jako množinu. Co pak budou prvky $U$ ?

Řešení

NP: certifikát je vybraných $k$ množin.

Redukce z Vertex Cover: $U = E$ a pro každý vrchol $v$ množina $S_v$ hran u $v$ . Parametr $k$ stejný.

⇒ i ⇐: Vybrané vrcholy pokrývají všechny hrany právě tehdy, když příslušné množiny pokrývají $U$ .

Příklad 4.9 (Feedback Vertex Set, cvičení 3.4)

Dokaž NP-úplnost: je dán $G$ a $k$ . Existuje $F$ velikosti nejvýše $k$ , po jehož odebrání nezbude žádná kružnice?

Nápověda

Chceš z hrany udělat něco, co musí být zasaženo jako kružnice. Co je nejmenší kružnice?

Řešení

NP: certifikát je $F$ . Ověříme, že $G - F$ nemá kružnici.

Redukce z Vertex Cover: ke každé hraně $\{u, v\}$ přidej nový vrchol $w_{uv}$ spojený s $u$ i $v$ . Vznikne trojúhelník. Parametr $k$ stejný.

⇒ Po odebrání pokrytí $C$ nezbude žádná původní hrana. Zbylý graf tvoří jen hrany k vrcholům $w$ , které mají stupeň nejvýš 1, takže je to les.

⇐ Každý trojúhelník musí mít vrchol v $F$ . Pokud $F$ obsahuje $w_{uv}$ , nahraď ho vrcholem $u$ . Velikost neroste a trojúhelník zůstane zasažený. Teď každou hranu zasahuje původní vrchol, tedy jde o vrcholové pokrytí.

Krok s nahrazením je BÚNO argument: řešení upravíme do standardního tvaru.

Příklad 4.10 (Dominating Set, cvičení 3.5)

Dokaž NP-úplnost: je dán $G$ a $k$ . Existuje $D$ velikosti nejvýše $k$ takové, že každý vrchol mimo $D$ má souseda v $D$ ?

Nápověda

Podobný trik jako u FVS. Dominující množina řeší vrcholy, Vertex Cover hrany. Jak z hrany udělat vrchol?

Řešení

NP: certifikát je $D$ .

Redukce z Vertex Cover: odstraň izolované vrcholy, pokrytí nepotřebují. Ke každé hraně $\{u, v\}$ přidej nový vrchol $w_{uv}$ spojený s $u$ i $v$ . Parametr $k$ stejný.

⇒ Pokrytí $C$ dominuje všem: každý $w_{uv}$ má souseda v $C$ a každý původní vrchol mimo $C$ má hranu, jejíž druhý konec je v $C$ .

⇐ Pokud $w_{uv} \in D$ , nahraď ho za $u$ . Každý $w_{uv}$ musí být dominován, takže teď $u$ nebo $v$ leží v $D$ . To je vrcholové pokrytí velikosti nejvýše $k$ .

Příklad 4.11 (MAX-2-SAT, cvičení 4.1)

Dokaž NP-úplnost: je dána CNF s klauzulemi o nejvýše dvou literálech a $k$ . Lze splnit aspoň $k$ klauzulí?

Nápověda

Z 3-SAT. Každou klauzuli nahraď skupinou 2-klauzulí, která pozná, jestli je původní splněná. Hledej počet, který jde dosáhnout právě když je splněná.

Řešení

NP: certifikát je ohodnocení. Spočítáme splněné klauzule.

Redukce z 3-SAT. Pro klauzuli $(a \vee b \vee c)$ přidej novou proměnnou $d$ a deset klauzulí:

(a),\ (b),\ (c),\ (d),\ (\neg a \vee \neg b),\ (\neg a \vee \neg c),\ (\neg b \vee \neg c),\ (a \vee \neg d),\ (b \vee \neg d),\ (c \vee \neg d)

Pravdivých z $a, b, c$	Nejlepší $d$	Splněno
0	0	6
1	0	7
2	1	7
3	1	7

Polož $k = 7m$ .

⇒ V každé klauzuli zvol $d$ podle tabulky, dostaneš 7 z 10.

⇐ Kdyby některá klauzule nebyla splněná, dala by nejvýše 6 a ostatní nejvýše 7, celkem méně než $7m$ .

Příklad 4.12 (NAE-3-SAT na 3-Coloring, cvičení 4.2)

Navrhni jednodušší redukci než na přednášce: NAE-3-SAT se ptá na ohodnocení, kde v žádné klauzuli nemají všechny tři literály stejnou hodnotu.

Nápověda

Jeden vrchol $B$ jako neutrální barva a trojúhelník s $B$ pro každou proměnnou. Co musí splnit trojúhelník klauzule, aby zakázal tři stejné barvy?

Řešení

Konstrukce. Vrchol $B$ značí neutrální barvu. Pro každou proměnnou trojúhelník $B, x, \neg x$ . Literály tak mají dvě zbylé barvy, čteme je jako True a False.

Pro každou klauzuli trojúhelník $t_1, t_2, t_3$ a hrana z $t_i$ na $i$ -tý literál.

⇒ Literály nejsou všechny stejné. Vezmi dva s různou hodnotou, třeba $\ell_1$ True a $\ell_2$ False. Třetí vrchol dostane $t_3 = B$ , dále $t_1$ False a $t_2$ True. Žádná hrana není jednobarevná.

⇐ Máme 3-obarvení. Barvu $B$ nazveme neutrální, další dvě True a False. Trojúhelník klauzule používá všechny tři barvy. Kdyby všechny literály byly True, žádné $t_i$ by nesmělo být True a na tři vrcholy by zbyly dvě barvy, spor. Stejně pro False.

Je to jednodušší, protože NAE je symetrický vůči prohození True a False, stejně jako barvy.

4.6 Certifikáty (cvičení 2.3)

Problém	Certifikát	Je v NP?
Clique	$k$ vrcholů	ano
Hamiltonian Path	pořadí vrcholů	ano
Graph Isomorphism	bijekce vrcholů	ano
Non-2-colorability	lichá kružnice	ano, i v P
Singularita matice	nenulové $x$ s $Ax = 0$	ano, i v P
Regularita matice	inverzní matice	ano, i v P
DFA Non-universality	nepřijímané slovo délky nejvýš $	Q
NFA Non-universality	nepřijímané slovo?	pozor

U NFA může být nejkratší nepřijímané slovo exponenciálně dlouhé, takže slovo samo není polynomiální certifikát. Nad rámec materiálů: problém je PSPACE-úplný.

4.7 Tři nejčastější chyby

Varování 4.13 (1. Exponenciální konstrukce)

Čísla na vstupu jsou binárně. Pokud za číslo $a_i$ přidáš $a_i$ vrcholů, je výstup exponenciálně velký. Proto redukce Subset Sum na Exact Path v DAG neplatí. Bez vah je ten problém dokonce v P. Pomůže nechat čísla jako váhy hran.

Varování 4.14 (2. Zapomenuté kritérium)

Redukce Knapsack na Longest Path v DAG zapomněla na nosnost. Nejdelší cesta vezme všechny předměty a implikace ⇐ neplatí. Těžkost byla v souboji dvou kritérií.

Varování 4.15 (3. Slabá implikace ⇐)

Nestačí ukázat, že „hezké“ řešení dává odpověď. Musíš vysvětlit, proč i libovolné řešení lze přečíst. Pomáhá kapacita gadgetů nebo BÚNO výměna.

4.8 Kvíz

Kvíz

1. Chceš ukázat, že

Q

je NP-těžký. Co redukuješ?

Q \le_p

3-SAT 3-SAT

\le_p Q

Obojí

2. Co musí důkaz NP-úplnosti obsahovat? Může být správně více možností, ale také žádná.

Q \in

NP Polynomiálnost konstrukce Obě implikace Algoritmus pro

Q

3. Redukce za číslo

a_i

přidá

a_i

vrcholů. Co je špatně? Nic Velikost je exponenciální vůči bitům vstupu Vrcholů je málo

4. Je-li

S

nezávislá množina v

G

, co je

V \setminus S

? Klika Vrcholové pokrytí Dominující množina vždy

5. MAX-2-SAT z 3-SAT se 4 klauzulemi: jaké

k

zvolíš? Odpověď:

6. Co říká NP-úplnost Subset Sum o čase

O(n \cdot T)

? Je to polynomiální algoritmus Je pseudopolynomiální,

T

je exponenciální v bitech Takový algoritmus neexistuje

7. Co je BÚNO argument v implikaci ⇐?

Ukázat řešení

Libovolné řešení lokálními výměnami upravíme do standardního tvaru, aniž by přestalo být platné a větší. U FVS nahradíme nový vrchol

w_{uv}

u

. Ze standardního tvaru pak řešení přečteme.

4.9 Příklady na procvičení

Cvičení 4.16

Dokaž, že 4-Coloring je NP-úplný.

Řešení

NP: obarvení. Z 3-Coloring: přidej vrchol $u$ spojený se všemi. ⇒ Dej $u$ čtvrtou barvu. ⇐ $u$ má barvu, kterou nikdo jiný nemá, takže zbytek používá tři barvy.

Cvičení 4.17

Dokaž, že Hitting Set je NP-úplný.

Řešení

NP: množina $H$ . Z Vertex Cover: $U = V$ , množiny jsou hrany, parametr stejný. Pokrytí hran je přesně zasažení všech dvouprvkových množin.

4.10 Tahák

Tahák

$A \le_p Q$ : ze známého těžkého na svůj.
Kostra: NP → zdroj → konstrukce → polynomiálnost → ⇒ → ⇐.
Doplnění velikosti: izolované nebo univerzální vrcholy.
Trik s hranami: nový vrchol $w_{uv}$ pro každou hranu.
$V \setminus S$ : nezávislá množina ↔ vrcholové pokrytí. Doplněk grafu: nezávislá ↔ klika.
Čísla binárně. Nikdy $a_i$ vrcholů.
Dvě kritéria nesmí zmizet.
⇐ musí platit pro libovolné řešení, pomůže kapacita gadgetu nebo BÚNO.

Kapitolu mám prostudovanou