Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

Anotace:
Students will learn about the fundamental classes of problems in the complexity theory and different models of algoritms and about implications of the theory concerning practical (in)tractability of difficult problems.

Osnovy přednášek:
Computational problems and models of computation, Turing Machine, Undecideability. Time hierarchy, non-deterministic Turing Machine. Class NP, the existence of an NP-complete problem, Cook's theorem. Strong and weak NP-hardness, pseudopolynomial algorithms, class coNP, Ladner's theorem. Oracle Turing Machine, relativization, Baker-Gill-Solovay theorem. Polynomial hierarchy, problems hard for classes of the hierarchy. Space complexity, Class PSPACE, Savitch's Theorem, Logspace. Boolean circuits, Circuit complexity, P/poly, circuits of bounded depth, paralelization of computation, P-completeness. Probabilistic Turing Machine, Classes of randomized algorithms, error reduction, relations to P/poly and to Polynomial Hierarchy. Optimalization problems, Approximation algorithms, Classes of approximability. Probabilistically checkable proofs, PCP theorem, inaproximability of Vertex Cover and Independent Set. Exponential Time Hypothesis (ETH), Strong ETH, their relations and implications. Quantum Computation and relations to classical classes.

Osnovy cvičení:
Complexity of algorithms, simulation of models of computation in different model. Non-determinism, class NP. Problems outside NP, various NP-complete problems a reductions between them, problems in coNP. Problems in PSPACE and various classes of the polynomial hierarchy, examples of circuits for various simple problems. Amplification of success probability of randomized algorithms, examples of randomized algorithms. Various approximation algorithms a proofs of inapproximability.

Literatura:

S.

Arora, B. Barak, ''Computational Complexity: A Modern Approach''. Cambridge University Press, 2009. ISBN 0521424267.

Goldreich, O. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 052188473X.

R.		Motwani, P. Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995. ISBN 0521474655.
M.		Mitzenmacher, E. Upfal, '' Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, 2005, ISBN9780521835404.

Wigderson, A., "Mathematics and Computation: A Theory Revolutionizing Technology and Science", Princeton University Press, 2019, ISBN 9780691189130 Christos H. Papadimitriou, ?Computational Complexity?. Pearson, 1993. ISBN 978-0201530827

D.		P. Williamson, D. B. Shmoys: ?The Design of Approximation Algorithms?, Cambridge university press, 2011. ISBN 9780521195270
V.		V. Vazirani: Approximation Algorithms, Springer, 2001. ISBN 3540653678

Požadavky:
Knowledge of graph theory and graph algorithms in scope of BIE-AG1, as well as formal languages, Turing machines, P and NP classes, and nedeterminism in scope of BIE-AAG is assumed. Knowledge from BIE-AG2, such as Hamilton cycles, TSP, approximation algorithms, etc. is highly beneficial.

https://courses.fit.cvut.cz/NI-CPX/

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr NIE-SI.21 Software Engineering 2021 V Není NIE-TI.21 Computer Science 2021 V Není NIE-DBE.2023 Digital Business Engineering V Není NIE-NPVS.21 Design and Programming of Embedded Systems 2021 V Není NIE-PSS.21 Computer Systems and Networks 2021 V Není NIE-PB.21 Computer Security 2021 V Není