PRŮBĚH PŘEDNÁŠKY VÝPOČTOVÁ SLOŽITOST (LETNÍ SEMESTR 2013/2014)

===================================  4.3.2014  ===================================

Každá konečná hra s nulovým součtem má rovnovážnou hodnotu.
Pro nekonečné hry s konečným počtem konfigurací platí podobné tvrzení (Zermelo).
Příklad nekonečné hry s hráči N s možnými tahy {1,2,3,4,5} a A s možnými tahy {a,b,c,d,e},
  kdy hráč N vyhrává, pokud max N(x) = |A(x)|, kde N(x) a A(x) jsou množiny symbolů
  odpovídajících hráčů, které se vyskytly nekonečně krát v hře s průběhem x.
Interpretace vyhodnocení AND/OR formule jako stromu hry.
Příklad hry na grafech pro neorientovaný graf tvořený čtvercovou sítí m krát n.
Hra na obecných orientovaných grafech je PSPACE úplná.
Zadána cvičení:
  Najít vítěznou strategii pro hráče N ve výše uvedené nekonečné hře.
  Dokázat, že ve hře na neorientované čtvercové sítí m krát n vítězí první hráč právě
  tehdy, když mn je sudé.

===================================  11.3.2014  ===================================

Probráno řešení nekonečné hry z předchozí hodiny.
Připomenuta úloha s hrou na neorientovaném grafu.
Připomenutí jazyka pro programování TS.
Vzájemné polynomiální převody jedno a více páskového TS a RAM.

===================================  18.3.2014  ===================================

Zavedení neuniformního TS a důkaz jeho ekvivalence neuniformním polynomiálním obvodům.
Karp-Liptonova věta, důsledek pro problém SAT.
Zavedení pojmů pravděpodobnostní prostor, náhodný jev a náhodná veličina.
Příklady spojitých a diskrétních náhodných veličin.
Zavedení pojmu střední hodnota.

===================================  25.3.2014  ===================================

Vlastnosti střední hodnoty náhodných veličin na konečném pravděpodobnostním prostoru.
Rozptyl, směrodatná odchylka, důkaz Čebyševovy nerovnosti, bez důkazu Černovova nerovnost.
Zavedení pravděpodobnostního TS, třídy RP a BPP.
Věta o zesilování pravděpodobnosti pro třídu RP.

===================================  1.4.2014  ===================================

Zesilování pravděpodobnosti správného výsledku pro třídu BPP.
Zmínka o univerzální traverzovací posloupnosti pro neorientované grafy.
BPP \subseteq P/poly.

===================================  8.4.2014  ===================================

Zmínka o náhodné procházce v orientovaném a neorientovaném grafu.
Připomenutí důkazu BPP \subseteq P/poly.
BPP \subseteq \Sigma_2.
Věta o neaproximovatelnosti MAX-SAT a problému kliky, vynechán důkaz lemmatu
  o velikosti klik v součinovém grafu.

===================================  15.4.2014  ===================================

Důkaz lemmatu o klikách v součinu grafů.
Modely pro reprezentaci Booleovských funkcí, obvod jako lineární program.
Probrána vnoření: stromy -> DNF a CNF, DNF -> formule, CNF -> formule,
  AND/OR-formule -> rozhodovací diagramy, rozhodovací diagramy -> obvody.
Zmínka o quasipolynomiálním vnoření DNF a CNF -> stromy.

===================================  22.4.2014  ===================================

Pro libovolnou Booleovskou funkci platí dd(f) \le L(f)^2.
Zmínka, že také platí dd(f) \le L(f)^\alpha, kde \alpha=log_2(3) \approx 1.584963.
Transformace obecné formule s binárními spojkami na ekvivalentní vyváženou formuli
  v bázi {not, and, or}.
Připomenutí výsledku o nevnořitelnosti DNF do read-once rozhodovacích diagramů.
Vnořitelnost read-once rozhodovacích diagramů do formulí implikuje vnořitelnost
  obecných rozhodovacích diagramů do formulí.
Třídy Booleovských funkcí uzavřených na skládání.
Maximální neúplné třídy jsou právě T_0, T_1, M, S, L, bez důkazu.
Nalezení spojek, které tvoří jednoprvkovou úplnou bázi.
Počty funkcí daného počtu proměnných ve třídách T_0, T_1, M, S, L.

===================================  29.4.2014  ===================================

Charakterizace funkcí vyjádřitelných pouze pomocí implikace.
Spojka maj_3(x,y,z) umožňuje vyjádřit právě všechny monotonní samoduální funkce.
Monotonní funkce má jen monotonní primární implikanty.
Složitost DNF pro monotonní funkci je rovna počtu jejích primárních implikantů.
Neporovnatelnost DNF a CNF.
Dolní odhad složitosti DNF pomocí délek primárních implikantů.
Pro každou funkci n proměnných platí dnf(f) \le 2^{n-1}.
Rovnost dnf(f) = 2^{n-1} nastává pro f rovné paritě všech proměnných nebo její negaci a
  pro některé další funkce.

===================================  6.5.2014  ===================================

Barringtonova věta, viz http://en.wikipedia.org/wiki/Barrington's_theorem. K odkazu
je třeba dodat, že NC^1 jsou obvody logaritmické hloubky, což je třída obvodů, které
jsou ekvivalentní formulím polynomiální velikosti. Ve výkladu na Wikipedii lze NC^1
všude nahradit formulemi polynomiální velikosti a místo "subcircuit" rozumět "subformula".