Předmět Strukturální složitost (NTIN081)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN081 - Strukturální složitost, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

Materiál	Typ	Datum	Počet stažení

Cíl

Naučit základy strukturální složitosti

Sylabus

Základní modely a pojmy, základní třídy problémů, polynomiální redukce, úplné a těžké problémyŘídké množiny a množiny nad jednoprvkou abecedou, separace tříd DEXT a NEXT,Turingovská polynomiální redukceBoolovské obvody, Shannonova věta, třídy P/poly, NP/poly, P/log, NP/log a jejich vztah k ostatním třídám problémůPravděpodobnostní algoritmy, třídy PP, BPP, RP a ZPP. Vztah BPP k neuniformní složitostiPolynomiální hierarchie, úplné problémy pro její třídy, zařazení BPP do polynomiální hierarchie

Literatura

[1] Balcázar, Díaz, Gabarró, Structural Complexity I, Springer Verlag, Berlin, 1988 [2] Balcázar, Díaz, Gabarró, Structural Complexity II, Springer Verlag, Berlin, 1990 [3] Schöning, Complexity and Structure, Lecture Notes in Computer Science, Springer Verlag, Berlin, 1985 [4] Allender, Limitations of the upward separation technique, Mathematical Systems Theory 24 (1991), 53-67 [5] Seiferas, Fischer, Meyer, Separating nondeterministic time complexity classes, Journal of the Association for Computing Machinery 25 (1978), no. 1, 146-167

Garant

prof. RNDr. Václav Koubek, DrSc.