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".