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

===================================  22.2.2012  ===================================

PSPACE je sjednocení DSPACE(n^k) pro k \ge 1.
NP \subset PSPACE.
Kódování dvojic pomocí závorek tak, že slovo lze jednoznačně dekódovat i při hierarchickém vnoření dvojic do sebe.
Zavedení PH pomocí operátorů \exists, \forall na jazycích a třídách s exponentem p (konkrétní polynom) a P (libovolný
    polynom s racionálními koeficienty).
Operátory zachovávají příslušnost do PSPACE (přidají další polynomiální kus potřebného prostoru), tedy
    PH \subseteq PSPACE.
Polynomiálnost složitosti komplementu nezávisí na tom, zda uvažujeme komplement do všech slov nebo jen do jazyka
    správně utvořených kódů dvojic.
De Morganova pravidla pro \exists^p, \forall^p, \exists^P, \forall^P.
Stromový výpočet pro vyhodnocení kvantifikované formule.
Formule s fixovanými délkami slov x_i v kvantifikátorech, nedokončeno.
Kvantifikované Booleovské formule, QBF je množina pravdivých kvantifikovaných formulí v prenexním tvaru.
QBF lze rozhodnout v PSPACE.
Příprava pomocných funkcí pro simulaci PSPACE v QBF, test znaku, kvadratická formule charakterizující právě
    jednu jedničku ve vstupu, použití pro test konfigurace.

===================================  29.2.2012  ===================================

Přednáška se nekonala.

===================================  7.3.2012  ===================================

Důkaz tvrzení, že \Sigma_k, \Pi_k jsou obsaženy v PSPACE, indukcí přes k.
Rekurzivní procedura pro QBF a její realizace na TS.
Odhad počtu konfigurací TS v prostoru l jako 2^(c_1 + c_2 l).
Predikát Cesta_{l, s}(alpha, beta) a jeho vyjádření formulí složitosti O(l^2s).
QBF je PSPACE-úplný problém s využitím předchozí formule.
Konečná hra má vždy optimální strategii pro každého z hráčů.
Příklad strategie pro hru Nim.
Zavedení hry na grafech a důkaz její PSPACE-úplnosti.

===================================  14.3.2012  ===================================

Programovací jazyk pro TS.
Simulace vícepáskového TS pomocí jednopáskového TS v čase O(t^2).
Přibližně simulace vícepáskového TS pomocí dvoupáskového TS v čase O(t log t).
Simulace TS pomocí RAM s jednotkovou složitostí O(t) a bitovou O(t log t).
Simulace RAM pomocí TS se čtyřmi páskami, nedokončeno.

Cvičení. P = NP je ekvivalentní tomu, že pro každou f(x) vyčíslitelnou v poly
čase, pro kterou platí |f(x)| = |x|, existuje g(y) vyčíslitelná v polynomiálním
čase taková, že pro libovolné x platí f(g(f(x))) = f(x).

===================================  21.3.2012  ===================================

Dokončení simulace RAM na TS.
Neuniformní TS, poly-obvody = P/poly.
Karp-Liptonova věta.
(alpha, beta)-PTS, RP, co-RP, BPP.

===================================  28.3.2012  ===================================

Zmínka o simulovaném žíhání.
Miller-Rabinův test prvočíselnosti bez důkazu jako příklad pravděpodobnostního algoritmu.
Odvození Černovovy nerovnosti s mezí (p/q)^q ((1-p)/(1-q))^(1-q) \le exp( -2(p-q)^2).
Zesilování pravděpodobnosti správného výsledku pro BPP.

===================================  4.4.2012  ===================================

BPP \subseteq P/poly.
BPP \subseteq \Sigma_2 \cap \Pi_2.
Poznámka: 2^2 = -1 (mod 5), 6^2 = -1 (mod 37). Přesto pro liché n nikdy nenastane a^(n-1) = -1 (mod n).
Ekvivalentní formulace P=NP pomocí inverze funkcí ve smylu f(g(f(x))) = f(x).

===================================  11.4.2012  ===================================

