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

===================================  24.2.2010  ===================================

Probrány formulace následujících vět
V1. Aproximační algoritmus pro Max-E3-SAT s faktorem 7/8.
V2. Neexistence aproximačního algoritmu pro Max-E3-SAT s faktorem 7/8+eps za předpokladu P \not= NP.
V3. Formulace redukce SAT na Max-E3-SAT s mezerou v počtech splnitelných klausulí pro vstup ze SAT a z komplementu SAT.
Problém Max-E3-Lin-2, aproximační algoritmus s faktorem 1/2.
V4. Formulace redukce SAT na Max-E3-Lin-2 s mezerou v počtech splnitelných rovnic pro vstup ze SAT a z komplementu SAT.
Dokázána V1 a implikace V4 => V3 => V2.
Důkaz V4 nebude prezentován.
Pokud P \not= NP, pak pro problém kliky neexistuje aproximační algoritmus s faktorem 7/8+eps.
Příště: zesílení na neaproximovatelnost problém kliky s libovolným konstantním faktorem.

===================================  3.3.2010  ===================================

Max-Lin-2 je NP-úplný, důkaz ukazuje, jakým způsobem může Max-Lin-2 reprezentovat výrokové formule.
Vyjádření Max-Lin(L) pomocí multilineárního polynomu nad reálnými čísly pro použití metody
postupného upřesňování pro deterministický aproximační algoritmus s faktorem 1/2 (nebude zkoušeno).
Pokud P \not= NP, pak problém kliky nemá aproximační algoritmus pro žádný konstantní aproximační faktor.
Zavedení třídy PSPACE. Třídy \Sigma_k a \Pi_k, speciálně \Sigma_1=NP, jsou obsaženy v PSPACE.
Problém QBF. Rekurzivní procedura pro test pravdivosti QBF.

===================================  10.3.2010  ===================================

Převod rekurzivního testu pravdivosti QBF na Turingův stroj.
Zadána úloha sestavit algoritmus vyhodnocení konstantního Booleovského výrazu.
Polynomiální převod libovolného PSPACE jazyka na obecnou formuli typu QBF.
Zbývá převod formule na prenexní formuli, jejíž vnitřní část je CNF.

===================================  17.3.2010  ===================================

Algoritmus vyhodnocení konstantního výrokového výrazu pomocí zásobníku s hloubkou úměrnou hloubce vnoření závorek.
Příště: pro případ bez závorek stačí 3 stavy {0, 1, 1 or *}.
Připomenutí převodu vyhodnocení obvodu na problém splnitelnosti CNF s doplněnými proměnnými.
Výpočet počtu primárních implikantů vyvážené monotonní AND/OR formule. Důsledek, uvedená formule nelze
  vyjádřit pomocí DNF polynomiální velikosti. Duální funkce tedy nemá CNF polynomiální velikosti.
Vítězné a remízní strategie pro konečné hry, souvislost s vyhodnocením formule v bázi {and, or} s negacemi jen v literálech.
Příklad strategie pro hru na acyklickém grafu a odebírání z hromádek pomocí kritické množiny konfigurací.

===================================  24.3.2010  ===================================

Zmínka o modálních logikách K, T, S4, pro které je test splňování PSPACE-úplná úloha.
Pro logiku S5 je test splňování co-NP úplná úloha.
Hra na grafech, posouzení vítězné strategie pro prvního hráče v dané konfiguraci je PSPACE-úplná úloha.
Zaveden programovací jazyk pro Turingův stroj. Lze použít libovolný jazyk bez rekurze při omezení, že všechny proměnné
nabývají jen konečně mnoha hodnot, a s doplňujícími funkcemi pro operace s páskou (read, write, move).

Ke hře Kalah. Analýza je například v článku
  http://naml.us/~irving/papers/irving2000_kalah.pdf
Předpokládá se m menších jamek pro každého hráče a dvě větší jamky na kraji. Kámen je aktivní, pokud je v některé
z menších jamek. Počet konfigurací pro n aktivních kamenů je v článku vyjádřen jako
  choose(n + 2m, 2m) - 2 choose(n + m, m) + 1
což pro
  m = 6
  n = 72
dává 112992379061381 (s mezerami 112 992 379 061 381) = 1.13 * 10^14

===================================  31.3.2010  ===================================

Simulace k-TS pomocí 1-TS v čase O(t^2).
Idea důkazu simulace k-TS pomocí 2-TS v čase O(t log t).
Zmínka o konstruovatelných funkcích a větě o hierarchii.
DTIME(2^n), DTIME(2^{2^n}), DTIME(2^{2^{2^n}}), ... jsou podmnožiny množiny primitivně rekurzivních množin.
Simulace k-TS pomocí RAM.
Debata o složitosti testu prvočíselnosti.

===================================  7.4.2010  ===================================

Přednáška se nekonala.

===================================  14.4.2010  ===================================

Přednáška se nekonala.

===================================  21.4.2010  ===================================

Posloupnost hyperoperací H_n(a, b) jako alternativa k Ackermannově funkci.
PR definice 2^n, 2^{2^n}, 2^{2^{2^n}}, ...
Jestliže f je PR a L \in DTIME(f), pak charakteristická fce L je PR, bez podrobného důkazu.
Simulace RAM s bitovou složitostí b na TS v čase O(b^2) a RAM s polynomiálním omezením mezivýsledků a jednotkovou
  složitostí k v čase (k^2 log k).
Neformální zavedení uniformních a neuniformních modelů, souvislost se složitostí pro vstupy omezené velikosti a
  s pravděpodobnostními výpočty.
Příště: přesné zavedení P/poly a důkaz SAT \in P/poly => \Pi_2 = \Sigma_2.

===================================  28.4.2010  ===================================

Zavedení P/poly, ekvivalence obecným obvodům.
Self-reducibilní jazyk, verifikace obvodu pro self-reducibilní jazyk pomocí ověření rekurence.
Karp-Liptonova věta.
Důsledek, SAT pravděpodobně nelze řešit polynomiálními obvody.
Zavedení pravděpodobnostního TS, (alpha, beta)-PTS, speciální případy
  RP = (0, 1/2)-PTS, co-RP = (1/2, 1)-PTS, BPP = (1/3, 2/3)-PTS.
Příště: zesilování pravděpodobnosti správného výsledku a důkaz BPP \subset P/poly.

===================================  5.5.2010  ===================================

Zesilování pravděpodobnosti správného výsledku v BPP.
Důsledek BPP \subseteq P/poly.
Spolu s Karp-Liptonovou větou dostáváme, že SAT \in BPP implikuje, že PH by byla konečná.
Eucleidův algoritmus, rozšířený Eucleidův algoritmus pro získání x, y
splňující xa + yb = (a,b). Zavedení Z_m^*, uzavřenost na inverzi a násobení.
Eulerova funkce \phi(m) a Eulerova věta (a,m) = 1 =>  a^\phi(m) = 1 (m).
Kryptografický systémy RSA a Diffie-Hellman.