Complexity Theory
Code  Completion  Credits  Range  Language 

NICPX  Z,ZK  5  3P+1C  Czech 
 Garant předmětu:
 Ondřej Suchý
 Lecturer:
 Dušan Knop, Ondřej Suchý
 Tutor:
 Michal Opler, Ondřej Suchý
 Supervisor:
 Department of Theoretical Computer Science
 Synopsis:

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

Knowledge of graph theory and graph algorithms in scope of BIEAG1, as well as formal languages, Turing machines, P and NP classes, and nedeterminism in scope of BIEAAG is assumed. Knowledge from BIEAG2, such as Hamilton cycles, TSP, approximation algorithms, etc. is highly beneficial.
 Syllabus of lectures:

1. Computational problems and models of computation
2. Undecideability, nondeterminism, class NP, existence of an NPcomplete problem
3. Further NPcomplete problems, strong and weak NPhardness, pseudopolynomial algorithms
4. Classes coNP and NP intersection coNP, polynomial hierarchy
5. Problem of P=NP, relativization
6. Class PSPACE, Savitch's Theorem
7. PSPACEcomplete 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. Pcompleteness
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 NPcomplete 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 9780201530827
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.
 Note:
 Further information:
 https://courses.fit.cvut.cz/NICPX/
 Timetable for winter semester 2023/2024:
 Timetable is not available yet
 Timetable for summer semester 2023/2024:
 Timetable is not available yet
 The course is a part of the following study plans:

 Master specialization Computer Security, in Czech, 2020 (elective course)
 Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
 Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
 Master specialization Management Informatics, in Czech, 2020 (elective course)
 Master specialization Software Engineering, in Czech, 2020 (elective course)
 Master specialization System Programming, in Czech, version from 2020 (elective course)
 Master specialization Web Engineering, in Czech, 2020 (elective course)
 Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
 Master specialization Computer Science, in Czech, 2020 (elective course)
 Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
 Study plan for Ukrainian refugees (elective course)