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 2024
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Garant: prof. Mgr. Michal Koucký, Ph.D.
• Vyučující: prof. Mgr. Michal Koucký, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Korekvizity : NTIN063

Anotace

čeština

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.

Poslední úprava: T_KTI (26.04.2016)

angličtina

This course extends the basic course on computational complexity (NTIN063). It covers hierarchy theorems for probabilistic computation, time-space trade-offs for SAT, Toda's Theorem, pseudo-random generators and interactive protocols.

Poslední úprava: T_KTI (26.04.2016)

Cíl předmětu

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

Poslední úprava: T_KTI (26.04.2016)

Podmínky zakončení předmětu

čeština

Ústní zkouška

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

angličtina

Oral exam.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

Literatura

čeština

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.

Poslední úprava: T_KTI (26.04.2016)

Požadavky ke zkoušce

čeština

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.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

angličtina

The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.

Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

Sylabus

čeština

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)

Poslední úprava: T_KTI (26.04.2016)

angličtina

Nondeterministic time hierarchy and hierarchy for probabilistic computation

BPP and polynomial hierarchy

Time-space trade-off for SAT

Isolation Lemma and Toda's Theorem

Pseudo-random generators, Nisan's pseudo-random generator

Interactive protocols - Arthur-Merlin games (class AM, IP=PSPACE)

Multi-prover interactive protocols (MIP=NEXP)

Poslední úprava: T_KTI (26.04.2016)