Kapitola 1
Státnice - NP-úplnost

1.1 Třídy P a NP, polynomiální převody, NP-úplnost

Definice (Úloha)

- Úloha je situace, kdy pro daný vstup (instanci úlohy) chceme získat výstup se zadanými vlastnostmi.

- Optimalizační úloha je úloha, kde cílem je získat optimální (zpravidla největší nebo nejmenší) výstup s danými vlastnostmi.

- Rozhodovací problém je úloha, jejímž výstupem je ANO/NE.

Definice (Kódování vstupů)

Každá instance problému je kódována jako posloupnost 0 a 1, tj. instance je slovo v abecedě . Kódy všech instancí problému tvoří jazyk nad abecedou , který se dělí na

- – kódy instancí s odpovědí ANO (jazyk kladných instancí)

- – kódy instancí s odpovědí NE (jazyk záporných instancí)

Rozhodovací problém pak je rozhodnutí, zda nebo (kde je kód nějaké instance ), když předpokládáme, že rozhodnutí lze udělat v polynomiálním čase vzhledem k .

Definice (Deterministický Turingův stroj)

DTS obsahuje řídící jednotku, čtecí a zápisovou hlavu a (nekonečnou) pásku. Program sestává z:

1. Konečné množiny páskových symbolů, vstupních symbolů a prázdného symbolu

2. Konečné množiny stavů řídící jednotky, která obsahuje startovní stav a 2 terminální stavy ,

3. Přechodové funkce

DTS s programem přijímá , právě když pro vstup se zastaví ve stavu . Jazyk rozpoznávaný programem M je .

DTS s programem řeší problém , právě když výpočet skončí pro každý vstup a platí .

Nechť je program pro DTS, který skončí pro . Časová složitost programu je dána funkcí výpočet na DTS s programem a vstupem skončí po krocích stroje. Pokud existuje polynom tak, že , pak je polynomiální DTS program.

Definice (Třída P)

Problém je ve třídě P, právě když existuje polynomiální DTS program , který řeší .

Definice (Nedeterministický Turingův stroj)

Stejný jako DTS, ale místo přechodové funkce je zde zobrazení , které každé dvojici z přiřazuje množinu možných pokračování výpočtu, tj. trojic z .

NTS s programem přijímá , právě když existuje přijímající výpočet programu (tj. běh , kdy na vstupu je a končí se ve stavu ). Jazyk rozpoznávaný programem M je .

Čas, ve kterém přijímá definujeme jako počet kroků nejkratšího přijímajícího výpočtu nad daty .

Časová složitost programu je dána funkcí:

Pokud existuje polynom takový, že , pak je polynomiální NTS program.

Definice (Třída NP)

Problém je ve třídě NP, právě když existuje polynomiální NTS program , který řeší . Na rozdíl od deterministického případu netrváme na tom, že výpočet musí skončit i pro nepřijímané instance.

Poznámka (Jiný model NTS)

Přidáme další pásku (orákulum) a stroj pracuje ve 2 fázích:

1. Nedeterministicky hádá – zapíše problém do orákula.

2. Deterministicky ověřuje obsah orákula – práce DTS na původním vstupu plus obsahu orákula.

Je to ekvivalentní s původním – omezíme-li počet možných přechodů NTS na 2 (tím ho jen zpomalíme) a zapisujeme-li do orákula větve pokračování výpočtu (pak stačí na jednu jeden bit), převedeme veškerý nedeterminismus čistě na naplnění orákula.

Definice (Třída co-NP)

Problém je ve třídě co-NP, právě když existuje polynomiální NTS program takový, že . O poměru množin co-NP a NP nevíme nic, jen to, že podmnožinou jejich průniku je P.

Převody a NP-úplnost

Definice (Polynomiálně vyčíslitelná funkce)

Funkce je polynomiálně vyčíslitelná, právě když existuje polynom a algoritmus takový, že pro každý vstup dává výstup v čase nejvýše .

Definice (Polynomiální převoditelnost)

Jazyk je polynomiálně převoditelný na jazyk (píšeme ), právě když existuje polynomiálně vyčíslitelná funkce taková, že

Definice (NP-těžký, NP-úplný problém)

- Problém je NP-těžký, právě když .

- Problém je NP-úplný, právě když je NP-těžký a .

Je-li nějaký NP-těžký problém převoditelný na jiný, pak ten musí být také NP-těžký.