Pro Max-E3-SAT existuje jednoduchý deterministický aproximační algoritmus s faktorem 7/8.
Pro jednoduchost formulací budeme předpokládat P \not= NP a eps > 0.
Aproximační faktor pro polynomiální algoritmus pro Max-E3-SAT a Max-SAT nemůže být 7/8 + eps.
Formulace základní PCP věty v terminologii verifikátorů a v terminologii redukce SAT na Max-SAT
  se zaručenou separací (1-eps, 1).
Důsledek, existuje kladné eps tak, že Max-SAT nemá polynomiální aproximační algoritmus s faktorem 1 - eps.
Úloha Max-E3-Lin-2, věta o redukci SAT na Max-E3-Lin-2 se separací (1/2+eps, 1-eps).
Jako důsledek dostaneme redukci SAT na Max-E3-SAT se separací (7/8+eps, 1-eps).
Důsledek je věta o neaproximovatelnosti Max-SAT s faktorem 7/8 + eps formulovaná výše.

===================================  18.4.2012  ===================================

Připomenutí PCP verifikátoru, ekvivalence definice s a bez omezení délky důkazu, formulace
  pomocí soundness a completeness parametrů.
Neaproximovatelnost pro problém kliky.
Analýza hill-climbing pro CNF formuli se dvěma lokálními extrémy.
Deterministický postup splnění alespoň tolika klausulí, jako náhodné ohodnocení.
Redukce 3-SAT na Max-E3-Lin-2.

===================================  25.4.2012  ===================================

Věta o pravděpodobnostním testování linearity Booleovské funkce, jestliže
Pr(f(x_1) + f(x_2) = f(x_1 + x_2)) \ge 1 - delta, pak existuje indexová
množina I tak, že Hamming(f, parita_I)/2^n \le delta. Důkaz příště.
Konstrukce (poly, const)-PCP verifikátoru pro existenci řešení soustavy kvadratických
rovnic nad Z_2 s využitím testování linearity.

===================================  2.5.2012  ===================================

Přednáška se nekonala.

===================================  9.5.2012  ===================================

Zavedení reprezentace Booleovských funkcí pomocí polynomů při kódování FALSE = 1, TRUE = -1.
Součiny proměnných značíme z_I pro I \subset {1, ..., n}, koeficient u z_I jako a_I a
parita_I(x) je součet proměnných s indexy v I modulo 2 v kódování FALSE = 0, TRUE = 1.
Pak platí
  \sum_I a_I^2 = 1
  a_I = 1 - 2 Hamming(f, parita_I)/2^n
Jestliže pro náhodné {0,1}-vektory x_1, x_2 je
  Pr(f(x_1) + f(x_2) = f(x_1 + x_2)) = p
pak pro náhodné {1, -1}-vektory z_1, z_2 je
  E(f^*(z_1) f^*(z_2) f^*(z_1 z_2)) = 2 p - 1
a dále
  2 p - 1 = \sum_I a_I^3
Dokončení důkazu příště.

===================================  16.5.2012  ===================================

Dokončení důkazu věty o testování linearity Booleovské funkce.
Měření složitosti DNF, CNF a rozhodovacích stromů, dnf(f), cnf(f), dt(f).
Implikant, primární implikant, podkrychle, částečný vstup.
Pro každou funkci existuje minimální DNF jen z primárních implikantů. Každá funkce je disjunkcí svých
primárních implikantů.
Monotonní funkce má jen monotonní implikanty, minimální DNF z primárních implikantů pro monotonní funkci
obsahuje všechny primární implikanty.
Důsledek, pro monotonní f je dnf(f) rovno počtu primárních implikantů f.
Dolní odhad dnf(f) pro funkce s primárními implikanty délky alespoň k.
Převod složitosti DNF a CNF pomocí negace a duální funkce.
Složitost funkcí free-dnf, free-cnf, parita, equality.
Důsledek, DNF a CNF jsou neporovnatelné z hlediska jejich vyjadřovací síly.
dt(f) \ge dnf(f) + cnf(f).
Důsledek, rozhodovací stromy jsou slabší model než DNF i CNF.
Přesný výpočet dt(T^n_k) pro prahovou funkci T^n_k = I(sum_i x_i \ge k).