Státnice - NP-úplnost

Z ωικι.matfyz.cz
Verze z 24. 10. 2012, 15:05, kterou vytvořil 77.48.63.197 (diskuse) (Revert spam.)

Přejít na: navigace, hledání

Tohle je poněkud obšírnější výcuc ke státnicovým okruhům ze složitosti pro obory Matematická lingvistika a Softwarové systémy, pocházející ze zápisků z předmětu Složitost I -- Tuetschek 22:44, 16 Aug 2010 (CEST)

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

Stre1nky Prahy 9 jsou sice nove9, ale je zde několik starfdch čle1nků bez data napse1ned. Takove1 informace pak vypade1 jako čerstve1, ale přitom je stare1 i nějakfd rok.Důkazem je tomu čle1nek „Koncepce rsutneorkkce dětskfdch hřišť na fazemed městske9 če1sti Praha 9“, kde se hned v favodu pedše „V minule9m roce nechala městske1 če1st vypracovat“.Takže škoda, že se neuve1ded datum, jako tomu je třeba na těchto stre1nke1ch.

No compalitns on this end, simply a good piece.

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 $ \Gamma\,\! $ páskových symbolů, $ \Sigma \subset \Gamma\,\! $ vstupních symbolů a $ *\in\Gamma\,\! $ prázdného symbolu
  2. Konečné množiny $ Q\,\! $ stavů řídící jednotky, která obsahuje startovní stav $ q_0\,\! $ a 2 terminální stavy $ q_Y\,\! $, $ q_N\,\! $
  3. Přechodové funkce $ \delta:(Q\backslash\{q_Y,q_N\})\times\Gamma\to Q\times\Gamma\times\{\leftarrow,\bullet, \rightarrow \}\,\! $

DTS s programem $ M\,\! $ přijímá $ x\in\Sigma^{*}\,\! $, právě když pro vstup $ x\,\! $ se $ M\,\! $ zastaví ve stavu $ q_Y\,\! $. Jazyk rozpoznávaný programem M je $ L(M)=\{x\in\Sigma^{*}|M \mbox{ prijima } x\}\,\! $.

DTS s programem $ M\,\! $ řeší problém $ Q\,\! $, právě když výpočet $ M\,\! $ skončí pro každý vstup $ x\in\Sigma^{*}\,\! $ a platí $ L(M)=L(Q)_Y\,\! $.

Nechť $ M\,\! $ je program pro DTS, který skončí pro $ \forall x\in\Sigma^{*}\,\! $. Časová složitost programu $ M\,\! $ je dána funkcí $ T_M(n)=\max\{m|\exists x\in\Sigma^{*},|x|=n, $ výpočet na DTS s programem $ M\,\! $ a vstupem $ x\,\! $ skončí po $ m\,\; $ krocích stroje$ \}\,\! $. Pokud existuje polynom $ p\,\! $ tak, že $ T_M(n)\leq p(n) \forall n\,\! $, pak $ M\,\! $ je polynomiální DTS program.

Definice (Třída P)

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

Definice (Nedeterministický Turingův stroj)

Stejný jako DTS, ale místo přechodové funkce $ \delta\,\! $ je zde zobrazení $ \delta\,\! $, které každé dvojici z $ Q\times\Gamma\,\! $ přiřazuje množinu možných pokračování výpočtu, tj. trojic z $ Q\times\Gamma\times\{\leftarrow,\bullet, \rightarrow \}\,\! $.

NTS s programem $ M\,\! $ přijímá $ x\in\Sigma^{*}\,\! $, právě když existuje přijímající výpočet programu $ M\,\! $ (tj. běh $ M\,\! $, kdy na vstupu je $ x\,\! $ a končí se ve stavu $ q_Y\,\! $). Jazyk rozpoznávaný programem M je $ L(M)=\{x\in\Sigma^{*}|M \mbox{ prijima } x\}\,\! $.

Čas, ve kterém $ M\,\! $ přijímá $ x\in\Sigma^{*}\,\! $ definujeme jako počet kroků nejkratšího přijímajícího výpočtu nad daty $ x\,\! $.

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

