PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Výpočetní složitost a interaktivni protokoly - NTIN081
Anglický název: Computational complexity and interactive protocols
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021 do 2021
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. Mgr. Michal Koucký, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN063
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
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.

Podmínky zakončení předmětu -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

Ústní zkouška

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.

Požadavky ke zkoušce -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

kouška je ústní. Zkouší se z probrané látky. Po zadání otázek dostane student čas na přípravu.

Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny.

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