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

===================================  15.10.2015  ===================================

Algoritmy v historických dobách, rovnice x^2 - 61 y^2 = 1.
Mechanický kalkulátor (sériová výroba od 1851), differential machine (1855), Hollerith (1890 United States Census).
Church-Turingova teze.
Kvantový počítač nepřekračuje sílu Turingova stroje, lze simulovat klasickým počítačem v exponenciálně delším čase.
Existují algoritmy pro kvantový počítač pro úlohu faktorizace přirozených čísel a pro úlohu diskrétního logaritmu.
Není známo, zda kvantový počítač může řešit SAT v polynomiálním čase.
Zmínka o kryptografii, AES, MD5.
Vyčíslitelnost v polynomiálním čase, Cobham 1964.
Složitost faktorizace přirozených čísel.
Zápis instancí úloh pomocí slov v konečné abecedě, kódování symbolů pomocí bloků v abecedě {0,1}.
Počet bitů v binárním zápisu přirozeného čísla n je nejvýše log n + 1.
Bezprefixové kódování, umožnuje kódování n-tic objektů zřetězením jejich kódů.
Problém zastavení Turingova stroje v daném čase, redukce na Presburgerovu aritmetiku a teorii reálných čísel.
Diagonální metodu pravděpodobně nelze použít k rozhodnutí otázky P versus NP (relativizace).

===================================  22.10.2015  ===================================

Diffie-Hellman key exchange.
Fermatova a Mersennova prvočísla.
Konstruovatelnost n-úhelníka pravítkem a kružítkem.
Generátor Mersenne Twister s periodou 2^19937-1.
Souvislost predikovatelnosti náhodného generátoru a řešitelnosti soustavy rovnic.
RSA factoring challenge.
Výpočet (a^k mod m) pomocí 2(l-1) násobení, kde l je počet bitů čísla k.
Násobení n bitových čísel složitosti O(n^alpha), kde alpha = log_2 3 = 1.585.
Další algoritmy pro násobení, složitost n log n log log n.
Zmínka o násobení matic.
Dijkstrův algoritmus.
Úlohy TAUT a SAT.
Převod na úlohu minimálního splňujícího ohodnocení monotonní formule.
Problém maximální kliky.
Příklad grafu: 6 vrcholů, 8 maximálních klik velikosti 3.
Obecněji jde o konstrukci z Turánovy věty.

===================================  29.10.2015  ===================================

Použití zásobníku v programech s rekurzí, nahrazení zásobníku polem.
Turánova věta o grafech.
Věty Ramseyova typu, zmínka o Paris-Harringtonově větě.
Reprezentace jednotlivých typů úloh pomocí relace, funkce a jazyka.
Nalezení splňujícího ohodnocení pomocí testu splnitelnosti.
Nalezení některé kliky velikosti m pomocí testu existence kliky této velikosti.
Blumovy axiomy pro složitost a věta o exponenciálním zrychlení.
Turingův stroj, přechodová funkce, reprezentace grafem.

===================================  5.11.2015  ===================================

Použití vícestopé pásky v TS.
Simulace vícepáskového TS jednopáskovým (v čase t^2) a dvoupáskovým (v čase t log t).
DTIME, DSPACE.
NP pomocí existenční kvantifikace, PSPACE.
Každou NP-úplnou úlohu lze převést na libovolnou PSPACE-úplnou úlohu.
Pokud je NP různé od PSPACE, pak opačný převod možný není, ale složitost PSPACE-úplné
  úlohy může být menší než složitost NP-úplné úlohy.
Riemannova hypotéza, univerzalita Riemannovy zeta funkce
  https://en.wikipedia.org/wiki/Zeta_function_universality

===================================  7.1.2016  ===================================

Definice NP-úplnosti, definice p-převoditelnosti.
Přenos polynomiálního algoritmu přes p-převoditelnost.
Tranzitivita p-převoditelnosti.
Definice NP-úplnosti.
P-převoditelnost SAT na Mon-SAT a opačně.
P-převoditelnost SAT na problém kliky a opačně.
Konstrukce efektivně konstruovatelných obvodů pro simulaci TS v polynomiálním čase.
Problém CSAT (circuit SAT) je NP-úplný.