Tento souhrn slouží pro přípravu k magisterským státnicím pro obory Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika a Státnice%20-%20Informatika%20-%20I4:%20Diskrétní%20modely%20a%20algoritmy. Detailní informace o předmětu hledej na stránkách Složitost I a Složitost II.
Rozsah látky
Seznam oficiálních státnicových otázek pro studijní obory Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika a Státnice%20-%20Informatika%20-%20I4:%20Diskrétní%20modely%20a%20algoritmy (aktualizováno 2013):
:: Věty o hierarchii tříd složitosti, konstruovatelné funkce, vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem, Savitchova věta. Úplné problémy pro různé třídy (NP, PSPACE, P, #P). Polynomiální hierarchie, pseudopolynomiální algoritmy, silná NP-úplnost, třída #P a #P-úplnost. Aproximační algoritmy a schémata. Metody tvorby algoritmů: dynamické programování, hladový algoritmus na matroidu. Základy pravděpodobnostních algoritmů.
Studijní obory Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy a Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika mají okruhy Složitost a Vyčíslitelnost do spojeny do jednoho a rozsah otázek pro složitost se liší.
Zdroje obecně
Většina je pokryta přednáškami Složitost I a II, některá témata je však třeba dohledat jinde (klidně po internetu, na wikipedii, v Majerechovi, v zahraničních skriptech...). Pozor, Čepkovy slajdy jsou více než stručné.
Vřele doporučuji strávit jedno odpoledne v knihovně s knížkou od Arory a Baraka Computational Complexity: A Modern Approach. Velmi názorně pomůže získat dobrou intuici u téměř všech okruhů a rigorózní důkazy se tam člověk venkoncem také dočte.
Věty o zrychlení a o mezerách
Věta o lineárním zrychlení
:see Složitost II#Věta o lineárním zrychlení (asi i wen:Linear%20speedup%20theorem)
DTS s alespoň dvěma páskami se na vstupu délky n dá zrychlit z t kroků na ()
postup: nový stroj stlačí r políček původní pásky na jedno -- nejdřív okopíruje a přejede na začátek ( kroků), pak simuluje v šesti krocích r kroků původního stroje: nejdřív načte tři svoje políčka (3r políček původního stroje; trvá 4 kroky nového [vlevo,vpravo,vpravo,vlevo]), pak zjistí, jak budou vypadat po r krocích (jen ve vnitřním stavu), a nakonec to zapíše (další max 2 kroky, za r kroků starého se stihnou změnit nejvýše dvě políčka nového stroje)
Je-li L jazyk přijímaný k-páskovým DTS M (k>=2) a s časovou složitostí . Potom pro každé kladné c existuje k-páskový M' s časovou složitostí c*t(n) přijímající L.
Vezmeme r > 12/c, uděláme M' jako výše, doba jeho běhu nad vstupem délky n se dá pro r>2 shora odhadnout výrazem (c/2)*t(n)+(6/r)t(n) (z ), což z r>12/c dává omezení doby běhu ct(n) pro skoro všechna n. Konečný počet výjimek se ošetří konečným automatem.
Nechť je L jazyk přijímaný k-páskovým DTS M s časovou složitostí t(n) = c*n. Dále ať k>=2 a c>1. Pak existuje k-páskový DTS M' s časovou složitostí přijímající L.
If time is money you've made me a wealtiehr woman.
Věty o hierarchii tříd složitosti
:see Složitost II#Základní třídy složitosti, wen:Complexity%20class, http://blog.computationalcomplexity.org/2004/07/time-and-space-hierarchies.html
Otevřenost časové hierarchie shora
Nechť T je rekurzivní funkce (tj. existuje TS, který ji vyčísluje). Potom existuje rekurzivní jazyk L takový, že .
Důkaz přes jazyk
ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 18: …= \{ x_i : M_i \̲m̲b̲o̲x̲{ nepřijímá } x…
, (máme očíslované řetězce i Turingovy stroje). Přítomnost v L se dá otestovat pomocí TS co si odsimuluje T(|x|) kroků příslušného stroje, L je tedy rekurzivní.Pokud by platilo , tak by existoval TS M, který rozpozná L v čase T(n). Ten stroj má nějaké číslo i. (Tj. .). Pak platí jedno z:
, tj. stroj M přijme v čase (protože ho poznává). Zároveň ale z stroj v čase nepřijímá (z definice L). Máme spor, protože M a je ten samý.
, takže ho M (rozpoznávač L) v daném čase nepřijme, ale (ten z definice L) ho v daném čase přijmout musí, tj. taky spor.
:(tj. vyzkoušíme, co řekne na jemu příslušející řetězec )
Proto .
Otevřenost prostorové hierarchie shora
Nechť S je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že .
Důkaz je analogický jako u časové hierarchie, vyrobí se jazyk
ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 18: …= \{ x_i : M_i \̲m̲b̲o̲x̲{ nepřijímá } x…
. Rozdíl je jen v simulaci , který se navíc může na svém omezeném prostoru zacyklit, což se ale dá detekovat, neb tam má omezený počet konfigurací.Věty o časové a prostorové hierarchii
O prostorové hierarchii
Nechť a jsou funkce takové, že , je prostorově konstruovatelná a . Potom existuje jazyk L takový, že .
To s omegou znamená že není omezená (ani když se přenásobí libovolnou konstantou), celá pointa věty je, že v takto větším prostoru se dají poznat nějaké další jazyky.
Důkaz
We show the existence of a language L such that but . We define L by describing a Turing machine ML, using space , that decides it. ML does
the following on input w = (M, y) of length :
Run M(w) with at most space and for at most steps (these bounds are imposed on M), using space at most .
If M(w) accepts within the given time and space bounds, then reject. Otherwise, accept.
In step 1, we can use the fact that is space constructible to mark off exactly tape cells for M to use.
We can similarly mark off an additional cells to use as a counter for checking the number of steps M makes, and one last set of cells to use for any remaining computation. By
construction, ML uses space .
We need to show that no machine using space can decide L. Assume the contrary. Then there exists a machine deciding L and using space .
Choose k large enough so that , so that makes fewer than steps on inputs of length k, and
so that the simulation of on inputs of length k can be performed in space. Consider the input .
If we run then (1) has enough time and space to simulate the entire execution of , and thus (2) outputs the opposite of whatever outputs. We conclude that and do not decide the same language.
O časové hierarchii
Nechť a jsou funkce takové, že a je časově konstruovatelná. Potom existuje jazyk L takový, že .
Konstruovatelné funkce
:see also Složitost II
Funkce je rekurzivní pokud existuje DTS M takový, že pro vstup 1<sup>n</sup> vydá výstup 1<sup>f(n)</sup>.
Funkce je vyčíslitelná v čase O(f) pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS udělá nejvýše cf(n) kroků než vydá 1<sup>f(n)</sup>.
Funkce je vyčíslitelná v prostoru O(f) pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS použije při práci prostor nejvýše cf(n).
Funkce je časově konstruovatelná pokud existuje DTS M takový, že pro každý vstup délky n zastaví po právě f(n) krocích (předpokládáme, že f(n) ≥ n + 1[^1]{: note-class="footnote"}).
Funkce je prostorově konstruovatelná pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.
Lemma: Nechť a jsou časově konstruovatelné funkce, dále nechť takové, že . Pak je časově konstruovatelná.
:: Podobně jako v důkazu věty o lineárním zrychlení zrychlíme výpočet trvající kroků, aby trval přesně kroků...
Věta: Nechť , taková, že existuje a , že . Pak je f časově konstruovatelná právě tehdy, když je vyčíslitelná v čase O(f).
:Je-li f časově konstruovatelná, pak máme stroj který běží v čase f(n). Můžeme mu přidat pásku, na kterou bude psát po dobu svého běhu jedničky, čímž f vyčíslí. :Naopak, označíme-li g(n) přesný čas stroje M, který funkci f počítá v čase O(f(n)). (Tedy g(n) < c*f(n) pro skoro všechna n a nějaké c.) Potom g je časem TS M, f + g je časem TS, který "po dopočítání M ještě spočítá počet jedniček na pásce". Funkce g je časově konstruovatelná díky stroji M. Z toho (a z lemmatu výše) plyne časová konstruovatelnost f.
Věta: Funkce f je prostorově konstruovatelná právě tehdy, když je vyčíslitelná v prostoru O(f).
:Doprava nám stačí upravit stroj který f prostorově konstruuje tak, aby při zabrání nového políčka zapsal na novou pásku jedničku. :Nechť M je k-páskový deterministický Turingův stroj vyčíslující f(n) v prostoru cf(n). Podle věty o lineární kompresi zkonstruujeme k-páskový stroj M', který vyčísluje f(n) v prostoru přesně f(n). Uvědomte si, že M' vyčísluje f(n), tedy musí pracovat v prostoru alespoň f(n). Stroj M' dále převedeme podle věty o redukci počtu pásek na jednopáskový stroj M, který již dokazuje prostorovou konstruovatelnost funkce f.*
Věta o lineární prostorové kompresi ::
:Je-li L jazyk přijímaný k-páskovým DTS M v prostoru S(n), pak pro každé přirozené číslo r existuje k-páskový DTS M', který přijímá L v prostoru
Věta o redukci počtu pásek pro prostorovou složitost ::
:Je-li L jazyk příjímaný k-páskovým DTS M v prostoru S(n), pak existuje jednopáskový DTS M', který přijímá L v prostoru S(n).
Důsledek: Každá časově konstruovatelná funkce je také prostorově konstruovatelná.
:: Funkce f je časově konstruovatelná, tedy je vyčíslitelná v čase O(f), tím spíše je vyčíslitelná v prostoru O(f) a z věty výše je tedy i prostorově konstruovatelná.
Vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem
DSPACE(S(n)), DTIME(T(n)), NSPACE(S(n)), NTIME(S(n)) -- třídy jazyků (ne)deterministické časové/prostorové složitosti T(n)/S(n).
Triviální vztahy
, kde XXX je něco z [DN](SPACE|TIME)
Věta o vztazích mezi třídami složitosti
<br/>
triviálně platí
z vět o lineární kompresi a redukci počtu pásek
(IMHO si stačí uvědomit, že prostor je vždy omezen spotřebovaným časem)
postupně generujeme f(n)-tice možných průchodů (v každém kroku max r možností, r=max|{přechodová funkce}|) jako graf průchodu výpočtem a výpočet simulujeme DTS podle toho -- simulace potřebuje DSPACE(f(n)) (třeba podle předchozího bodu), uloženi f(n)-tice potřebuje místa, tj. taky DSPACE(f(n)), a tenhle prostor se dá použivat pro jednotlivé simulace stejný. Celkem tedy .
a , pak , kde C<sub>L</sub> je konstanta závislá na jazyku L
Nechť M je jednopáskový stroj poznávající L v prostoru f(n). Počet jeho konfigurací je omezen , pro vhodné ( je počet stavů, je počet páskových symbolů, člen (n+1) asi? pro pozici hlavy na vstupní pásce).
#*Zkonstruujeme M', který simuluje M a nejvýše po krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
a , pak , kde C<sub>L</sub> je konstanta závislá na jazyku L
Počet konfigurací opět omezen nějakým . Vygenerujeme graf, vrcholy=stavy (tj. omezené), hrana=přechod jedním krokem (konstanta*|stavy|, protože přechodová funkce je konečná). Pak se graf projde a zjistí, jestli tam je přijímací výpočet.
, pak , kde C<sub>L</sub> je konstanta závislá na jazyku L
Nechť M je k-páskový NTS, který poznává L v čase f(n). Počet jeho konfigurací je omezen pro vhodné ( je počet stavů, páskových symbolů).
Zkontruujeme DTS M', který vygeneruje seznam všech konfigurací dosažitelných z počáteční konfigurace, což lze provést v kradratickém čase vzhledem k délce výsledného seznamu. Tato délka je omezena součinem počtu konfigurací a délky zápisu jedné konfigurace. Tedy . M' je pak schopný poznat jestli je dosažitelná nějaká přijímající konfigurace, počet jeho kroků je omezen .
Savitchova věta
:see wen:Savitch's%20theorem
Nechť je prostorově konstruovatelná funkce taková, že . Potom .
:Pokud NTS M přijímá jazyk L v prostoru S(n), pak existuje konstanta taková, že M má nejvýše konfigurací. Počet kroků přijímajícího výpočtu pak bude nanejvýš . :Pak definujeme proceduru , která zkoumá, jestli se ze stavu dá přejít do stavu za maximálně kroků. (Dělá to rekurzivně -- pro i=0 ověří jestli jsou stavy shodné nebo existují přímý přechod a vrátí výsledek, jinak pro každý stav pouští a a zkoumá jejich výsledek.)
:Jedna kopie procedury TEST si musí pamatovat tři konfigurace (jedna konfigurace potřebuje stav, pozici vstupní a výstupní hlavy, a obsah pracovní pásky, to vše O(S(n)) a parametr i (ten se taky vejde do O(S(n)), viz max počet kroků výpočtu). :Simulace probíhá tak, že pro všechny přijímací stavy voláme proceduru ( je počáteční konfigurace) a pokud aspoň jednou odpoví true, vstup přijmeme.
:Pracovní páska pak funguje jako zásobník parametrů procedury TEST, která se zahloubí nanejvýš O(S(n)), takže se celý výpočet vejde do prostoru
Úplné problémy pro třídy NP, PSPACE
:see wen:NP-complete, wen:PSPACE-complete
Def: Problém A je T-těžký, kde T je třída, vzhledem k k-převoditelnosti, pokud .
Def: Problém A je T-úplný, kde T je třída, vzhledem k k-převoditelnosti, pokud je T-těžký a navíc .
Převoditelnosti pro různé třídy:
NP - poly time převoditelnost
P - log space převoditelnost
PSPACE - poly time převoditelnost
Úplné problémy pro různé třídy:
NP: Kachličky, SAT; 3-SAT, 3-Color, Klika, NM, VP; VP, HK, TSP; VP, SP
P: SAT na Hornovských klauzulích, Vyhodnocení obvodu booleovských hradel (CVP)
PSPACE: SAT na kvantifikovaných klauzulích (QBF-SAT) - splnitelnost SAT kde proměnné můžou být kvantifikované i univerzálním kvantifikátorem (důkaz podobný důkazu Savichovy věty)
dále typicky hry (zoběcněný wen:%20Hex%20%28board%20game%29)
Důkazy různých NP-C
Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve studnici).
Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je zde. Původně je věta formulována pro problém SAT, ale snazší důkaz je pro KACHL a potom ukázat, že KACHL < SAT.
Důkaz KACHL < SAT je také v Majerechových skriptách.
SAT < 3-SAT
:: Za každou klauzuli s jiným počtem literálů než 3 dáme množinu klauzulí, která dává ekvivalentní podformuli. Vezměme klauzuli c<sub>i</sub>: 1. , pak $
c_i' := (x \vee y_1 \vee y_2) \wedge (x \vee y_1 \vee \bar y_2)
\wedge (x \vee \bar y_1 \vee y_2) \wedge (x \vee \bar y_1 \vee \bar y_2)
$
, pak $
c_i' := (x_1 \vee x_2 \vee y) \wedge (x_1 \vee x_2 \vee \bar y)
$
pro , pak $
c_i' := (x_1 \vee x_2 \vee y_1) \wedge (\bar y_1 \vee x_3 \vee y_2) \wedge \dotsb
\wedge (\bar y_{i-2} \vee x_i \vee y_{i-1}) \wedge \dotsb \wedge (\bar y_{k-3} \vee x_{k-1} \vee x_k)
$
SAT < Klika
:: Graf nad všemi literály formule (opakované literály se budou opakovat i v grafu), hrana mezi každými dvěma literály z různých klauzulí, pokud s nejedná o vzájemnou negaci (x a -x). Hledáme kliku o velikosti jako je počet klauzulí, ta pak pro každou klauzuli určuje splňující literál.
Klika < NM
:: Nezávislé množiny odpovídají právě klikám v komplementárním grafu.
NM < VP
:: Doplňky vrcholových pokrytí odpovídají právě nezávislým množinám. Důkaz snadno sporem, hrana porušující nezávislost není v doplňku pokryta a naopak.
Početní úlohy, #P a #P-úplnost
Def: Funkce f patří do třídy #P pokud existuje binární relace v NPF a platí . f je početní úloha asociovaná s problémem R, píšeme taky #R (např #SAT).
Věta: Každý problém má relaci , pro kterou platí, že - Relace (x,y) y jsou polynomiálně velké certifikáty pro .
Tohle nám dává souvislost #P s NP. Intuitivně bude platit, že NP-úplné problémy budou #P-úplné. Na druhou stranu v #P musí intuitivně být těžké problémy, jejichž rozhodovací problém těžký není. Počítat řešení musí být jistě alespoň tak těžké, jako najít libovolné.
Další věty/vlastnosti:
lze spočítat polynomiálním počtem dotazů na relaci - certifikát je polynomiálně omezený vstupem, tak generuju certifikáty a ptám se relace
f(x) je v polynomiálním prostoru vzhledem k |x| - počet certifikátů je omezený takže k binárnímu zápisu nám max stačí p(|x|) bitů
Def: Převoditelnost v #P: Trochu složitější než klasická, protože nepřevádíme jen vstup, ale i výsledek. když existují v P takové, že .
Pak #P-těžkost téhle převoditelnosti. P-úplnost můžeme definovat ale i pomocí polynomiální převoditelnosti relace A z definice # problému. A tohle je docela důležité pro důkazy převoditelnosti, protože nám to dává souvislost s převody uvnitř NP.
Věta: Pokud máme relaci A v NPF-těžkou (každá relace v NPF lze na A převést), tak problém #A je #P-úplný.
Pozn. NPF-převoditelnost je polynomiální převoditelnost se zachováním řešení: , existuje v P tak, že
#P-úplný problém: #SAT je #P-úplný - jasné, když dostaneme nějaký problém v #P, tak relaci s ním asociovanou umíme převést na SAT (protože SAT je NP-úplný).
Zajímavější problém je: #DNF-SAT je #P-úplný - to nám ukazuje to, že
Důkaz: DNF-SAT je v PF, takže #DNF-SAT určitě v #P. Když převedeme #SAT na #DNF-SAT tak budeme hotovi (protože #SAT je #P-úplný). Zjevně pro vstup na n proměnných platí: a negaci umíme spočítat polynomiálně pomocí de-morganových pravidel. Funkce a funkce .
Polynomiální hierarchie
:see polynomiální hierarchie, wen:Polynomial%20hierarchy, Pekne a jednoduche vysvetleni - souvislost s TQBF a PSPACE, alternujici kvantifikatory. :Dobre je si vygooglit v obrazcich heslo polynomial time hierarchy.
Def: TS s orákulem A (jazyk) je TS co má navíc pásku, pomocí které může 'zavolat' orákulum pro . Jazyk slov pro TS M s orákulem A je L(M,A).
Def: Turingovská převoditelnost (pomocí orákula): A je det. turingovsky převoditelný na B pokud existuje DTS M s orákulem B pro nějž A=L(M,B). Značíme . Obdobně nedet. turingovská převoditelnost . Například, každý jazyk A v P je tur. převoditelný na prázdný jazyk (na to, jestli je nepotřebujeme nic než klasický TS z P).
Def: Teď můžeme definovat tzv. Relativizované třídy:
- všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí orákula jazyka A, např
- všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např
- všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí orákula jazyka A, např
- všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např
Pozn: zjevně tyhle třídy můžeme rekurzivně volat samy na sebe P(NP(P)), NP(NP(NP)) apod
Pozn: NP(NP)=? ... nevime! (nemuzem pouzit postup jako u P(P), vypocet simulace nema jednu vetev).
Pro každou množinu jazyků platí .
**Def:**Polynomiální hierarchie - Třídy definované následovně:
kde coNP je definované klasicky množinově na jazycích
Zde je dobré vědět nějaké vztahy mezi jednotlivými třídami. Viz obrázek na anglické wikipedii.
Věta: .
PH je v PSPACE
Věta ::
Dokazuje se indukcí podle i
i = 0;
předpokládáme, že tvrzení platí pro i (IP), chceme ukázat, že :: :: * -- co poznám v NP, poznám v i PSPACE, a orákulum mám stejné :: :: místo orákula může stroj kolikrát chce pouštět DTS, co si bude vedle psát ve svém polynomiálním prostoru
Věta: O kolapsu PH - Pokud P=NP, tak PH=P
{{TODO|Další vzájemné vztahy, alternující kvatifikátory, kolaps PH}}
Pseudopolynomiální algoritmy
:see wen:Pseudo-polynomial%20time
Nechť je dán rozhodovací problém (úloha, jejímž výstupem je ANO/NE) π a jeho instance I. Def:
**kód(I) .. délka zápisu I v nějakém kódování (např. binárním) **max(I) .. velikost největšího čísla v I (ne jeho kódu)
Alg. řešící π se nazývá pseudopolynomiální, pokud je jeho čas. slož. omezena polynomem v proměnných kód(I) a max(I).
Pokud je π tž. forall I: max(I)≤p(kód(I)) potom pseudopolynomiální=polynomiální
Problémy, pro které obě skupiny nesplývají se nazývají číselné. tj. neexistuje polynom p tž. viz výš
Ne však každý číselný problém lze řešit pseudopolynomiálně (tzv. silně NP-uplné problémy)
π<sub>p</sub> omezení na podproblém π tž. platí max(I)≤p(kód(I)). Pokud π<sub>p</sub> NPÚ, tak π S-NPÚ
Klika, TSP je S-NPÚ
{{TODO|S-NPÚ patří do tohoto požadavku taky!}}
Dolní odhady pro uspořádání (rozhodovací stromy)
:podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf
popsano v otazkach k Datovym strukturam: St%C3%A1tnice_-Informatika-Datov%C3%A9_struktury#Doln.C3.AD_odhady_pro_uspo.C5.99.C3.A1d.C3.A1n.C3.AD.28rozhodovac.C3.AD_stromy.29
Aproximační algoritmy a schémata
Pozri tiež Státnice - Aproximační algoritmy a schémata
:see wen:Approximation%20algorithm, kus na straně 12 z http://urtax.ms.mff.cuni.cz/%7Enovap2am/poznamky/slozitost.sxw
*Předpoklady: Každé řešení má nezápornou hodnotu.
Značení: velikost zadání, C hodnota optimálního řešení, C hodnota aproximovaného řešení
Definice
***Poměrová chyba**:
***Relativní chyba**: **Pozn.: Pokud jsou konstanty, tak se obyčejně parametr vynechává.
*Aproximační schéma (AS) pro optimalizační úlohu je aproximační alg., který pro vstup délky a číslo najde řešení s relativní chybou . Může být exponenciální vzhledem k i .
*Polynomiální AS: AS, které je polynomiální vzhledem k .
*Úplně Polynomiální AS (ÚPAS): PAS, které je polynomiální i k .
Well done article that. I'll make sure to use it wisley.
Příklady
Vrcholové pokrytí
*ρ=2.
Stačí v cyklu: Vždy vzít ze zbylých hran jednu. Oba její vrcholy přidat do pokrytí a odstranit ostatní incidentní hrany.
:DK:
Ať je F množina všech hran vybraných během algoritmu a C nalezené pokrytí. Platí: |C|=2*|F| (každá hrana má 2 vrcholy) a navíc |F|≤|C*| (optimální řešení musí pokrýt i hrany z F).
:|C|=2*|F| a |F|≤|C*| potom |C|≤2*|C*|
ÚPAS pro součet podmnožiny
*Je dána konečná podmnožina množ. přirozených čísel A s prvky x<sub>i</sub>, hodnota součtu t a aproximační parametr 0<ε<1.
*Součet L+x označuje seznam vzniklý ze seznamu L přičtením hodnoty x ke všem jeho položkám. Zachovává uspořádání.
*Prořezat seznam L s parametrem δ znamená, že pro každý odstraněný prvek y existuje v prořezaném seznamu L'
prvek z splňující:
(1-δ)y ≤ z ≤ y. Zachovává uspořádání.
*Algoritmus řešení: APPROX_SP(A,t,ε):
Metody tvorby algoritmů
Dynamické programování
Hladový algoritmus
Základy pravděpodobnostních algoritmů
Zmatení pojmů
::
Pravdepodobnostní Turingův stroj (PTS) - definice
RP, co-RP
BPP
BPP a BPTIME
RP, coRP, ZPP
Materiály
[^1]: Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach [draft January 2007]. Remark 1.5, page 1.7 (17).