{{predmet|Složitost I|Ondřej Čepek|TIN062}}
* [http://ktiml.mff.cuni.cz/vyuka/materialy.html Oficiálne materiály KTIML on-line]
* [http://www.ms.mff.cuni.cz/~marem2am/tmp/sloz.ps Učebné texty k Složitosti a NP úplnosti] - obsahujú dôkazy k vetám z prednášky
* [http://mff.modry.cz/slozitost/ Materiály z mff.modry.cz]
* [http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/slozitost.sxw Další poznámky] (sxw)
* Nějaké kusy jsou asi i ve státnicovém okruhu [[Státnice - Informatika - Složitost|Složitost]]
= Zápočtové príklady =
Takto vypadajú niektoré riešenia niektorých zápočtových príkladov, preberaných na cvičeniach. Zatial aspoň tých ťažších. Ospravedlňujem sa za gramatycké i iné prípadné chyby. Dúfam, že to niekomu raz pomôže. [[User:Jsimlo|jsimlo]] 14:30, 27 Jan 2006 (CET)
Nebo řešení (alespoň náznakem a bez záruky) všech je v materilech na "modrym" viz "resene priklady by jirja" --[[User:Jirja|Jirja]] 13:48, 3 Feb 2006 (CET)
== Cvičení 1 ==
=== Medián ===
:Substituční metodou dokažte linearitu algoritmu pro hledání mediánu a stanovte konstantu linearity.
----
Z prednášky vieme, že časová zložitosť hľadania mediánu je <math>T(n)=c*n/5+T(n/5)+(n-1)+T(7/10*n)</math>. Podľa zadania máme substitučnou metódou (teda [[wen:Akra-Bazzi method|kuchařku]] nemôžeme použiť) dokázať, že <math>T(n) \in \theta(n)</math>. Chceme teda dokázať (podľa [[wen:Big o notation#Related asymptotic notations: O, o, Ω, ω, Θ, Õ|definície]] <math>\theta(n)</math>), že <math>n \in O(T(n))</math> a zároveň <math>T(n) \in O(n)</math>.
* Dôkaz, že <math>n \in O(T(n))</math>:
: Chceme dokázať, že <math>\exists \;n_0,\exists \;K>0\mbox{ také, že } |n| \le \; K |T(n)|\mbox{ pre všetky }n>n_0</math>. <math>n_0</math> by odhadom mohlo byť 5, K = 1. Skúsme dokázať, že <math>n \le T(n)</math>.
:: <math>n \le n - 1 + c*n/5</math>, pretože vieme, že c je prirodzené číslo a uvažujeme len <math>n \ge 5</math>.
:: <math>n \le n - 1 + c*n/5 \le c*n/5+T(n/5)+(n-1)+T(7/10*n) = T(n)</math>
* Dôkaz, že <math>T(n) \in O(n)</math>:
:Snažíme sa dokázať, že <math>\exists \;n_0,\exists \;K>0\mbox{ také, že } T(n) \le K*n \mbox{ pre všetky }n>n_0</math>. Začneme tentoraz od 1 (<math>n_0 = 1</math>), ale K si ponecháme na neskôr, pretože ho nevieme natipovať.
:: <math>T(1) \le K*1</math> ... platí.
:: <math>T(n) = c*n/5+T(n/5)+(n-1)+T(7/10*n) \le c*n/5+K*n/5+(n-1)+K*7/10*n \le</math>
::: <math>\le (c+5)*n/5 + K*n*9/10 = n*(2c+10+9*K)/10</math> a chceme, aby toto bolo menšie ako <math>K*n</math>. Teda:
:::: <math>n*(2c+10+9*K)/10 \le K*n</math>
:::: <math>2c+10+9*K \le 10*K</math>
:::: <math>2c+10 \le K</math>
:Stačí teda zobrať <math>K = 2c+10</math>, aby <math>T(n) \le K*n</math>. Hodnota multiplikatívnej konštanty je teda <math>2c+10</math>.
=== Kuchařka ===
: Najděte asymptotická řešení následujících rekurentních rovnic (předpokládejte, že T(n) je konstanta pro všechna n<3):
----
a) <math>T(n) = 2T(n/2) + n^3</math>
:Je to príklad na kuchařku A, kde a = 2, c = 2 a d = 3.
:: Keďže <math>\log_2(2) = 1 < 3</math>, tak <math>T(n) \in \theta(n^3)</math>.
b) <math>T(n) = T(9n/10) + n</math>
: Keďže <math>\log_{9/10} 1 = 0 < 1</math>, tak <math>T(n) \in \theta(n)</math>.
c) <math>T(n) = 16T(n/4) + n^2</math>
: Keďže <math>\log_4 16 = 2 = d</math>, tak <math>T(n) \in \theta(n^2 \log n)</math>.
d) <math>T(n) = 7T(n/3) + n^2</math>
: Keďže <math>\log_3 7 < 2</math>, tak <math>T(n) \in \theta(n^2)</math>.
e) <math>T(n) = 7T(n/2) + n^2</math>
: Keďže <math>\log_2 7 > 2</math>, tak <math>T(n) \in \theta(n^{\log_2 7})</math>.
f) <math>T(n) = 2T(n/4) + \sqrt n = 2T(n/4) + n^{1/2}</math>
: Keďže <math>\log_4 2 = 1/2</math>, tak <math>T(n) \in \theta(\sqrt n \log n)</math>.
g) <math>T(n) = T(n-1) + n</math>
: <math>T(n) = T(n-1) + n = T(n-2) + n-1 + n = T(n-3) + n-2 + n-1 + n =</math>
:: <math>= O(1) + \sum_{i=3}^n (n - i) = O(1) + \sum_{i=3}^n i = O(1) + n*(n+1)/2 \in \theta(n^2)</math>.
h) <math>T(n) = T(\sqrt n) + 1</math>
: Zadefinujeme si pomocnú funkciu takto: <math>R(x) := T(2^x)</math>.
:: Platí pre ňu: <math>R(x) = T(2^x) = T(\sqrt {2^x}) + 1 = T(2^{x/2}) + 1 = R(x/2) + 1</math>.
:: Na takúto funkciu môžeme aplikovať kuchařku a dostaneme:
::: Keďže <math>\log_2 1 = 0 = d</math>, tak <math>R(x) \in \theta(\log x)</math>.
: Pre T(n) potom platí, že <math>T(n) = R(\log_2 n) \in \theta(\log (\log_2 n)) = \theta(\log \log n))</math>.
i) <math>T(n) = 2 T(\sqrt n) + \log n</math>
: Zadefinujeme si pomocnú funkciu takto: <math>R(x) := T(2^x)</math>.
:: Platí pre ňu: <math>R(x) = T(2^x) = 2T(\sqrt {2^x}) + \log_2 2^x = 2 T(2^{x/2}) + x = 2 R(x/2) + x</math>.
:: Na takúto funkciu môžeme aplikovať kuchařku a dostaneme:
::: Keďže <math>\log_2 2 = 1 = d</math>, tak <math>R(x) \in \theta(x*\log x)</math>.
: Pre T(n) potom platí, že <math>T(n) = R(\log_2 n) \in \theta(\log_2 n * \log (\log_2 n)) = \theta(\log n \log \log n))</math>.
j) <math>T(n) = 3T(n/2) + n \log n</math>
: Tu treba využiť, že <math>\log n \in O(n^ \epsilon) \mbox{ pre všetky } \epsilon > 0</math>.
: Keďže <math>\log_2 3 > 1</math>, tak <math>T(n) \in \theta(n^{\log_2 3})</math>.
k) <math>T(n) = T(n-1) + 1/n</math>
: <math>T(n) = T(n-1) + 1/n = T(n-2) + 1/(n-1) + 1/n = O(1) + \sum_{i=3}^n 1/i = O(1) + \ln n \in \theta(\log n)</math>.
l) <math>T(n) = T(n-1) + \log n</math>
: <math>T(n) = T(n-1) + \log n = T(n-2) + \log (n-1) + \log n = O(1) + \sum_{i=3}^n \log n = O(1) + \log {\prod_{i=3}^n i} \in \theta(\log n!)</math>.
m) <math>T(n) = 2T(n/5) + T(n/2) + n</math>
: Prvý príklad podľa kuchařky B:
:: Keďže <math>2*(1/5)^1 + 1/2^1 = 2/5 + 1/2 = 4/5 < 1</math>, tak <math>T(n) \in \theta(n)</math>.
n) <math>T(n) = 3T(n/2) + 4T(n/4) + n^2</math>
: Podľa kuchařky B:
:: Keďže <math>3*(1/2)^2 + 4*(1/4)^2 = 3*1/4 + 4*1/16 = 4/4 = 1</math>, tak <math>T(n) \in \theta(n^2 \log n)</math>.
o) <math>T(n) = 2T(2n/3) + T(n/3) + n \sqrt n</math>
: Podľa kuchařky B:
:: Keďže <math>2*(2/3)^{3/2} + (1/3)^{3/2} > 1</math>, tak musíme dopočítať l.
:: <math>2*(2/3)^l + (1/3)^l = 1</math>. Teda l = 2. Z toho vyplýva, že <math>T(n) \in \theta(n^2)</math>.
=== Strassen ===
: Jak rychle lze vynásobit obdélníkové matice velikosti (kn x n) a (n x kn) pokud použijeme Strassenův algoritmus pro násobení matic velikosti (n x n) jako podproceduru? Zkuste obě možná pořadí násobení a odvoďte asymptotickou složitost takových násobení (jako funkci k a n).
----
* Násobíme matice v poradí (kn x n) x (n x kn).
: Klasickým násobením potrebujeme <math>k^2 n^3</math> násobení.
: Ak použijeme Strassenov algoritmus na násobenie matíc n x n (ktorý má zložitosť <math>O(n^{log_2 7})</math> - to vieme z prednášky), môžeme obe matice chápať, ako trochu prerastené matice k x 1 a 1 x k, pričom vynásobenie dvoch prvkov trvá <math>O(n^{log_2 7})</math>. Keď násobím matice k x 1 a 1 x k, zaberie mi to <math>k^2</math> času. Celková zložitosť je teda <math>O(k^2 n^{log_2 7})</math>.
* Násobíme matice v poradí (n x kn) x (kn x n).
: Klasickým násobením potrebujeme <math>k n^3</math> násobení.
: Ak použijeme Strassenov algoritmus na násobenie matíc n x n (ktorý má zložitosť <math>O(n^{log_2 7})</math>), môžeme obe matice chápať, ako trochu prerastené matice 1 x k a k x 1, pričom vynásobenie dvoch prvkov trvá <math>O(n^{log_2 7})</math>. Keď násobím matice 1 x k a k x 1, zaberie mi to k času. Celková zložitosť je teda <math>O(k n^{log_2 7})</math>.
== Cvičení 2 ==
{{TODO|}}
=== Matroid 1 ===
: Nechť S je konečná neprázdná množina o n prvcích a k je přirozené číslo menší než n. Nechť I je množina všech podmnožin množiny S o velikosti nejvýše k. Dokažte, že (S,I) je matroid.
----
* Dôkaz, že S je neprázdna konečná množina nepotrebujeme (lebo to vieme zo zadania).
* Dôkaz dedičnej vlastnosti, teda že: <math>\forall A,B, A \sub B, B \in I: A \in I</math>:
: Nech <math>B \in I => |B| \le k</math>. Ďalej nech A je ľubovoľná podmnožina B. Potom <math>|A| \le k => A \in I</math>. Q.E.D.
* Dôkaz výmennej vlastnosti, teda že: <math>\forall A,B \in I, |A| < |B|: \exist x \in B \setminus A: A \cup \{x\} \in I</math>:
: Nech B je ľubovoľná množina z I. Potom <math>|B| \le k</math>. Ďalej nech A je množina z I taká, že <math>|A| < |B| \le k => |A| < k</math>. Potom stačí zobrať ľubovoľné x z B \ A (že nejaké existuje, je jasné, pretože B je väčšia ako A) a <math>|A \cup \{x\}| = |A| + 1 \le k => A \cup \{x\} \in I</math>. Q.E.D.
=== Matroid 2 ===
: Nechť S je konečná neprázdná množina a nechť <math>S_1, S_2, ..., S_n</math> je rozdělení množiny S na po dvou disjunktní podmnožiny. Nechť <math>I = \{A | \forall i: |A \cap S_i| \le 1\}</math>. Dokažte, že (S,I) je matroid.
----
* Dôkaz, že S je neprázdna konečná množina nepotrebujeme (lebo to vieme zo zadania).
* Dôkaz dedičnej vlastnosti, teda že: <math>\forall A,B, A \sub B, B \in I: A \in I</math>:
: Nech <math>B \in I => \forall i: |B \cap S_i| \le 1</math>. Ďalej nech A je ľubovoľná podmnožina B. Potom <math>\forall i: |A \cap S_i| \le |B \cap S_i| \le 1 => A \in I</math>. Q.E.D.
* Dôkaz výmennej vlastnosti, teda že: <math>\forall A,B \in I, |A| < |B|: \exist x \in B \setminus A: A \cup \{x\} \in I</math>:
: Všetky množiny z I majú tú vlastnosť, že každé <math>S_i</math> je v nich zastúpené maximálne raz, teda každý ich prvok "zastupuje" nejaké <math>S_i</math>. Takže si zoberme ľubovoľné <math>B \in I</math> a <math>A \in I</math> menšie ako B. Z toho vyplýva, že B má v sebe viac zastúpených <math>S_i</math> ako A. Zoberme jedno z takých <math>x \in B</math>, ktoré zastupuje také <math>S_i</math>, ktoré v A zastúpené nie je. Toto <math>x \in B \setminus A</math>, pretože ak by patrilo do A, tak by neplatila predošlá veta. Tiež platí, že <math>A \cup \{x\} \in I</math>, teda Q.E.D.
=== Matroid 3 ===
:Nechť (S,I) je matroid a nechť J = {A | S-A obsahuje nějakou maximální množinu z I}. Dokažte, že (S,J) je matroid.
----
*(S,I) je matroid a preto S je neprazdna, konecna.
*Dedicnost:
:Kedze <math>B \subset A</math> tak <math>(S-A) \subset (S-B)</math>. Takze maximalna mnozina, ktora bola v <math>I</math> pre <math>B</math> tam urcite bude aj pre <math>A</math>.
*Vymenna vlastnost
:Chceme: <math>A', B' \in J; |A'|\ <\ |B'|; \mbox{pak}\ \exists x \in B' \setminus A', \mbox{ze}\ \{x\} \cup A' \in J.</math>
:Oznacme: <math>A \in I</math> ako maximalnu mnozinu pre <math>A' \in J</math> a <math>B \in I</math> ako maximalnu mnozinu pre <math>B' \in J</math>.
:Dalej oznacme:[[Image:Slozitost1_matroid3.png|frame|Oznacenie mnozin]]
:<math>Z = B' - (A \cup A')</math>
:<math>X = A \cap B'</math>, <math>Y = B \cap A'</math>,
:<math>V = A - X\!</math>, <math>W = B - Y\!</math>
:Mame dva pripady:
:*<math>Z \ne \emptyset</math>
::<math>\exists x \in Z</math>, ktory mozeme dolnit do <math>A'\!</math> aby stale platilo <math>A \subset S-(A' \cup \{x\})</math>.
:*<math>Z = \emptyset</math>
::Musime na to inak. Ukazeme, ze prvok na doplnenie sa da najst niekde v <math>X</math>.
::Vieme: <math>(|A'|\ <\ |B'|, Z = \emptyset) \Rightarrow (|Y|\ <\ |X|)</math>
::Vieme: <math>(|A| = |B|, |Y|\ <\ |X|) \Rightarrow (|V|\ <\ |W|) \Rightarrow (|W| \ne \emptyset)</math>
::<math>(S,I)</math> je matroid a preto podla vymennej vlastnosti mozme <math>V</math> doplnit aspon jednym prvkom <math>W</math>. Doplnime teda ten jeden prvok z <math>W</math> a potom este doplnime prvky z <math>X</math> tak, aby sme ziskali <math>V_{max}\!</math>, ktora bude maximalna v <math>I</math> a zaroven bude patrit do <math>S-A'\!</math>. Takto nam ale v <math>X</math> musel zostat jeden nedoplneny prvok, pretoze <math>A</math> bolo maximalne. Mame teda <math>B' - (A' \cup V_{max}) \ne \emptyset</math>, kde sa nachadza prvok, ktory mozme doplnit do <math>A'\!</math> aby platilo <math>V_{max} \subset S-(A' \cup \{x\})</math>.
== Cvičení 3 ==
=== Stok ===
1. Nechť je orientovaný graf <math>G = (V,E)</math>, kde <math>|V| = n</math>, zadán maticí sousednosti. Navrhněte algoritmus, který zjistí, zda <math>G</math> obsahuje '''stok''', tj. vrchol <math>x</math> takový, že vstupní stupeň <math>x</math> je <math>n-1</math> a výstupní stupeň <math>x</math> je <math>0</math>, přičemž algoritmus smí použít (přečíst) pouze <math>O(n)</math> prvků matice (předpokládejme, že před zahájením algoritmu je již celá matice načtena do paměti).
----
Takový vrchol má ve svém sloupci samé <math>1</math> (kromě svého řádku) a ve svém řádku samé <math>0</math> a navíc je v grafu určitě jen jeden. Proto mohu jít od bodu po řádku <math>[0,0]</math> a dokud nalézám nuly, pokračovat (tím vylučuji všechny vrcholy, příslušné sloupcům, kde by musela být <math>1</math>).
Když najdu jedničku, pokračuji po sloupcích a vylučuji vrcholy příslušné řádkům. Pokud na řádku nebo sloupci <math>k</math> vylezu z matice, pak <math>k</math> je jediný kandidát na stok a mohu otestovat jeho celý řádek nebo sloupec.
=== Bipartita ===
2. Navrhněte algoritmus založený na BFS, který rozhodne, zda daný neorientovaný graf je bipartitní a pokud ano, oddělí obě partity.
----
Začneme z nějakého vrcholu, obarvíme ho barvou <math>A</math> a potom v BFS pokud jdeme z vrcholu s barvou <math>A</math>, obarvíme všechny jeho následníky barvou <math>B</math> a naopak. Pokud bychom zjistili, že nějaký z následníků už je barevný stejně jako jeho předch. vrchol, víme, že graf není bipartitní (do vrcholu existuje cesta ze zdroje, jak sudé, tak liché délky) a končíme.
=== Topologické číslování ===
3. Víme, že DFS nalezne topologické očíslování vrcholů acyklického grafu podle klesajících časů opuštění. Dokažte nebo vyvraťte, že pro libovolný (i cyklický) graf takové očíslování minimalizuje počet ''inkonzistentních'' hran (tj. takových, které vedou proti topologickému očíslování).
----
Neplatí. Je pěkný protipříklad na 3 nebo 4 vrcholech, nakreslil bych ho sem, ale nejsem schopny ziskat login :(.
=== Polosouvislost ===
4. Orientovaný graf <math>G</math> se nazývá polosouvislý, pokud pro každé dva vrcholy <math>x,y</math> existuje v <math>G</math> buď orientovaná cesta z <math>x</math> do <math>y</math>, nebo orientovaná cesta z <math>y</math> do <math>x</math>. Navrhněte algoritmus na testování polosouvislosti grafů s co nejlepší asoymptotickou složitostí
----
:Pro acyklické:
Platí věta '''Acyklický graf <math>G</math> je polosouvislý, právě když v něm existuje orientovaná cesta na všech vrcholech.''' -- implikace zprava doleva je trivka, zleva doprava jde sporem (v topologickém uspořádání najdu <math>(i,i+1)\notin E</math>.
:Pro obecné:
Algoritmus:
* Najít silně souvislé komponenty (lin. algoritmus)
* Sestavit acyklickou kondenzaci (jedna SSK --> 1 vrchol)
* Pustit na to acyklický případ
Platí totiž věta: '''G je polouvislý, právě když jeho acyklická kondenzace je polosouvislá.''' --- implikace zprava doleva je triviální, vezmu dvě komponenty, mezi nimi je cesta jedním směrem, a v rámci těch komponent to jde převést na cestu z kteréhokoliv do kteréhokoliv vrcholu. Druhá implikace je ještě lehčí -- najdu cestu a zkondenzuji.
== Cvičení 4 ==
=== Dijkstra Error ===
Zkonstruujte příklad grafu se zápornými hodnotami hran (bez záp. cyklů), na kterém selže Dijkstrův algoritmus.
----
4 vrcholy A, B, C, D a hrany/váhy AB: 3, BC: -3, AC: 1, CD: 1. Při hledání cesty z A mu vyjde, že D je ve vzdálenosti 2, když ve skutečnosti je vzdálenost 1 (nejlepší je si to nakreslit).
=== Nespolehlivá síť ===
Máme nějakou komunikační síť, tedy orientovaný <math>G=(V,E)</math>, kde pro každou hranu <math>(u,v)</math> je dána ''"spolehlivost"'' <math>0<w(u,v)<1</math> (pravděpodobnost, že tato hrana při komunikaci neselže). Tyto pravděpodobnosti jsou nezávislé. Vytvořte algoritmus pro nalezení nejspolehlivější cesty v síti.
----
# řešení: Dijkstra upravený tak, že <math>\infty := 0</math>, <math>0 := 1</math>, <math>+ := *</math>, extractMin := extractMax a decreaseKey := increaseKey
# řešení:<math>w'(e)= -\log_2 w(e)</math> a normální Dijkstra
=== Dijkstra s omezenou váhovou funkcí ===
Nechť je dán vážený orientovaný graf <math>G=(V,E)</math>, kde <math>|V|=n, |E|=m</math> a váhy na hranách jsou zadány funkcí <math>w:E\to \{1,2,\dots,k\}</math>. Dále předpokládejme, že <math>k<n</math>. Implementujte Dijkstrův algoritmus tak, aby běžel v <math>O(nk+m)</math>
----
Vytvořím pole délky <math>k\cdot n</math> a v něm udržuji vrcholy v aktuální vzdálenosti od začátku (vrcholy se stejnou vzdáleností ve spojácích). Potom při extractMin stačí jít o <math>k</math> prvků dopředu, protože jinak je všechno v nekonečnu. Při decreaseKey jen přehodím jeden prvek. Z toho mám:
* extractMin <math>O(k)</math>
* decreaseKey <math>O(1)</math>
Celkem tedy <math>O(nk+m)</math>. Dá se to i vylepšit a používat jen pole délky <math>(k+1)</math> (za pomoci modulení).
=== Vylepšení ===
Změňte implementaci předchozího problému tak, aby algoritmus běžel v <math>O((n+m)\log k)</math>.
----
Vyrobím si haldu (o velikosti maximálně <math>k+1</math>), ze které vedou pointery na podle vzdálenosti setříděné spojáky vrcholů se stejnou vzdáleností <math>\mod k+1</math>. Potom:
* extractMin -- max. mi zanikne jeden spoják a musím upravit haldu -- <math>O(\log k)</math>
* decreaseKey -- max. <math>O(\log k)</math> na odebrání prvku ze vzdálenější pozice + <math>O(\log k)</math> na přidání do bližší.
== Cvičení 5 ==
Ja som na tom cviku nebol, ale príklady sú očividne v pohode. Prvý je trivka, druhý používa trochu z výrokovej a predikátovej logiky. Asi je rozumné vedieť, čo je to CNF a DNF, inak žiadne zákernosti. [[User:Jsimlo|jsimlo]] 16:00, 27 Jan 2006 (CET)
=== SAT ===
:Nechť máme k dispozici ''černou skřínku'', která umí řešit SAT (rozhodovací problém splnitelnosti CNF formulí) v polynomiálním čase. Zkonstruujte algoritmus, které pro danou CNF najde v polynomiálním čase splňující ohodnocení proměnných, pokud takové ohodnocení existuje.
----
Algoritmus bude fungovat po krokoch. V kazdom kroku ''i'' dosadi za <math>x_i</math> hodnotu, BUNO napriklad hodnotu 0. Formulu s dosadenou hodnotou predlozi SAT skrinke a podla odpovedi bud necha <math>x_i</math> = 0, alebo dosadi hodnotu opacnu.
Po najviac ''n'' krokoch, kde ''n'' je pocet premennych formule, dosadime za vsetky <math>x_i</math> nejake hodnoty, ktore stale splnuju formulu. Mame teda nejake jej splnitelne ohodnotenie, pokial existuje.
Pozn.: Algoritmus predkladal upravenu formulu SAT skrinke iba raz za kazdy krok. Mohlo sa nam preto stat, ze vysledok, ktory sme vygenerovali nie je spravnym vysledkom, pretoze ziaden spravny vysledok neexistuje (hlavne u nesplnitelnych formuli :). To sa da osetrit jednoducho. Uplne na zaciatku algoritmu sa spytame SAT skrinky, ci je vstupna formula vobec splnitelna. Pokial nie, nema vyznam ulohu dalej riesit. Pokial splnitelna je, urcite najdeme jej ohodnotenie.
Zlozitost: ''n''-krat pouzijeme polynomialnu skrinku SAT, sme teda stale polynomialny.
=== TAUT ===
:Definujme problém TAUT následovně:
:<u>Instance</u>: Boolovská formule ''F'' sestávající z ''n'' proměnných a operací negace, disjunkce a konjunkce.
:<u>Otázka</u>: Je ''F'' tautologie?
:a) Je TAUT ve třídě NP?
:b) Je TAUT ve třídě co-NP?
:c) Jaká je složitost TAUT pokud je ''F'' CNF?
:d) Jaká je složitost TAUT pokud je ''F'' DNF?
----
Třída co-NP je třída takových problémů, jejichž "otočené" verze (odpovědi NE a ANO se prohodí) jsou v NP (jestli <math>coNP \cap NP = \emptyset</math>, nikdo neví)
----
*a) Nevie sa (víme, že je to ve třídě co-NP, ale o NP nic netušíme)
*b) Ano. Certifikatom pre zápornú odpoveď je ohodnotenie, kde formula nie je splnitelna.
*c) Linearna.
:<math>A \land B</math> je tautologia, pokial aj ''A'' aj ''B'' su tautologie. Kazda podformula formule ''F'', plna samych disjunkci, teda musi byt sama o sebe tautologiou. A to je prave vtedy, ked sa v nej nachadza nejaka formula a zaroven i jej negacia.
*d) coNP-C. Ukazeme, ze pokial vieme riesit coTAUT, vieme riesit i SAT.
:<math>SAT \propto \overline{TAUT}</math>
:*Majme problem <math>\overline{TAUT}</math>. Instance: Formule ''F'' je DNF. Otazka: <math>\exists x_1..x_n: F[x] = 0?</math>
:*A majme problem <math>SAT\,\!</math>. Instance: Formule ''F'' je CNF. Otazka: <math>\exists x_1..x_n: F[x] = 1?</math>
:Trivialne vieme, ze <math>(F[x] = 1) \equiv (\lnot F[x] = 0)</math> a pomocou DeMorganovych pravidiel vieme, ze <math>\lnot CNF[x] \equiv DNF[\lnot x]</math>.
:Takze <math>\overline{TAUT}[\lnot F] \equiv SAT[F]</math>. <math>\overline{TAUT}</math> je teda NP-C a TAUT je coNP-C.
== Cvičení 6 ==
Snažil som sa problémy opísať čo najpolopatistickejšie, dúfam, že i korektne, keď tak ma opravte. Keď tomu človek vôbec nerozumie, mal by si asi skúsiť prečítať aspoň definíciu NP a NP-úplnosti z teórie ešte pred zápočtom. Doporučujem texty od Majerecha, je to tam celkom príjemne napísané. Rovnako pomôže, keď človek vie, o čom sú tie problémy, na ktoré sa snažíme prevádzať. To sa dá pomerne stručne a jasne nájsť napríklad na slajdoch od Čepka. Inak potom je to už jednoduché. Žiadne extra drsné triky ani nápady.. :)) [[User:Jsimlo|jsimlo]] 15:56, 27 Jan 2006 (CET)
=== LOUP ===
:Definujme problém LOUP (loupežníci) následovně:
:<u>Instance</u>: Přirozená čísla a1, ... , an
:<u>Otázka</u>: Existuje podmnožina T množiny indexů ''S'' = {1, ... ,n} taková, že <math>\sum_{i \in T} a_i = \sum_{i \in S-T} a_i</math>
:Dokažte, že LOUP je NP-úplný problém.
----
*<math>LOUP \in NP</math>:
:Certifikat: Mnozina indexov rozdelenia.
*<math>SP \propto LOUP</math>:
:Mame zadanie SP ako mnoziny <math>a_1..a_n,\ b</math>.
:Polozime <math>A = \sum_{i=1}^n a_i, \qquad b' = \max {\{b, A-b\}} \ge A/2, \qquad a_{n+1} = 2b' - A</math> a riesime LOUP pre <math>a_1,\ ...,\ a_n,\ a_{n+1}</math>.
:Inymi slovami, mame kopu roznych minci <math>a_1 .. a_n</math> a chceme z nich poskladat sumu ''b'' algoritmom delenia na polovicu. Vyrobili sme si preto jednu specialnu mincu <math>a_{n+1}</math>, ktora dolpna celkovy sucet minci tak, aby pri ich rozdeleni na dve polovice bolo ''b'' na jednej strane a zvysne mince na druhej. Nasa specialna minca skonci podla velkosti ''b'' bud na jednej strane spolu z ''b'' alebo na druhej strane spolu s ostatnymi mincami. Tak ci tak sme oddelili ''b'' od zvysku.
:Tvrdenie: Skonstruovana instancia pre LOUP ma riesenie, prave ked ma riesenie vstupna instancia SP.
:<math>\Rightarrow</math>
::<math>\exists T \subseteq {1..n+1}: \sum_{i \in T} a_i = \sum_{i \in S-T} a_i</math>
::BUNO nech <math>n+1 \notin T</math>, potom <math>\sum_{i=1}^{n+1} a_i = A+2b'-A = 2b'</math>, a teda <math>\sum_{i \in T} a_i = b'</math>, pretoze nam LOUP rozdelil zadanie na dve polovice.
::Takze pokial
:::a) <math>b' = b</math>, potom ''T'' je riesenim SP,
:::b) <math>b' = A-b</math>, potom ''S-T'' je riesenim SP.
:<math>\Leftarrow</math>
::<math>T: \sum_{i \in T} a_i = b</math>
::Takze pokial
:::a) <math>b' = b</math>, potom priradme <math>T':= T</math>,
:::b) <math>b' = A-b</math>, potom priradme <math>T':= S-T</math>.
::Plati, ze <math>\sum_{i \in T'} a_i = b'</math> a preto nase <math>T'\,\!</math> je riesenim LOUP.
<!-- nejak divne to "T s ciarkou" vypadalo, ked rendrovalo ako HTML, tak som tam pridal ten force. jsimlo -->
=== PATH ===
:Nejkratší cestu mezi dvěma vrcholy v neorientovaném váženém grafu lze nalézt pomocí Dijkstrova algoritmu, pokud jsou zadané váhy na hranách nezáporné. Jak se změní složitost této úlohy, pokud povolíme, aby byly váhy záporné?
----
Zlozitost bude NP-C. Ukazeme, ze <math>HK \propto HC</math> a <math>HC \propto PATH</math>. PATH je nas problem zo zadania.
<math>PATH \in NP</math>
:Certifikat: zoznam vrcholov cesty.
<math>HK \propto HC</math>
[[Image:Slozitost1_hc-hk.png|frame|Nakres grafu G a pridaneho vrcholu z. S vrcholom z spojime iba tie vrcholy, ktore su spojene aj s x.]]
:Mam neorientovany graf ''G'' a chcem v nom najst HK. Zvolim si nejaky vrchol ''x'' z grafu ''G''. Potom upravim graf ''G'' tak, ze pridam novy vrchol ''z'' a spojim ho hranou zo vsetkymi vrcholmi, ktore boli spojene z ''x''. Takze mam <math>\forall y: e(x,y) \equiv e(z,y)</math>.
:V upravenom grafe hladam HC z vrcholu ''x'' do vrcholu ''z''. Pokial najdem, tak posledna hrana v najdenej ceste vedie z vrcholu ''v'' do ''z''. Takyto vrchol ''v'' je ale spojeny hranou aj z vrcholom ''x'', a preto sa da posledna hrana <math>e(v,z)</math> nahradit za <math>e(v,x)</math>, cim uzavrieme kruznicu prechadzajucu vsetkymi povodnymi vrcholmi. Nasli sme teda HK pomocou HC.
<math>HC \propto PATH</math>
:Mam graf ''G'' a chcem v nom najst HC. Pridam ku grafu ''G'' ohodnotenie ''-1'' na vsetkych hranach. Na takto ohodnotenom grafe pustim nas problem PATH, ktory mi najde najkratsie cesty. V pripade nasho ohodnotenia bude ale najkratsia cesta zaroven i cesta, ktora prejde najviac vrcholov. Overime teda, ci ma hladana cesta dlzku <math>-(n-1)</math> a pokial ano, je tato cesta HC.
=== 0-1 CP ===
:Definujme problém 0-1 CP (celočíselné programování) následovně:
:<u>Instance</u>: Celočíselná matice ''A'' řádu ''m'' krát ''n'' a celočíselný vektor ''b'' délky ''m''
:<u>Otázka</u>: Existuje vektor ''x'' délky ''n'' obsahující pouze čísla 0 a 1 takový, že <math>Ax \le b</math> ?
:Dokažte, že 0-1 CP je NP-úplný problém.
----
<math>CP \in NP</math>
Certifikat: Vektor <math>x</math> (zlozeny z nul a jedniciek).
<math>SP \propto CP</math>
Mame zadanie problemu SP: cisla <math>a_1..a_n</math> a cislo <math>b</math>.
Z cisel <math>a_1..a_n</math> poskladame maticu a vektor nasledujucim sposobom:
<math>
A' = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ a_1 & a_2 & \cdots & a_n \\ \vdots & \vdots & \ddots & \vdots \\ -a_1 & -a_2 & \cdots & -a_n \end{pmatrix}
,\qquad
b' = \begin{pmatrix} b \\ b \\ \vdots \\ -b \end{pmatrix}
</math>
Na takto postavenu maticu <math>A'</math> a vektor <math>b'</math> pustime nas problem CP. Pokial CP uspeje, tak najde vektor <math>x</math> pre ktory bude platit: <math>A'x \le b'</math>.
Z toho vieme, ze <math>(\vec a * \vec x \le b) \land (- \vec a * \vec x \le -b)</math> a preto <math>\vec a * \vec x = b</math>.
Pozn. 1: Z nerovnosti sme si trivialnou fintou spravili rovnost.
Pozn. 2: Riadkovy vektor <math>\vec a</math> krat stlpcovy vektor <math>\vec x</math> je cislo <math>b</math> (resp. vektor <math>\vec b</math> o velkosti 1x1).
Rovnost <math>\vec a * \vec x = b</math> nam ale hovori, ze vektor <math>\vec x</math> zlozeny z nul a jedniciek nam vlastne vybera z mnoziny vsetkych <math>a_i</math> take prvky, aby spolu davali sucet <math>b</math>. Ostava nam teda uz iba vektor <math>x</math> previest na mnozinu indexov, ktora bude riesenim problemu SP.
----
Ine riesenie.
<math>CP \in NP</math>
Certifikat: Vektor ''x'' (zlozeny z nul a jedniciek).
<math>SAT \propto CP</math>
{{TODO|Princip bol v tom, ze sa zo vstupnej CNF formule problemu SAT vyrobili nerovnosti, ktore popisovali splnitelnost tej formule. Tie nerovnosti sa potom upravili, cim vznikla matica ''A'' a vektor ''b'', ktore sa dali pouzit v CP. Existencia riesenia a vektoru x potom znamenala, ze formula je urcite splnitelna. [[User:Jsimlo|jsimlo]] 15:19, 27 Jan 2006 (CET)}}
Necht mame instanci SAT v CNF <math>F=(x_1 \lor \neg x_2 \lor x_4) \land (\neg x_1 \lor x_3 \lor \neg x_4) \land (\neg x_2 \lor \neg x_3)</math> a necht mame BB resici 0-1CP. Potom instanci 0-1CP zkonstrujme nasledovne
<math>
\begin{cases}
x_1+(1-x_2)+x_4 \ge 1\\
(1-x_1)+x_3+(1-x_4) \ge 1\\
(1-x_2)+(1-x_3) \ge 1
\end{cases}
\rightarrow
\begin{cases}
-x_1+x_2-x_4 \le 0\\
x_1-x_3+x_4 \le 1\\
x_2+x_3 \le 1
\end{cases}
</math>
=== IP ===
:Definujme problém IP (izomorfismus podgrafů) následovně:
:<u>Instance</u>: Neorientované grafy ''G'' a ''H''
:<u>Otázka</u>: Je graf ''G'' izomorfní s nějakým podgrafem grafu ''H''? (varianta 1)
:<u>Otázka</u>: Je graf ''G'' izomorfní s nějakým indukovaným podgrafem grafu ''H''? (varianta 2)
:Dokažte, že obě varianty IP jsou NP-úplné problémy.
----
<math>IP \in NP</math>
Certifikat: zoznam dvojic vrcholov, ktore sa maju na seba zobrazit.
<math>KLIKA \propto IP</math>
Mam graf ''H'' a chcem v nom najst kliku o velkosti ''k''. Nech viem riesit problem IP. Zostrojim si graf ''G'' ako uplny graf na ''k'' vrcholoch, <math>G = K_k</math>, a hladam pomocou IP graf ''G'' v grafe ''H''. Pokial ho najdem, tak som nasiel kliku velkosti ''k'' v grafe ''H'' a teda som vyriesil problem KLIKA. Toto funguje pre obe varianty, pretoze klika je maximalny podgraf. Maximalny podgraf bude urcite indukovany, pokial bude existovat.
{{TODO|Myslim, ze by sa toho dalo napisat trochu viac o tom ze to tak naozaj je. Nejaky ten dokaz a podobne, ale to uz je trivialne. [[User:Jsimlo|jsimlo]] 15:19, 27 Jan 2006 (CET)}}
= Externí odkazy =
* [http://www.math.lsu.edu/~preprint/2002/jgo2002e.pdf Matroidy(in English)]
