Course details
Complexity
SLO Acad. year 2012/2013 Summer semester 5 credits
This course covers the following themes: Matematical models of computation ( skeleton language, RAM, RASP models and their connection with Turing machines), time complexity, complexity classes, P and NP, NP-completness, important 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, applications of computational complexity theory - cryptography and one-way functions.
Guarantor
Language of instruction
Completion
Time span
- 26 hrs lectures
- 26 hrs projects
Department
Subject specific learning outcomes and competences
Understanding theoretical and practical limits of arbitrary computational systems.
Learning objectives
To learn mathematical models of computation and complexity theory.
Prerequisite knowledge and skills
There are no prerequisites
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.
Progress assessment
Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.
The minimal total score of 15 points gained out of the projects.
Controlled instruction
- Projects: max. 32 points
- Final exam: max. 68 points
Course inclusion in study plans