{{TOC float}}
{{Sources|
''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] ze [[Státnice_-_Informatika_-_Složitost_(obory_Matematická_lingvistika_a_Softwarové_systémy)|složitosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze zápisků z předmětu [[Složitost I]] -- [[User:Tuetschek|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.
====Definice (Kódování vstupů)====
Každá instance problému <math> Q\,\!</math> je kódována jako posloupnost 0 a 1, tj. instance je <u>slovo v abecedě</u> <math> \{0,1\}^{*}\,\!</math>. Kódy všech instancí problému <math> Q\,\!</math> tvoří <u>jazyk</u> <math> L(Q)\,\!</math> nad abecedou <math> \{0,1\}^{*}\,\!</math>, který se dělí na
* <math> L(Q)_Y\,\!</math> -- kódy instancí s odpovědí ANO (jazyk kladných instancí)
* <math> L(Q)_N\,\!</math> -- kódy instancí s odpovědí NE (jazyk záporných instancí)
Rozhodovací problém pak je rozhodnutí, zda <math> x\in L(Q)_Y\,\!</math> nebo <math> x\in L(Q)_N\,\!</math> (kde <math> x\,\!</math> je kód nějaké instance <math> Q\,\!</math>), když předpokládáme, že rozhodnutí <math> x\in L(Q)\,\!</math> lze udělat v polynomiálním čase vzhledem k <math> |x|\,\!</math>.
====Definice (Deterministický Turingův stroj)====
DTS obsahuje řídící jednotku, čtecí a zápisovou hlavu a (nekonečnou) pásku. Program sestává z:
# Konečné množiny <math> \Gamma\,\!</math> páskových symbolů, <math> \Sigma \subset \Gamma\,\!</math> vstupních symbolů a <math> *\in\Gamma\,\!</math> prázdného symbolu
# Konečné množiny <math> Q\,\!</math> stavů řídící jednotky, která obsahuje startovní stav <math> q_0\,\!</math> a 2 terminální stavy <math> q_Y\,\!</math>, <math> q_N\,\!</math>
# Přechodové funkce <math> \delta:(Q\backslash\{q_Y,q_N\})\times\Gamma\to Q\times\Gamma\times\{\leftarrow,\bullet, \rightarrow \}\,\!</math>
DTS s programem <math> M\,\!</math> ''přijímá'' <math> x\in\Sigma^{*}\,\!</math>, právě když pro vstup <math> x\,\!</math> se <math> M\,\!</math> zastaví ve stavu <math> q_Y\,\!</math>. ''Jazyk rozpoznávaný programem M'' je <math> L(M)=\{x\in\Sigma^{*}|M \mbox{ prijima } x\}\,\!</math>.
DTS s programem <math> M\,\!</math> ''řeší'' problém <math> Q\,\!</math>, právě když výpočet <math> M\,\!</math> skončí pro každý vstup <math> x\in\Sigma^{*}\,\!</math> a platí <math> L(M)=L(Q)_Y\,\!</math>.
Nechť <math> M\,\!</math> je program pro DTS, který skončí pro <math> \forall x\in\Sigma^{*}\,\!</math>. Časová složitost programu <math> M\,\!</math> je dána funkcí <math> T_M(n)=\max\{m|\exists x\in\Sigma^{*},|x|=n,</math> výpočet na DTS s programem <math>M\,\!</math> a vstupem <math>x\,\!</math> skončí po <math>m\,\;</math> krocích stroje<math>\}\,\!</math>. Pokud existuje polynom <math> p\,\!</math> tak, že <math> T_M(n)\leq p(n) \forall n\,\!</math>, pak <math> M\,\!</math> je ''polynomiální DTS program''.
====Definice (Třída P)====
Problém <math> Q\,\!</math> je ve třídě P, právě když existuje polynomiální DTS program <math> M\,\!</math>, který řeší <math> Q\,\!</math>.
====Definice (Nedeterministický Turingův stroj)====
Stejný jako DTS, ale místo přechodové funkce <math> \delta\,\!</math> je zde zobrazení <math> \delta\,\!</math>, které každé dvojici z <math> Q\times\Gamma\,\!</math> přiřazuje <u>množinu</u> možných pokračování výpočtu, tj. trojic z <math> Q\times\Gamma\times\{\leftarrow,\bullet, \rightarrow \}\,\!</math>.
NTS s programem <math> M\,\!</math> ''přijímá'' <math> x\in\Sigma^{*}\,\!</math>, právě když existuje přijímající výpočet programu <math> M\,\!</math> (tj. běh <math> M\,\!</math>, kdy na vstupu je <math> x\,\!</math> a končí se ve stavu <math> q_Y\,\!</math>). ''Jazyk rozpoznávaný programem M'' je <math> L(M)=\{x\in\Sigma^{*}|M \mbox{ prijima } x\}\,\!</math>.
Čas, ve kterém <math> M\,\!</math> přijímá <math> x\in\Sigma^{*}\,\!</math> definujeme jako počet kroků nejkratšího přijímajícího výpočtu nad daty <math> x\,\!</math>.
Časová složitost programu je dána funkcí:
:<math>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}\,\!</math>
Pokud existuje polynom <math> p\,\!</math> takový, že <math> T_M(n)\leq p(n)\,\!</math>, pak <math> M\,\!</math> je polynomiální NTS program.
====Definice (Třída NP)====
Problém <math> Q\,\!</math> je ve třídě NP, právě když existuje polynomiální NTS program <math> M\,\!</math>, který řeší <math> Q\,\!</math>. 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:
# Nedeterministicky hádá -- zapíše problém do orákula.
# 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 <math> Q\,\!</math> je ve třídě co-NP, právě když existuje polynomiální NTS program <math> M\,\!</math> takový, že <math> L(M) = L(Q)_N\,\!</math>. 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 <math> f:\{0,1\}^{*}\to\{0,1\}^{*}\,\!</math> je ''polynomiálně vyčíslitelná'', právě když existuje polynom <math> p\,\!</math> a algoritmus <math> A\,\!</math> takový, že pro každý vstup <math>x\in \{0,1\}^{*}\,\!</math> dává výstup <math> f(x)\,\!</math> v čase nejvýše <math> p(|x|)\,\!</math>.
====Definice (Polynomiální převoditelnost)====
Jazyk <math> L_1\,\!</math> je ''polynomiálně převoditelný'' na jazyk <math> L_2\,\!</math> (píšeme <math> L_1\propto L_2\,\!</math>), právě když existuje polynomiálně vyčíslitelná funkce <math> f\,\!</math> taková, že
:<math>\forall x\in\{0,1\}^{*}:x\in L_1\equiv f(x)\in L_2\,\!</math>
====Definice (NP-těžký, NP-úplný problém)====
* Problém <math> Q\,\!</math> je ''NP-těžký'', právě když <math> \forall Q'\in\mathrm{NP}:L(Q')_Y\propto L(Q)_Y\,\!</math>.
* Problém <math> Q\,\!</math> je ''NP-úplný'', právě když je <math> Q\,\!</math> NP-těžký a <math> Q\in\mathrm{NP}\,\!</math>.
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==
{{Sources|''Upraveno podle vypracovaných otázek V. Bedecse, původně zřejmě ze slajdů [[Ondřej Čepek|Doc. Čepka]] k [[Složitost I|Složitosti I]] .'' -- [[User:Tuetschek|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í) <math>F</math> na <math>n</math> proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli <math>F</math>?
Důkaz transformací '''KACHL ∝ SAT''': pomocí proměnných <math>x_{ijk}</math>, kde <math>x_{ijk} = 1</math>, pokud na pozici <math>[i,j]</math> se nachází kachlík typu <math>k</math>. 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) <math>F</math> na <math>n</math> Booleovských proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli <math>F</math>?
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í: <math>(a_{i,1} \vee a_{i,2} \vee a_{i,3} \vee \dots \vee a_{i,k_i})</math> odpovídá <math>(a_{i,1} \vee a_{i,2} \vee y_{i,1}) \wedge (\neg y_{i,1} \vee a_{i,3} \vee y_{i,2}) \wedge (\neg y_{i,2} \dots) \wedge \dots \wedge (\neg y_{i,k_i-3} \vee a_{i,k_i-1}\vee a_{i,k_i})</math>
==== 3-COLOR ====
Tříobarvení grafu: Mějme neorientovaný graf <math>G=(V, E)</math>. Lze obarvit vrcholy ve <math>V</math> třemi barvami tak, aby žádná hrana v <math>E</math> neměla na obou koncích vrcholy stejné barvy?
[[Image:3sat-3color.png|frame|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 <math>G=(V, E)</math> a přirozené číslo <math>k</math>. Existuje <math>V' \subseteq V</math>, <math>|V’| = k</math>, indukující úplný podgraf grafu <math>G</math>?
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 <math>x_i</math> a <math>\neg x_i</math> nevede hrana.
Your webtise has to be the electronic Swiss army knife for this topic.
==== Vrcholové pokrytí (VP) ====
Máme neorientovaný graf <math>G=(V, E)</math> a přirozené číslo <math>r</math>. Existuje <math>V' \subseteq V</math>, <math>|V’| = r</math> taková, že každá hrana má ve <math>V'</math> 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 <math>G=(V,E)</math>. Obsahuje G ''hamiltonovskou kružnici'', tj. jednoduchou kružnici, která prochází každým vrcholem právě jednou?
[[Image:hk-vp.png|frame|Transformace '''VP ∝ HK''']]
Transformace '''VP ∝ HK''': Na <math>|V|</math> 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''' <math>v_1,\dots,v_r</math>. 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 <math>G=(V,E)</math>, váhy <math>w : E \to \mathbb{Z}_0^+</math> a číslo <math>k \in \mathbb{Z}^+</math>. Existuje v <math>G</math> hamiltonovská kružnice s celkovou váhou nejvýše <math>k</math>? 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 <math>w(e) = 1</math>, pokud <math>e</math> byla v původním grafu a <math>w(e) = 2</math> jinak. Je-li chtěná váha rovna počtu vrcholů původního grafu, řešení dává '''HK''' v něm.
C2QK8d <a href="http://kqmbecrxajbd.com/">kqmbecrxajbd</a>
==Silná NP-úplnost, pseudopolynomiální algoritmy==
Apparently this is what the esetemed Willis was talkin' 'bout.
====Poznámka (O číselných problémech)====
Pokud pro nějaký problém <math> \Pi\,\!</math> platí, že <math> \forall I:max(I)\leq p(\,\!</math>''kód''<math> (I))\,\!</math> pro nějaký polynom <math> p\,\!</math>, 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 <math> p\,\!</math>, že by platila), nazýváme ''číselné problémy''.
====Věta (O pseudopolynomialitě a NP)====
Nechť <math> \Pi\,\!</math> je NP-úplný problém a není číselný. Pak pokud P<math> \neq\,\!</math>NP, nemůže být <math> \Pi\,\!</math> ř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ť <math> \Pi\,\!</math> je rozhodovací problém a <math> p\,\!</math> polynom. Potom <math> \Pi_p\,\!</math> označme množinu instancí (podproblém) problému <math> \Pi\,\!</math>, pro které platí <math> max(I)\leq p(\,\!</math>''kód''<math> (I))\,\!</math>. Potom máme-li pseudopolynomiální algoritmus <math> A\,\!</math>, který řeší problém <math> \Pi\,\!</math>, určitě existuje polynomiální algoritmus, řešící <math> \Pi_p\,\!</math>. Toto platí pro libovolné p.
====Důkaz====
Algoritmus <math> A'\,\!</math>, řešící <math> \Pi_p\,\!</math> v polynomiálním čase, otestuje <math> x\,\!</math> na přítomnost v <math> \Pi_p\,\!</math> (spočítá ''kód''<math> (x)\,\!</math> a <math> max(x)\,\!</math>) a pokud <math> x\in\Pi_p\,\!</math>, chová se stejně jako <math> A\,\!</math>, takže běží v čase <math> q(\,\!</math>''kód''<math> (x),max(x))\leq q(\,\!</math>''kód''<math> (x),p(\,\!</math>''kód''<math> (x))) = q'(\,\!</math>''kód''<math> (x))\,\!</math>.
====Definice (Silně NP-úplný problém)====
Rozhodovací problém <math> \Pi\,\!</math> je ''silně NP-úplný'', pokud <math> \Pi\in\,\!</math>NP a existuje polynom <math> p\,\!</math> takový, že podproblém <math> \Pi_p\,\!</math> je NP-úplný.
====Věta (O silné NP-úplnosti)====
Nechť problém <math> \Pi\,\!</math> je silně NP-úplný. Potom, pokud P<math> \neq\,\!</math>NP, neexistuje pseudopolynomiální algoritmus, který by řešil <math> \Pi\,\!</math>.
====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 <math> a_1,\dots a_{3m},b\in \mathbb{N}\,\!</math> takové, že <math> \forall j:\frac{1}{4}b\leq a_j\leq\frac{1}{2}b\,\!</math> a navíc <math> \sum_{j=1}^{3m} a_j = mb\,\!</math>. Existuje <math> S_1,\dots S_m\,\!</math> disjunktní rozdělení množiny <math> \{1,\dots,3m\}\,\!</math> takové, že <math> \forall i:\sum_{j\in S_i} a_j = b\,\!</math>?
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 <math> |G|\,\!</math> (v převodu <math> VP\propto SP\,\!</math> byla exponenciálně velká).
{{Statnice I3}}
