Neuniformní výpočetní modely - NTIN082

• Anglický název: Nonuniform computational models
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• 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í
• 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

Anotace

čeština

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 různými druhy booleovských obvodů a branching programů, jejich vzájemnými vztahy a vztahy s klasickými výpočetními třídami.

angličtina

Poslední úprava: T_KTI (26.04.2016)

This course extends the basic course on computational complexity (NTIN063). It covers various types of Boolean circuits and branching programs, their relationships and relationships to the usual complexity classes.

Cíl předmětu

Poslední úprava: T_KTI (26.04.2016)

Naučit další látku z teorie složitosti zejména v oblasti neuniformních výpočetních modelů.

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

čeština

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

Zkouška je ústní.

angličtina

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

The exam is oral.

Literatura

čeština

Poslední úprava: T_KTI (26.04.2016)

Stasys Jukna. Boolean Function Complexity: Advances and Frontiers.

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

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

Požadavky ke zkoušce

čeština

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

Zkouš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.

angličtina

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

he 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.

Sylabus

čeština

Poslední úprava: T_KTI (26.04.2016)

Třída P/poly, Booleovské obvody

coNEXP součástí NEXP/poly (exponenciální verze NP vs coNP)

NP^NP nemůže mít Booleovské obvody velikosti O(n^k) pro pevné k

Obvody logaritmické hloubky, Booleovské formule

Obvody konstantní hloubky

Parita není v AC0 - důkaz Razborova a Smolenského

Aproximace MAJ je v AC0

ACC0 vs CC0

Redukce hloubky obvodu

Williams: NEXP není v ACC0

Branching programy, vztah k logaritmickému prostoru

Barringtonova věta o vztahu branching programů k Booleovským formulím

Generalizace Barringtonovy věty: vyhodnocení aritmetické formule s použitím tří registrů

Katalytické výpočty

angličtina

Poslední úprava: T_KTI (26.04.2016)

Boolean circuits and P/poly

coNEXP is not in NEXP/poly

NP^NP does not have circuit of size O(n^k), for fixed k

Logarithmic depth circuit, Boolean formulas

Constant depth circuits

Parity not in AC0 - proofs of Razborov and Smolensky

Approximating MAJ in AC0

ACC0 vs CC0

Circuit depth reductions

Williams: NEXP is not in ACC0

Branching programs and their relationship to space bounded computation

Barrington's Theorem

Generalization of Barrington's Theorem for arithmetic formulas

Catalytic computation