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

==========================  22.2.2006  ==============================

Aproximační algoritmus pro MAX-SAT. Kombinací rovnoměrného rozdělení
proměnných a rozdělení získaného řešením lineárního programování se
dosáhne aproximačního faktoru 3/4.

==========================  1.3.2006  ==============================

Definice třídy PCP.
Znění PCP věty: NP = PCP(O(log n),O(1)).
Důsledek 1. Transformace SAT na MAX-SAT, která dá buď splnitelnou formuli nebo
    formuli s m klausulemi, z nichž je splnitelných nejvýše (1-eps)m současně.
Důsledek 2. Neexistence aprox. alg. pro MAX-SAT s faktorem 1-eps.

==========================  8.3.2006  ==============================

Neaproximovatelnost problému kliky:
 - neexistuje (1-\epsilon) aprox. alg. (důkaz převodem z MAX-SAT)
 - součinový graf, velikost maximální kliky v součinovém grafu je
   součinem velikosti maximálních klik ve výchozích grafech.
 - aprox. alg. s faktorem 1/c => aprox. alg. s faktorem (1-\epsilon)
   pro libovolně malé epsilon.
 - důsledek je, že neexistuje aprox. alg. s faktorem 1/c pro žádné
   konstantní c.

Linearní Booleovské funkce:
 - Hammingovská vzdalenost \rho(f,g) = pocet x, pro které f(x) \not= g(x)
 - f,g lineární => \rho(f,g) je některá z hodnot 0, 1/2 2^n, 2^n.
 - lineární funkce g bez abs. členu splňuje g(x)+g(y)=g(x+y).
 - Obecná lineární funkce f s absolutním členem splňuje
    f(u+v1) + f(u+v2) = f(u) + f(u+v1+v2)
 - V Booleovském případě to lze nahradit
     f(u) + f(u+v1+v2) + f(u+v1) + f(u+v2) = 0   (*)
 - Model s černou skříňkou: neznáme f, ale můžeme zjistit f(u) pro
   libovolné dané u.
 - Cílem je ověřit, zda f je lineární nebo blízká lineární funkci
   ve smyslu Hammingovy vzdálenosti pomocí co možno nejméně dotazů.
 - Spolehlivé deterministické řešení neexistuje.
 - Existuje pravděpodobnostní řešení následujícího typu.
   Vygenerujeme t trojic náhodných vektorů u,v1,v2 a pro každou trojici
   zjistíme, zda splňuje (*). Pokud některá trojice nesplňuje (*),
   pak to znamená, že byl nalezen důkaz toho, že f není lineární.
   Pokud všechny splní, pak nemůžeme zaručit, že f je lineární.
   Platí ale následující.
   Pro libovolně malá kladná \delta a \alpha existuje t tak, že výše popsaný
   test splňuje:
   Pokud Hammingovská vzdálenost f od nejbližší lineární funkce je alespoň
   \delta 2^n, pak test najde důkaz nelinearity s pravděpodobností 
   alespoň (1-\alpha).

==========================  15.3.2006  ==============================

Dvě formulace věty o testu lineárních funkcí:

Věta 1.
Nechť \delta(1-\delta) < 1/6
a     \epsilon < \delta(1-\delta)(1 - \delta(1-\delta)).
Pak pro každou f platí implikace:
   Pokud neexistuje lineární h \rho(f,h) < \delta 2^n,
   pak pravděpodobnost nalezení důkazu nelinearity
   - v jednom kroku je \ge \epsilon.
   - v t krocích je \ge 1 - (1-\epsilon)^t

Věta 2.
Pro každé 0 < \delta < 1/2 a 0 < \alpha < 1 existtuje t
tak, že pro libovolné n a každou funkci f n proměnných platí:
   Pokud neexistuje lineární h \rho(f,h) < \delta 2^n,
   pak v t krocích je nalezen důkaz nelinearity 
s pravděpodobností \ge 1-\alpha.

PSPACE, zahrnuje NP, co-NP, \Sigma_k, \Pi_k.
NPSPACE = PSPACE přes s,t-souvislost grafu konfigurací.
PSPACE-úplnost. Zmínka, že KBF je PSPACE-úplný problém.

==========================  22.3.2006  ==============================

Informace o známých výsledcích o prostorové složitosti s-t souvislosti grafů.
Pro orientované O(log n), pro neorientované O(log^2 n).
KBF je PSPACE-úplný problém (zbývá převést formuli na standardní tvar).

==========================  29.3.2006  ==============================

Dokončení PSPACE-úplnosti KBF (převod formule do standardního tvaru).
Strom konečné hry a hledání vítězné strategie pomocí min-max strategie.
PSPACE-úplnost hry na grafech.

Zavedení Blumových axiomů pro složitost.
Formulace věty o zrychlení.
Plyne z ní nemožnost definovat složitost L jako složitost nejrychlejšího algoritmu
  pro L. Složitosti nejsou lineárně uspořádané. Lze pracovat pouze s odhady
  (L je nebo není prvkem DTIME(f(n))).
