Complexity Theory

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
NI-CPX Z,ZK 5 3P+1C Czech
Garant předmětu:
Ondřej Suchý
Dušan Knop, Ondřej Suchý
Michal Opler, Ondřej Suchý
Department of Theoretical Computer Science

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.


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.

Syllabus of lectures:

1. Computational problems and models of computation

2. Undecideability, non-determinism, class NP, existence of an NP-complete problem

3. Further NP-complete problems, strong and weak NP-hardness, pseudopolynomial algorithms

4. Classes coNP and NP intersection coNP, polynomial hierarchy

5. Problem of P=NP, relativization

6. Class PSPACE, Savitch's Theorem

7. PSPACE-complete problems (quantified formulas and games), problems hard for classes of the hierarchy

8. Logspace

9. Circuit complexity, P/poly, circuits of bounded depth, paralelization of computation

10. P-completeness

11. Randomized algorithms

12. Relations between classes of randomized algorithms and with other classes

13. Optimalization probléms, Approximation algorithms

14. Probabilistically checkable proof, gap problem, PCP theorem

15. Communication complexity

16. Complexity of counting, #P

17. (Strong) Exponential Time Hypothesis, corollaries

18. Pseudo random number generators, derandomization

Syllabus of tutorials:

1. Complexity of algorithms, simulation of models of computation in different model

2. Problems outside NP, various NP-complete problems a reductions between them, problems in coNP

3. Problems in PSPACE and various classes of the polynomial hierarchy, examples of circuits for various simple problems

4. Various approximation algorithms a proofs of inapproximability

5. Amplification of success probability of randomized algorithms, examples of randomized algorithms

6. Communication schemes, lower bounds for communication complexity

Study Objective:

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.

Study materials:

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

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

R. Motwani, P. Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995. ISBN 0521474655.

Further information:
Time-table for winter semester 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2023-06-05
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6290606.html