$ T_M(n)=\begin{cases}1 \mbox{ neexistuje }x\mbox{ delky }n\mbox{, ktere je prijimano }\\\max\{m|\exists x\in\Sigma^{*},|x|=n, M\mbox{ prijima }x\mbox{ v case }m\}\end{cases}\,\! $

Pokud existuje polynom $ p\,\! $ takový, že $ T_M(n)\leq p(n)\,\! $, pak $ M\,\! $ je polynomiální NTS program.

Definice (Třída NP)

Problém $ Q\,\! $ je ve třídě NP, právě když existuje polynomiální NTS program $ M\,\! $, který řeší $ Q\,\! $. 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 $ Q\,\! $ je ve třídě co-NP, právě když existuje polynomiální NTS program $ M\,\! $ takový, že $ L(M) = L(Q)_N\,\! $. 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 $ f:\{0,1\}^{*}\to\{0,1\}^{*}\,\! $ je polynomiálně vyčíslitelná, právě když existuje polynom $ p\,\! $ a algoritmus $ A\,\! $ takový, že pro každý vstup $ x\in \{0,1\}^{*}\,\! $ dává výstup $ f(x)\,\! $ v čase nejvýše $ p(|x|)\,\! $.

Definice (Polynomiální převoditelnost)

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

$ \forall x\in\{0,1\}^{*}:x\in L_1\equiv f(x)\in L_2\,\! $

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

  • Problém $ Q\,\! $ je NP-těžký, právě když $ \forall Q'\in\mathrm{NP}:L(Q')_Y\propto L(Q)_Y\,\! $.
  • Problém $ Q\,\! $ je NP-úplný, právě když je $ Q\,\! $ NP-těžký a $ Q\in\mathrm{NP}\,\! $.

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

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

Upraveno podle vypracovaných otázek V. Bedecse, původně zřejmě ze slajdů Doc. Čepka k Složitosti I . -- Tuetschek 10:28, 31 Aug 2010 (CEST)

Mě asi nejvedc chutnal nilskfd okoun jen tak opečenfd na me1sle, pak tuňe1k e1le1 steak, sekanfd btifek z lososa a z českfdch ryb bezkonkurenčně ve1nočned kapr!

NP-úplné problémy

Splnitelnost (SAT)

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

Důkaz transformací KACHL ∝ SAT: pomocí proměnných $ x_{ijk} $, kde $ x_{ijk} = 1 $, pokud na pozici $ [i,j] $ se nachází kachlík typu $ k $. 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.

Sara, you had an awesome saeson. You improved so much, I am always looking forward to your next game. Keep practicing and keep scoring. I am proud of you and I love you.

3-COLOR

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

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 $ G=(V, E) $ a přirozené číslo $ k $. Existuje $ V' \subseteq V $, $ |V’| = k $, indukující úplný podgraf grafu $ G $?

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 $ x_i $ a $ \neg x_i $ nevede hrana.

Your webtise has to be the electronic Swiss army knife for this topic.

Vrcholové pokrytí (VP)

Máme neorientovaný graf $ G=(V, E) $ a přirozené číslo $ r $. Existuje $ V' \subseteq V $, $ |V’| = r $ taková, že každá hrana má ve $ V' $ 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 $ G=(V,E) $. Obsahuje G hamiltonovskou kružnici, tj. jednoduchou kružnici, která prochází každým vrcholem právě jednou?

Transformace VP ∝ HK

Transformace VP ∝ HK: Na $ |V| $ 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 $ v_1,\dots,v_r $. 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 $ G=(V,E) $, váhy $ w : E \to \mathbb{Z}_0^+ $ a číslo $ k \in \mathbb{Z}^+ $. Existuje v $ G $ hamiltonovská kružnice s celkovou váhou nejvýše $ k $? 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 $ w(e) = 1 $, pokud $ e $ byla v původním grafu a $ w(e) = 2 $ jinak. Je-li chtěná váha rovna počtu vrcholů původního grafu, řešení dává HK v něm.