Připomenutí podobných jevů v nižších složitostech (násobení matic).
Věta o dírách. Zbývá konstrukce funkce s vlastností
  r \le n => pro každé |x|=n je time(M_r,x) mimo interval [f(n)+1, 2^f(n)].

==========================  5.4.2006  ==============================

Dokončení důkazu věty o dírách.
Definice funkce konstruovatelné v čase a v prostoru.
Charakterizace pomocí vyčíslení v čase O(t(n)) nebo prostoru O(s(n)).

Poznámka k odečítání časů výpočtu: TS s časem t2-t1 se udělá tak, že
se nejprve simuluje M1 rychlostí c1 a M2 rychlostí c2. Po dokončení
výpočtu M1 se výpočet M2 dokončí normální rychlostí. Pokud c2/c1 < t2/t1
a c2 = c1 + 1, je výsledný čas t1/c1 + t2 - c2*t1/c1 = t2 - t1.

==========================  12.4.2006  ==============================

Dokončení odečítání času TS.
Ukázka problému v generátoru pseudonáhodných čísel.
Sčítání i odčítání jedniček s testem na nulu lze v čase O(n).
Postačující podmínka na konstruovatelnost f pomocí složitosti
  jejího výpočtu v binární soustavě.
Algoritmy na výpočet odmocniny, logaritmu, exponenciály,
  zatím bez odhadu složitosti.
Problém funkce splňující f(f(x)) = exp(x).

==========================  19.4.2006  ==============================

Dirichletova věta o existenci racionální aproximace |x - p/q| \le 1/q^2 .
Dvě možné formulace důkazu:
1. Rozdělit interval [0,1] na n+1 stejně dlouhých uzavřených intervalů. 
   Pro úvahu nevadí, že mají společné krajní body.
   Uvažme zlomkové části {ix}, 0 \le i \le n, přičemž pro zlomkovou část {0x}
   budeme uvažovat obě možné hodnoty 0 i 1. Máme tedy n+2 zlomkových částí
   a tedy aspoň dvě z nich padnou do stejného úseku a mají tedy rozdíl
   nejvýše 1/(n+1).
2. Seřadit zlomkové části {ix} podle velikosti a sledovat jejich vzdálenosti
   na jednotkovém intervalu uzavřeném do kruhu. Máme celkem n+1 vzdáleností
   se součtem 1. Tedy aspoň jedna z nich je nejvýše 1/(n+1).
Dolní odhad chyby racionální aproximace algebraického čísla x stupně d
|x - p/q| \ge 1/(alpha q^d)
Důkaz transcendentnosti čísla 1.11000100000000000000001000000000...
(n-tá jednička na pozici n!, jinak 0).

Složitost výpočtu e^m s absolutní chybou 1/2^k. Byl použit výpočet pomocí
řady e^m = \sum_{i=0,...,infty} m^i/i! . Byl odhadnut potřebný počet členů
a potřebná přesnost výpočtu každého z nich. Výsledná časová složitost byla
polynomiální od délky výstupu a prostorová byla lineární od délky výstupu.

==========================  26.4.2006  ==============================

Věta o prostorové a časové hierarchii.
(K problému s čítačem: Neuvědomil jsem si, že už tři roky
používám definici DSPACE(s), která vyžaduje, aby se stroj
vždy zastavil. Důkaz prostorové hierarchie tedy již nevyžaduje
zařazení žádného čítače.)

==========================  3.5.2006  ==============================

Eulerova věta (zobecnění malé Fermatovy věty).
Použití Eucleidova algoritmu na nalezení inverzního prvku v Z_m.
RSA systém veřejného klíče (znám od roku 1977).
Diffie-Hellman systém distribuce tajného klíče (znám od roku 1976).

==========================  10.5.2006  ==============================

Věta: Číslo n je prvočíslo právě tehdy, když pro každé přirozené
   číslo a z intervalu [2,n-2] platí a^{n-1} = 1 mod n.
V důkazu se využije toho, že pro složené n lze zvolit a, které je s n soudělné.

Pokud chceme, aby svědků pro složené n bylo hodně, je nutné, aby jich byl
velký počet i mezi zbytkovými třídami nesoudělnými s n.
Toto nelze obecně zaručit.

Příklad: 561 je Carmichaelovo číslo.
Důkaz na základě vlastností jeho rozkladu.

Pravděpodobnostní test prvočíselnosti využívající silnější kriterium:
Nechť n-1 = q 2^k, kde q je liché.
Pak nechť x_i = a^{q 2^i} pro i = 0,...,k.

Číslo a je svědkem toho, že n je složené, pokud nastane jeden
z těchto případů:
1. x_k \not= 1
2. pro některé i = 0,...,k-1 platí současně 
   x_i \not\in {-1,1} a x_{i+1} = 1

Dokázali jsme, že pro složené číslo n existuje alespoň n/2 svědků
podle výše uvedeného kriteria.