Complexity Theory
Code  Completion  Credits  Range  Language 

MICPX  Z,ZK  5  3P+1C  Czech 
 Lecturer:
 Luděk Kučera (guarantor), Ondřej Suchý
 Tutor:
 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 (un)solvability of difficult problems.
 Requirements:
 Syllabus of lectures:

1. Models of computation.\r
2. Algorithmic undecidability.\r
3. Nondeterminism, the class NP, the existence of an NPcomplete problem.\r
4. NPcomplete problems.\r
5. Problem P=NP, relativization, classes coNP and NP intersection coNP.\r
6. The class PSPACE, Savitch theorem, hierarchy in PSPACE.\r
7. PSPACEcomplete problem (quantified formulae and games), complete problem for the hierarchy classes.\r
8. Circuit and algebraic complexity.\r
9. Randomized algorithms, complexity classes of randomized algorithms (classes BPP, ZP, RP).\r
10. Oneway functions, pseudorandom sequences, discrete logarithm, cryptography.\r
11. Interactive proofs, probabilistically verifiable proofs, expanders, gap problem, PCP theorem, nonaproximability of 3SAT.\r
 Syllabus of tutorials:

1. Mutual simulations of computational models.
2. [2] NPcomplete problems and their reductions.
3. Particular problems in coNP and NP intersection coNP.
4. [2] Complete problems for PSPACE and different classes of the hierarchy in PSPACE.
5. [2] Examples of circuits for different simple problems, bounded fanin.
6. [3] Examples of different MonteCarlo and Las Vegas algorithms.
7. Examples of pseudorandom sequences ans simple facts about their (non)predictability.
8. Amplification of a success probability, examples of randomized algorithms.
9. Expanders and random walks, Markov chains and their mixing.
 Study Objective:

Provide a theoretical background for deciding whether a given problem is, according to our present knowledge, solvable and what kind of computational methods could be used.
 Study materials:

1. Arora, S., Barak, B. ''Computational Complexity: A Modern Approach''. Cambridge University Press, 2009. ISBN 0521424267.
2. Goldreich, O. ''Computational Complexity: A Conceptual Perspective''. Cambridge University Press, 2008. ISBN 052188473X.
3. Motwani, R., Raghavan, P. ''Randomized Algorithms''. Cambridge University Press, 1995. ISBN 0521474655.
 Note:
 Further information:
 https://courses.fit.cvut.cz/MICPX/
 Timetable for winter semester 2018/2019:

06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Fri Thu Fri  Timetable for summer semester 2018/2019:
 Timetable is not available yet
 The course is a part of the following study plans:

 Specialization System Programming, Presented in Czech, Version 2014, 2015 (elective course)
 Specialization Web Engineering, Presented in Czech, for Students who Enrolled in 2014 and 2015 (elective course)
 Knowledge Engineering, in Czech, Presented in Czech, for Students who Enrolled in 2015 (elective course)
 Master Informatics, Presented in Czech, Version for Students who Enrolled in 2015 (VO, elective course)
 Knowledge Engineering, in Czech, Presented in Czech, Version 2016 and and 2017 (elective course)
 Computer Systems and Networks, Presented in Czech, Version 2016, 2017 and 2018 (elective course)
 Design and Programming of Embedded Systems, in Czech, Version 2016, 2017 and 2018 (elective course)
 Specialization Web and Software Engineering, in Czech, Version 2016, 2017 and 2018 (elective course)
 Specialization Software Engineering, in Czech, Version 2016, 2017 and 2018 (elective course)
 Specialization Web Engineering, Presented in Czech, Version 2016, 2017 and 2018 (elective course)
 Master Informatics, Presented in Czech, Version 2016, 2017 and 2018 (VO)
 Specialization System Programming, Presented in Czech, Version 2016, 2017 and 2018 (elective course)
 Specialization Computer Science, Presented in Czech, Version 20162017 (compulsory course of the branch)
 Knowledge Engineering, in Czech, Presented in Czech, Version 2018 (elective course)