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

==========================  7.3.2007  ==============================

Pravděpodobnostní algoritmus splňující alespoň m/2 klausulí.
Připomenutí použití multilineárních polynomů pro převod
pravděpodobnostního algoritmu na deterministický.
Pravděpodobnostní aproximační algoritmus s faktorem 3/4,
zbývá dokázat odhad pro jednotlivé klausule.

==========================  14.3.2007  ==============================

Dokončení aproximačního algoritmu pro MAX-SAT (faktor 3/4).
Transformace SAT na MAX-SAT s dokazatelnou mezerou pro počet
splněných klausulí mezi (1-eps)MAX-SAT a MAX-SAT.
Důsledek: neaproximovatelnost MAX-SAT v poly čase s faktorem 1-eps.
Důsledek: neaproximovatelnost problému kliky v poly čase
s faktorem 1-eps.
Zesílení výsledku pro kliku na libovolný konstantní faktor.

==========================  21.3.2007  ==============================

Připomínka zavedení PSPACE, NP \subseteq PSPACE, 
zmínka o \Sigma_k, \Pi_k a jejich vztahu k PSPACE.
Zavedení PSPACE-úplnosti.
Problém KBF, KBF je v PSPACE, KBF je PSPACE-úplný.

==========================  28.3.2007  ==============================

Existence vítězné nebo remízní strategie pro konečné hry.
PSPACE-úplnost hry na grafech.
Zavedení Blumových axiomů pro složitost.
Věta o zrychlení bez důkazu. Důsledek: složitost nelze definovat
jako složitost nejefektivnějšího algoritmu pro danou úlohu.
Věta o dírách s důkazem. Důsledek: ne každá funkce je vhodnou
mírou složitosti.
Zavedení funkcí konstruovatelných v čase a v prostoru.
Charakterizace pomocí vyčíslitelnosti v omezené složitosti.
Prostor a čas pro počítání po jedné nahoru a dolů.

==========================  4.4.2007  ==============================

Postačující podmínka na konstruovatelnost pomocí vyčíslitelnosti
ve dvojkové soustavě. Numerický postup výpočtu odmocniny a logaritmu.
Věta o prostorové hierarchii.
Simulace vícepáskového TS pomocí dvoupáskového (bez důkazu).

==========================  11.4.2007  ==============================

Přednáška se nekonala.

==========================  18.4.2007  ==============================

Věta o časové hierarchii.

Booleovské funkce, Booleovská krychle, podkrychle,
částečný vstup, monom, vztahy mezi nimi.
Počty ohodnocení proměnných v jednotlivých vrstvách Booleovské krychle.
Duální funkce.
Monotonní, samoduální, lineární funkce.
Funkce je lineární právě když každá její restrikce na dvě
proměnné je lineární.
Funkce typu T_0, T_1.
Charakterizace úplných bází (byla dokázána charakterizace
lineárních spojek pomocí jejích restrikcí na dvě proměnné, což
umožňuje formulovat přehlednější důkaz věty než je ve skriptech).

==========================  25.4.2007  ==============================

Mintermy. Funkce je disjunkcí svých mintermů. Příklad funkce
se dvěma minimálními DNF. Monotonní funkce má monotonní mintermy.
Zavedeny modely a jim příslušné míry velikosti reprezentace:
- obvody, formule, DNF, CNF (založené na kombinování Booleovských
  hodnot spojkami)
- rozhodovací diagramy, read-once rozhodovací diagramy, stromy
  (založené na větvení výpočtu na základě hodnot jednotlivých proměnných).
Horní odhady velikosti reprezentace:
strom 2^n (přesná hodnota)
DNF   2^{n-1} (přesná hodnota)
formule O(2^n) (lze snížit až na (1+o(1))2^n/log n, ale ne více)
obvody O(2^n/n) (přesnější hodnota je (1+o(1))2^n/n)
Pro obvody zbývá dopočítat šířku největší hladiny
s využitím řešení rovnice k = log(n-k).

==========================  2.5.2007  ==============================

Dokončení obvodů velikosti O(2^/n) pro libovolnou funkci n proměnných.
Spojka sel dává úplnou bázi buď s negací nebo s oběma konstantami.
Zavedení size_M(f) a speciálně dnf(f), cnf(f), dt(f), dd(f), 1-dd(f),
a také C(f) pro obvody a L(f) pro formule.
Zavedení Poly(M) pro model M.
Byly dokázány inkluze
  Poly(dnf) obsahuje Poly(dt)   (větve končící 1)
  Poly(cnf) obsahuje Poly(dt)   (větve končící 0)
  Poly(1-dd) obsahuje Poly(dt)  (speciální případ)
  Poly(dd) obsahuje Poly(1-dd)   (speciální případ)
  Poly(formule) obsahuje Poly(dnf)   (speciální případ, složitost se nejvýše vynásobí n)
  Poly(formule) obsahuje Poly(cnf)   (speciální případ, složitost se nejvýše vynásobí n)
  Poly(obvody) obsahuje Poly(dd)  (přepis rozhodovacího diagramu pomocí spojky sel)
Jako příklad opačného výsledku ukázáno, že
  Poly(dnf) neobsahuje Poly(1-dd) (dnf pro paritu má 2^{n-1} monomů, read-once diagram je O(n)).

==========================  9.5.2007  ==============================

Transformace formule v bázi {and,or,not} na rozhodovací diagram.
Formule v bázi {and,or,not} velikosti O(n^2) pro paritu.
Zobecnění dolního odhadu složitosti dnf pro paritu na obecné
funkce v závislosti na jejich supportu a délce mintermů.
Složitost dnf pro monotonní funkci.
Složitost dnf, cnf a stromů pro funkce equality_n, equality_n^*
a free-cnf, free-dnf. Oddělení dnf od cnf a stromů, oddělení
cnf od dnf a stromů.
Konečné projektivní geometrie a definice Booleovské funkce
s jejich využitím.

==========================  16.5.2007  ==============================

Přednáška se nekonala.