{{predmet|Složitost I|Ondřej Čepek|TIN062}}
* [http://ktiml.mff.cuni.cz/vyuka/materialy.html Oficiálne materiály KTIML on-line]
* [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)
= 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 podprocedůru? 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ť S1, S2, ..., Sn je rozdělení množiny S na po dvou disjunktní podmnožiny. Nechť I = {A | i |A Si| 1}. Dokažte, že (S,I) je matroid.
----
{{TODO|}}
=== 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', \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 ==
{{TODO|}}
== Cvičení 4 ==
{{TODO|}}
== 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?
----
*a) Nevie sa.
*b) Ano. Certifikatom 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)}}
=== 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)]
