{{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==
====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 <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, \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, \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ě P, 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.'' -- [[User:Tuetschek|Tuetschek]] 10:28, 31 Aug 2010 (CEST)}}
=== Cook-Levinova věta ===
Existuje NP-úplný problém.
==== Důkaz pro KACHL ====
{{TODO|Dopsat zkráceně, [[KACHL|tady]] je detailní.}}
Máme množinu barev <math>B</math>, čtvercová síť <math>S</math> s obvodem obarveným barvami z <math>B</math> a množinu <math>K</math> typů kachlíků, kde je každý typ definován svou horní, dolní, levou a pravou barvou.
Lze síť <math>S</math> vykachlíkovat pomocí kachlíků z množiny <math>K</math> (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ě) <math>F</math> na <math>n</math> proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli <math>F</math>?
==== 3-SAT ====
Kubická CNF (vždy len 3 premenne v zatvorkach) <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''''.
==== 3-BG ====
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? Transformace '''3-SAT ∝ 3-BG'''.
==== 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 ∝ KL'''.
==== Nezávislá Množina (NM) ====
Mějme neorientovaný graf <math>G=(V, E)</math> a přirozené číslo <math>q</math>. Existuje <math>V' \subseteq V</math>, <math>|V’| = q</math>, taková, že uvnitř <math>V'</math> nejsou žádné hrany? Transformace '''KL ∝ NM'''.
==== 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'''.
==== 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? Transformace '''VP ∝ HK'''.
==== 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 <math>\mathbb{Z}^+</math>. Existuje v <math>G</math> hamiltonovská kružnice s celkovou váhou nejvýše <math>k</math>? Transformace '''HK ∝ TSP'''.
==== Součet podmnožiny (SP) ====
Jsou daná čísla <math>a_1 , \dots ,a_n , b \in \mathbb{Z}^+</math>. Existuje množina indexů <math>S \subseteq \{1,\dots ,n\}</math> taková, že <math>\sum_{i\in S} a_i = b</math>? Transformace '''VP ∝ SP'''.
==Silná NP-úplnost, pseudopolynomiální algoritmy==
====Příklad====
'''SP''' není exponenciální, ale polynomiální v počtu a velikosti čísel. Algoritmus:
# Nechť <math> a_1\leq a_2\leq \dots \leq a_n\,\!</math> a <math> A\,\!</math> je bitové pole délky <math> b\,\!</math> (kde <math> 1\,\!</math> na pozici <math> i\,\!</math> bude indikovat možnost vytvoření podmnožiny se součtem <math> i\,\!</math>).
# Všechny prvky pole <math> A\,\!</math> nastav na <math> 0\,\!</math>.
# Pro <math> i\,\!</math> od <math> 1\,\!</math> do <math> n\,\!</math> opakuj (hl. cyklus):
## <math> A[a_i]:=1\,\!</math>
## Pro <math> j\,\!</math> od <math> a_{i-1}\,\!</math> do <math> b\,\!</math> zkoušej: když <math> A[j] = 1\,\!</math> a <math> j+a_i\leq b\,\!</math>, nastav <math> A[j+a_i]:=1\,\!</math>
# Je-li <math> A[b] = 1\,\!</math>, podmnožina se součtem rovným <math> b\,\!</math> existuje.
Po <math> i\,\!</math>-tém průchodu hlavním cyklem obsahuje <math> A\,\!</math> jedničky právě u všech součtů neprázdných podmnožin <math> \{a_1,\dots,a_i\}\,\!</math>. Důkaz -- indukcí. Celk. složitost je <math> O(n\cdot b)\,\!</math>, 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 <math> \Pi\,\!</math> a jeho instance <math> I\,\!</math>. Pak definujeme:
* ''kód(I)'' -- délka zápisu (počet bitů) instance <math> I\,\!</math> 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 <math> I\,\!</math> (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''<math> (I)\,\!</math> a <math> max(I)\,\!</math>. 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 <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}}