1.2 Příklady NP-úplných problémů a převody mezi nimi

Cook-Levinova věta

Existuje NP-úplný problém.

Důkaz pro KACHL

Máme množinu barev , čtvercová síť s obvodem obarveným barvami z a množinu typů kachlíků, kde je každý typ definován svou horní, dolní, levou a pravou barvou.

Lze síť vykachlíkovat pomocí kachlíků z množiny (stejný typ lze použít libovolněkrát, kachlíky ale nelze otáčet) tak, aby:

- barvy kachlíků přilehlé k obvodu sítě souhlasily s barvami předepsanými tomto na obvodu sítě a

- každá dvojice barev na dotyku dvou kachlíků byla rovněž shodná?

NP-úplné problémy

Splnitelnost (SAT)

CNF (booleovská formule v konjunktivní normální formě, tj. konjunkce disjunkcí) na proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli ?

Důkaz transformací KACHL ∝ SAT: pomocí proměnných , kde , pokud na pozici se nachází kachlík typu . Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny.

3-SAT

Kubická CNF (vždy jen 3 proměnné v jedné disjunkci) na Booleovských proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli ?

Transformace SAT ∝ 3-SAT: stačí každou klauzuli (disjunkci) rozložit s pomocí nových volných proměnných na několik kubických klauzulí: odpovídá

3-COLOR

Tříobarvení grafu: Mějme neorientovaný graf . Lze obarvit vrcholy ve třemi barvami tak, aby žádná hrana v neměla na obou koncích vrcholy stejné barvy?

Obrázek 1.1: Transformace 3-SAT ∝ 3-COLOR

Transformace 3-SAT ∝ 3-COLOR: Vytvořím pro všechny proměnné a jejich negace vrcholy grafu a spojím se třemi body (z nichž každý musí být jinak barevný podle obrázku), aby proměnné musely mít barvu T nebo F. Proměnné a negace jsou taky spojené, aby bylo jednoznačně dána hodnota každé z nich. Pro každou klauzuli 3-SAT přidám grafík podle obrázku (napojím na proměnné, které představují literály klauzule a na druhé straně na barvu F), aby proměnné v něm nešly obarvit FFF.

KLIKA

Mějme neorientovaný graf a přirozené číslo . Existuje , , indukující úplný podgraf grafu ?

Transformace SAT ∝ KLIKA – pro každý literál vytvořím bod grafu, spojím všechny body odpovídající literálům různých klauzulí, pokud se nejedná o komplementární proměnné, tj. mezi a nevede hrana.

Nezávislá Množina (NM)

Mějme neorientovaný graf a přirozené číslo . Existuje , , taková, že uvnitř nejsou žádné hrany?

Transformace KLIKA ∝ NM: stačí prohodit hrany a ne-hrany.

Vrcholové pokrytí (VP)

Máme neorientovaný graf a přirozené číslo . Existuje , taková, že každá hrana má ve alespoň jeden vrchol?

Transformace NM ∝ VP: NM je doplněk VP (vedou-li hrany do VP, už nemůžou vést mezi ostatními vrcholy).

Hamiltonovská Kružnice (HK)

Máme neorientovaný graf . Obsahuje G hamiltonovskou kružnici, tj. jednoduchou kružnici, která prochází každým vrcholem právě jednou?

Obrázek 1.2: Transformace VP ∝ HK

Transformace VP ∝ HK: Na pomyslných linkách naskládám pro každou hranu původního grafu dvanáctici vrcholů spojených podle obrázku (widget). Krajní body všech linek spojím s vrcholy odpovídající původnímu VP . Protože widgety lze projít jen částečně (2x po linkách) nebo úplně (jednou všechny), bude HK vést částečným průchodem přes widgety, pokud oba vrcholy příslušné jejich hraně původního grafu patří do VP a úplným jinak.

Obchodní cestující (TSP)

Máme úplný neorientovaný graf , váhy a číslo . Existuje v hamiltonovská kružnice s celkovou váhou nejvýše ? Někdy se počítá nad neúplným grafem a požaduje se hamiltonovský sled, tj. je možné opakovat vrcholy; to se ale na tuto definici snadno převede.

Transformace HK ∝ TSP: stačí nastavit váhy tak, že , pokud byla v původním grafu a jinak. Je-li chtěná váha rovna počtu hran původního grafu, řešení dává HK v něm.

Součet podmnožiny (SP)

