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

==========================  9.10.2007  ==============================

Budeme se zabývat tím, jak velký prostor a čas je potřebný k řešení úloh na počítači.
Algoritmicky neřešitelné úlohy:
 - L(G) = \Sigma^*
 - L(G_1) \cap L(G_2) \not= 0
 - problém slov v obecné asociativní algebře
 - polynomiální rovnice více proměnných v přirozených číslech 
   (důkaz neřešitelnosti pochází od Matijaseviče, 10. Hilb. problém)
Příklady náročných úloh:
 - problém obchodního cestujícího (TSP)
 - konečné hry (šachy, go, hra na grafech)
 - problém splnitelnosti výrokových formulí (SAT)
Algoritmus násobení n bitových čísel složitosti n^log_2 3.
Existuje algoritmus složitosti O(n log n log log n).
Připomenuto značení O(f), \Omega(f).

==========================  16.10.2007  ==============================

Algoritmická neřešitelnost polynomiálních rovnic v celých číslech.
Položena otázka úspornější parametrizace n přirozených čísel pomocí
celých čísel než pomocí 4n parametrů.

Důkaz vzájemné převoditelnosti následujících problémů
 (A) splnitelnost Booleovských formulí v KNF 
 (B) řešitelnost soustav polynomiálních rovnic v tělese Z_2.
 (C) splnitelnost obecných Booleovských formulí v bázi všech binárních spojek
Převod úlohy typu (A) na (B) pomocí přepisu klausule l_1, ..., l_k
na polynom (1 - (1 - l_1)...(1 - l_k)).
Převod úlohy typu (B) na (C) lze provést náhradou násobení za konjunkci
a sčítání za nonekvivalenci.
Převod úlohy typu (C) na (A) vyžaduje přidání nových proměnných, které
popisují hodnoty všech podformulí. S pomocí těchto nových proměnných
se vyhodnocení formule popíše pomocí lokálních podmínek svazujících
každou podformuli s jejími bezprostředními podformulemi.

Shrnuty pojmy
 - rozhodovací úloha
 - výpočet funkce
 - vyhledávací úloha
Zaveden pojem optimalizační úloha.

==========================  23.10.2007  ==============================

- Příklady optimalizačních úloh, rozhodovací varianta, výpočet optima,
  hledání optimálního řešení.
- Zavedení TS s jednou a více páskami, kopírování s jednou a dvěma páskami.
- Značení pro čas t(w), t(n) a prostor s(w), s(n) pro konkrétní TS. Výpočty
  s prostorovou složitostí menší než n.
- RAM, jednotková a logaritmická (bitová) složitost.
- RAM s násobením. Jednotková a bitová složitost n násobného umocnění na druhou.
- RAM bez násobení a dělení. Složitost operace trunc(x/2).
  Poznámka: Navržený algoritmus pro trunc(x/2) s konstantním prostorem
  má jednotkovou složitost O(n^2), kde n je délka zápisu x.
- Požadavek rozumného kódování. Musí být efektivní (nejvýše polynomiální)
  převod mezi kódem a původní strukturou v modelu, kdy můžeme přímo pracovat
  s libovolnými kombinatorickými strukturami. Není to exaktně definovaný pojem,
  protože není formálně zaveden potřebný výpočetní model.
  Zmínka o problému testování a^b \lt c^d pro n bitová čísla.

Poznámka: V roce 1796 dokázal Gauss, že každé přirozené číslo je
součtem tří trojúhelníkových čísel, což jsou čísla tvaru n(n+1)/2,
tedy choose(n+1,2).

==========================  30.10.2007  ==============================

Transformace rovnice n proměnných z N na 
 1. rovnici s 11 proměnnými ze Z pomocí zesílení Matijasevičovy věty
 2. rovnici s 3n proměnnými ze Z pomocí Gaussova výsledku o součtu
    tří trojúhelníkových čísel.
Hledání splňujícího ohodnocení výrokové formule pomocí testu splnitelnosti.
Hledání Hamiltonovské kružnice pomocí testu přítomnosti takové kružnice.
Úvaha o hledání důkazu matematické věty pomocí testu dokazatelnosti.
Poznámka, že algoritmicky nerozhodnutelný problém musí obsahovat
  instance nezávislé na teorii množin.
