Complexity Theory

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

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.

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.

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

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

Cíle studia:

To provide a theoretical background for deciding whether a given problem is, according to our present knowledge, tractable and what kind of computational methods could be used.

Studijní materiály:

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

Poznámka:

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

Další informace:

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

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Master specialization Software Engineering, in English, 2021 (volitelný předmět)
• Master specialization Computer Security, in English, 2021 (volitelný předmět)
• Master specialization Computer Systems and Networks, in English, 2021 (volitelný předmět)
• Master specialization Design and Programming of Embedded Systems, in English, 2021 (volitelný předmět)
• Master specialization Computer Science, in English, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Master Specialization Digital Business Engineering, 2023 (volitelný předmět)