Course details
Complexity
Guarantor
Language of instruction
Czech
Completion
Examination
Time span
- 26 hrs lectures
- 26 hrs projects
Department
Study literature
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
- Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
- Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7
Fundamental literature
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
Syllabus of lectures
- Introduction. Complexity, time and space complexity.
- Matematical models of computation. Skeleton language.
- RAM, RASP machines and their relation with Turing machines.
- Nondeterminism. Oracle machines. Reducibility.
- P and NP. Examples: Kruskal, Traveling Salesman.
- NP-completness. NP-complete problems.
- Satisfability problem and its variants.
- Other NP-problems.
- NP and co-NP languages.
- Space complexity, PS and NPS languages.
- PS-complete languages.
- Language classes based on randomization - classes RP and ZPP.
- Applications: Cryptography and one-way functions.
Course inclusion in study plans