Konstrukce jazyka L_f pro danou funkci s polynomiálně omezenou
  délkou výstupu. Důkaz, že L_f je v P právě když f je vyčíslitelná
  v polynomiálním čase.
Zavedení tříd DTIME(t) a DSPACE(s).
Blumova věta o (exponenciálním) zrychlení. Důsledek: nelze definovat
  složitost úlohy, jen algoritmu. Složitost úlohy lze charakterizovat
  jen tím, zda L patří do DTIME(t) nebo DSPACE(s) pro konkrétní
  míry složitosti t,s. Množina takových t,s nemusí mít minimum.
Zmínka o větě o dírách a o konstruovatelnosti.
Zavedení Booleovských obvodů. Transformace polynomiálního výpočtu TS
  na polynomiálně velký obvod.
Neuniformní modely. TS s pomocnou funkcí alpha.

==========================  6.11.2007  ==============================

Algoritmy na RAM bez dělení a násobení pro výpočet trunc(x/2)
s konstantní pamětí.
Zavedení P/poly, LOGSPACE/poly.
formule \subseteq LOGSPACE/poly (bez důkazu).
obvody = P/poly (bez důkazu).
Toto dává do souvislosti porovnání síly výrokových formulí
a obvodů s porovnáním neuniformních variant tříd LOGSPACE a P,
o kterých se předpokládá, že vnoření LOGSPACE do P je ostré.
STCONN je v DSPACE(log^2 n).
USTCONN je v DSPACE(log n) = LOGSPACE.
Pravděpodobnostní TS.
Polynomiální pravděpodobnostní TS lze simulovat ve třídě P/poly.
Ekvivalence read-once rozhodovacích diagramů je rozhodnutelná
pravděpodobnostním TS v poly čase.
(Stroj může nezjistit neekvivalenci, ale nemůže udělat chybu,
pokud jsou ekvivalentní.)
Interaktivní pravděpodobnostní důkaz neizomorfnosti dvou grafů.

==========================  13.11.2007  ==============================

LOGSPACE \subseteq P.
Také LOGSPACE/poly \subseteq P/poly.
Polynomiální formule pro maticovou funkci "v každém sloupci dvě jedničky po sobě".
Logaritmický prostor na TS pro tuto úlohu.
Programovací jazyk pro TS.
Simulace k-páskoveho 1-páskovým TS.
Náznak simulace k-páskového 2-páskovým TS.
Uložení registrů RAM na pásce TS.

==========================  20.11.2007  ==============================

Simulace RAM pomocí TS.
Simulace RAM pomocí efektivně konstruovatelných obvodů.
Ekvivalence P/poly a obecných obvodů.
Zavedení p-převoditelnosti.
SAT je p-převeditelný na problém klika v grafu.

==========================  27.11.2007  ==============================

p-převoditelnost problému kliky na SAT.
Splnitelnost Booleovských obvodů je NP-úplná úloha.
Vyjádření lokálních podmínek pro splnění obvodů dává formuli
v KNF, což dokazuje NP-úplnost SAT.
p-převoditelnost SAT na 3-SAT.

==========================  4.12.2007  ==============================

NP-úplnost problému přesného 3-pokrytí.
Vzájemná p-převoditelnost problému batohu s přirozenými a s celými čísly.
NP-úplnost problému batohu s přirozenými čísly převodem z 3-SAT.

==========================  11.12.2007  ==============================

Problém batohu s celými čísly.
Problém rozdělení v přirozených a celých číslech.
Ekvivalence všech uvedených variant problému batohu.
Problém batohu lze řešit v čase, který je polynomiální
v hodnotách čísel n,b.
Věta o úplnosti rezoluce (zatím bez důkazu).
Důsledek: 2-SAT je v P.
Nedokončené řešení 2-SAT pomocí grafu.
Zavedení aproximačních algoritmů.
Problém vrcholového pokrytí a jeho souvislost
s problémem kliky (zatím bez důkazu).

==========================  18.12.2007  ==============================

Vzájemná p-převeditelnost problému kliky a vrcholového pokrytí.
Dokončení testu 2-SAT přes tranzitivní uzávěr implikací.
Důkaz úplnosti rezoluční metody.
Aproximační algoritmus pro vrcholové pokrytí s faktorem 2.