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 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: 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

Anotace

čeština

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.

Poslední úprava: T_KTI (26.04.2016)

angličtina

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.

Poslední úprava: T_KTI (26.04.2016)

Cíl předmětu

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

Poslední úprava: T_KTI (26.04.2016)

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

čeština

Zkouška je ústní.

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

angličtina

The exam is oral.

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

Literatura

čeština

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.

Poslední úprava: T_KTI (26.04.2016)

Požadavky ke zkoušce

čeština

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.

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

angličtina

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.

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

Sylabus

čeština

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

Poslední úprava: T_KTI (26.04.2016)

angličtina

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

Poslední úprava: T_KTI (26.04.2016)