TIN048 - Složitost a dolní odhady
ZS 2002
Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: 2/0 Zk
Rozsah v LS: ---
Třída: I
Anotace
Lze dokázat, že nějakou explicitní funkci nelze počítat jednoduchými algoritmy?
Známe mnoho problémů, o kterých předpokládáme, že se nedají jednoduše řešit
(např. NP-úplné problémy), ale o žádné takové funkci neumíme dokázat například
ani to, že se nedá počítat ve třech krocích na paralelním počítači s polynomiálním
počtem procesorů, které umí počítat prahové funkce v jednom kroku.
Cílem přednášky je podat co nejúplnější obraz současného stavu výzkumu
v této části teorie složitosti. Přednáška je určena především studentům
vyšších ročníků a doktorandům. Přednášející v tomto oboru pracuje a publikuje.
Související přednášky jsou TIN020 Složitost a NP-úplnost a AIL021 Booleovské
funkce a jejich aplikace, které se zabývají podobnými tématy, ale obsahově
se nepřekrývají a ani nejsou předpokladem této přednášky.
Osnova
-
Booleovské a algebraické obvody a jejich třídy. Definice a základní odhady
velikosti (Shannon)
-
Exponenciální dolní odhady na velikost monotónních obvodů. Aproximační
metoda a metoda fúze.
-
Výrokové počty, definice a souvislost se složitostí výpočtů. Dolní odhady
pro vybrané výrokové kalkuly (interpolace, algebraické metody).
-
Dolní odhady na velikost obvodů konstantní hloubky, Hastadovo "switching
lemma".
-
Obvody konstantní hloubky s prvky počítajícími paritu a prahové funkce.
-
Komunikační složitost jako metoda pro dokazování dolních odhadů. Odhady
na hloubku monotónních obvodů.
-
Dolní odhady na velikost a hloubku formulí (nemonotónních).
-
Meze současných metod pro dokazování dolních odhadů (tzv. "natural proofs").
Základní lit.
Většinou články z časopisů a konferencí. Základní pojmy jsou v různém rozsahu
vyloženy např. v těchto knihách:
Papadimitriou: Computational Complexity
Garey, Johnson: Computers and Intractability. A guide to the theory
of NP-completeness.
Doplň.popis
Přednáška se nekoná každý rok, předpokládám její opakování za 2-3 roky.
Úmluva bude v prvním týdnu semestru na KAM, v rámci hromadné úmluvy na
výběrové přednášky KAM. Kontakt: sgall@math.cas.cz,
http://www.math.cas.cz/~sgall/,
tel. 222 090 780.
4. 10. 2002