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

==========================  7.10.2008  ==============================

Úlohy s dokazatelně dvojitě exponenciální složitostí.
 - Presburgerova aritmetika,
 - aritmetika reálných čísel.

Úlohy s pravděpodobně exponenciální složitostí.
 - Problém splnitelnosti Booleovských formulí (SAT)
 - Problém kliky
 - Problém batohu
 - Problém Hamiltonovské kružnice

Rozhodovací úloha, výpočet funkce, vyhledávací úloha.

Klika a Vrcholové pokrytí jsou snadno navzájem převoditelné.
Další převody mezi úlohami:
SAT na Klika.
Velikost maximální kliky na existenci kliky velikosti alespoň b.
cvičení: Převod nalezení splňujícího ohodnocení na SAT.
cvičení: Převod nalezeni H.k. na test existence H.k.

==========================  14.10.2008  ==============================

Cvičení z minulé hodiny: nalezení splňujícího ohodnocení pomocí
testu splnitelnosti, nalezení Hamiltonovské kružnice pomocí testu
existence takové kružnice.
Algoritmy třídění, quick sort, merge sort, odhad složitosti.
Obecná věta o převodu výpočtu funkce na rozhodovací úlohu.

==========================  21.10.2008  ==============================

TS s jednostranně nekonečnou páskou, vícepáskový TS.
TS pro měření prostorové složitosti menší než velikost vstupu.
RAM, rozdíl proti RASP.
univerzální TS, použití k diagonálnímu důkazu algoritmické
neřešitelnosti problému zastavení, univerzální RAM jako realizace
RASP pomocí RAM.
Struktura RAM, registry, vstupní posloupnost, přímé a nepřímé
adresování, konstanty, aritmetické instrukce a instrukce 
podmíněného a nepodmíněného skoku.
Jednotková a bitová (logaritmická) míra složitosti RAM.

==========================  4.11.2008  ==============================

Počet násobení reálných čísel pro vynásobení dvou komplexních čísel.
Strassenův algoritmus pro násobení matic.
Násobení binárně zapsaných čísel v čase n^\alpha, kde \alpha = log_2 3 = 1.58496...
Booleovský obvod, rozdíl proti formuli, zápis pomocí lineárního programu.
Složitost obvodu.
Rozpoznávání jazyka v abecedě {0,1} po řezech pevné délky slova pomocí 
posloupnosti obvodů.
Obecné obvody jsou neuniformní model (různé algoritmy pro různě dlouhé vstupy).
Obvody konstruovatelné v polynomiálním čase (uniformní model).

==========================  11.11.2008  ==============================

Uniformní a neuniformní modely.
Neuniformní TS s polynomiálně omezenou poradní funkcí.
Orákula v rekurzi, ve složitosti, rozdíl proti poradní funkci.
Obecné třídy DTIME(t), DSPACE(s).
Třídy P, PSPACE, LOG.
Inkluze LOG \subseteq P \subseteq PSPACE
Neuniformní třídy P/poly, LOG/poly.
Zmínka o polynomiální hierarchii.
Zmínka o větě: SAT \in P/poly => \sigma_3 = \pi_3 v polynomiální hierarchii.
Rovnost uniformních modelů (zatím bez důkazu)
  P = jazyky rozpoznatelné polynomiálně velkými polynomiálně konstruovatelnými obvody
Rovnosti neuniformních modelů (jen začátek důkazu)
  P/poly = jazyky rozpoznatelné polynomiálně velkými obecnými obvody
  LOG/poly = jazyky rozpoznatelné polynomiálně velkými rozhodovacími diagramy
Speciálně, LOG/poly obsahuje jazyky definovatelné polynomiálně velkými formulemi.
Dokázáno: L rozhodnutelný polynomiálně velkými obvody => L \in P/poly.

Příště zkrácení o 10 minut v případě položení rozumné otázky.

==========================  18.11.2008  ==============================

Reprezentace jazyka "lichý počet jedniček" jako posloupnost Booleovských
funkcí "parita" a jejich vyjádření obvodem lineární velikosti a formulí
kvadratické velikosti v bázi {and, or, not}.
Posloupnost obvodů pro úlohu test souvislosti grafu. Obvody byly polynomiálně velké.
Protože předvedenou konstrukci lze efektivně naprogramovat (nepoužili jsme žádný
čistě existenční argument), jsou tyto obvody navíc polynomiálně konstruovatelné.

Dobrovolné cvičení: Důkaz správnosti algoritmu a obvodu pro test souvislosti.

==========================  25.11.2008  ==============================

Přednáška se nekonala.

==========================  2.12.2008  ==============================

Paměťový obvod pro jeden bit.
Posuvný registr s lichými a sudými hodinovými pulzy.
Sekvenční obvod, který iteruje výpočet reprezentovaný acyklickým podobvodem
a využívá dva paměťové registry pro dva po sobě jdoucí stavy výpočtu.
Pokud L \in P (resp. L \in P/poly), pak existuje efektivně konstruovatelná
(resp. obecná) posloupnost obvodů polynomiální velikosti, která rozpoznává L
při vhodném kódování abecedy L pomocí {0,1}.
Obě varianty této věty platí i opačně, tedy máme 
  P = jazyky rozpoznatelné efektivně konstruovatelnými obvody poly-velikosti
  P/poly = jazyky rozpoznatelné obecnými obvody poly-velikosti

Cvičení: obvod velikosti O(2^n) pro libovolnou Booleovskou funkci n proměnných.

==========================  9.12.2008  ==============================

Efektivní kódování vstupu.
Věta o zrychlení, nemožnost definice nejlepšího algoritmu.
Definice p-převoditelnosti.
Tranzitivita p-převoditelnosti.
Pokud je L p-převoditelný na úlohu v P, pak L v P.
Cookova věta: Libovolný jazyk v NP je p-převoditelný na 3-SAT.
NP-úplnost problému klika v grafu, nezávislá množina,
  vrcholové pokrytí (všechny tři plynou z dřívějších výsledků).
NP-úplnost MAX-2-SAT.

==========================  16.12.2008  ==============================

NP-úplnost problému Hamiltonovské kružnice a p-převoditelnost tohoto problému
na problém obchodního cestujícího.
NP-úplnost problému přesného 3-pokrytí pomocí převodu instance 3-SAT
s n proměnnými a m klausulemi na instanci problému přesného 3-pokrytí
s množinou X velikosti  4mn + 2m + 2m(n-1) = 6mn .

==========================  9.1.2009  ==============================

Problém batohu a půlení.
Rezoluční metoda důkazu spornosti teorie je úplná.
2-SAT je řešitelný v poly čase.