PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Strukturální složitost - NTIN081
Anglický název: Structural Complexity
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2016
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. Mgr. Michal Koucký, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN063
Je korekvizitou pro: NTIN082
Anotace -
Poslední úprava: T_KTI (26.04.2016)

Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s hierarchií pro pravděpodobnostní třídy výpočtů, time-space trade-offs pro SAT, Todovou větou, pseudonáhodnými generátory a interaktivními protokoly.
Cíl předmětu
Poslední úprava: T_KTI (26.04.2016)

Naučit další látku z teorie složitosti: vztahy mezi třídami složitosti, pseudonáhodné generátory a interaktivni protokoly.

Literatura -
Poslední úprava: T_KTI (26.04.2016)

Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008.

Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008.

D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Computational Complexity, 16: 139-179, 2007.

D. van Melkebeek. Time-Space Lower Bounds for Satisfiability. Bulletin of EATCS, 73: 57-77, 2001.

Sylabus -
Poslední úprava: T_KTI (26.04.2016)

Nedeterministická časová hierarchie a hierarchie pro pravděpodobnostní třídy výpočtů

BPP a polynomiální hierarchie

Time-space trade-off pro SAT

Izolační lema a Todova věta

Pseudonáhodné generátory, Nisanův pseudonáhodný generátor

Interaktivní protokoly - Arthur-Merlin (třída AM, IP=PSPACE)

Interaktivní protokoly s více dokazateli (MIP=NEXP)

 
Univerzita Karlova | Informační systém UK