Jsou daná čísla . Existuje množina indexů taková, že ?

Transformace VP ∝ SP: vyrobím incidenční matici grafu (řádky odp. vrcholům, sloupce hranám), kde budou jedničky na místech, kde daná hrana vede z daného vrcholu. Přidám k ní matici, jejíž řádky i sloupce odpovídají hranám a jedničky jsou pouze na diagonále (tj. každá hrana má jedničku ve “svém” řádku a sloupci). “Nalevo” od incidenční matice přidám sloupec plný jedniček. Řádky matice interpretuju jako čísla ve čtyřkové soustavě (v každém sloupci jsou tři jedničky, proto nedojde nikdy k přesunu řádů) a hledám součet podmnožiny jako číslo, které má na začátku velikost VP (sečte se ze sloupce jedniček) a následují samé dvojky (pro každou hranu).

1.3 Silná NP-úplnost, pseudopolynomiální algoritmy

Příklad

SP není exponenciální, ale polynomiální v počtu a velikosti čísel. Algoritmus (dynamické programování):

1. Nechť a je bitové pole délky (kde na pozici bude indikovat možnost vytvoření podmnožiny se součtem ).

2. Všechny prvky pole nastav na .

3. Pro od do opakuj (hl. cyklus):

2. Pro od do zkoušej: když a , nastav

4. Je-li , podmnožina se součtem rovným existuje.

Po -tém průchodu hlavním cyklem obsahuje jedničky právě u všech součtů neprázdných podmnožin . Důkaz – indukcí. Celk. složitost je , což je exponenciální vzhledem k binárně kódovanému vstupu, ale polynomiální, máme-li na vstupu čísla konstantní délky.

Definice (Pseudopolynomiální algoritmus)

Nechť je dán rozhodovací problém a jeho instance . Pak definujeme:

- kód(I) – délka zápisu (počet bitů) instance v binárním kódování (či jiném na něj polynomiálně převoditelném)

- max(I) – velikost největšího čísla, vyskytujícího se v (NE délka jeho binárního zápisu!)

Algoritmus se nazývá pseudopolynomiální, pokud je jeho časová složitost omezena polynomem v proměnných kód a . Každý polynomiální algoritmus je tím pádem pseudopolynomiální.

Poznámka (O číselných problémech)

Pokud pro nějaký problém platí, že kód pro nějaký polynom , pak všechny pseudopolynomiální algoritmy, řešící tento problém, jsou zároveň polynomiální.

Všechny problémy, kde tato rovnice neplatí(tj. neexistuje , že by platila), nazýváme číselné problémy.

Věta (O pseudopolynomialitě a NP)

Nechť je NP-úplný problém a není číselný. Pak pokud PNP, nemůže být řešen pseudopolynomiálním algoritmem.

Poznámka

Ani ne každý číselný problém je řešitelný pseudopolynomiálním algoritmem.

Věta (O pseudopolynomialitě a podproblémech)

Nechť je rozhodovací problém a polynom. Potom označme množinu instancí (podproblém) problému , pro které platí kód. Potom máme-li pseudopolynomiální algoritmus , který řeší problém , určitě existuje polynomiální algoritmus, řešící . Toto platí pro libovolné p.

Důkaz

Algoritmus , řešící v polynomiálním čase, otestuje na přítomnost v (spočítá kód a ) a pokud , chová se stejně jako , takže běží v čase kódkódkódkód.

Definice (Silně NP-úplný problém)

Rozhodovací problém je silně NP-úplný, pokud NP a existuje polynom takový, že podproblém je NP-úplný.

Věta (O silné NP-úplnosti)

Nechť problém je silně NP-úplný. Potom, pokud PNP, neexistuje pseudopolynomiální algoritmus, který by řešil .

Důkaz

Plyne z předchozí věty.

Příklady

TSP je silně NP-úplný. Je to číselný problém, protože váhy hran nejsou omezené. Když váhy na hranách omezím, dostanu NP-úplný podproblém (jde na něj převést HK).

3-ROZDĚLENÍ je silně NP-úplné. Problém: máme takové, že a navíc . Existuje disjunktní rozdělení množiny takové, že ?

Důkaz se provádí převodem z 3DM (třídimenzionální párování na tripartitních grafech), všechna čísla konstruovaná pro převod jsou polynomiálně velká vzhledem ke (v převodu byla exponenciálně velká).