Course details
Complexity (in English)
SLOa Acad. year 2024/2025 Summer semester 5 credits
Turing machines as a basic computational model for computational complexity analysis, time and space complexity on Turing machines. Alternative models of computation, RAM and RASP machines and their relation to Turing machines in the context of complexity. Asymptotic complexity estimations, complexity classes based on time and spaceconstructive functions, typical examples of complexity classes. Properties of complexity classes: importance of determinism and nondeterminism in the area of computational complexity, Savitch theorem, relation between nondeterminism and determinism, closure w.r.t. complement of complexity classes, proper inclusion between complexity classes. Selected advanced properties of complexity classes: Blum theorem, gap theorem. Reduction in the context of complexity and the notion of complete classes. Examples of complete problems for different complexity classes. Deeper discussion of P and NP classes with a special attention on NPcomplete problems (SAT problem, etc.). Relationship between decision and optimization problems. Methods for computational solving of hard optimization problems: deterministic approaches, approximation, probabilistic algorithms. Relation between complexity and cryptography. Deeper discussion of PSPACE complete problems, complexity of formal verification methods.
Guarantor
Course coordinator
Language of instruction
Completion
Time span
 26 hrs lectures
 26 hrs projects
Assessment points
 70 pts final exam
 30 pts projects
Department
Lecturer
Instructor
Learning objectives
Familiarize students with the complexity theory, which is necessary to understand practical limits of algorithmic problem solving on physical computational systems.
Familiarize students with a selected methods for solving hard computational problems.
Understanding theoretical and practical limits of arbitrary computational systems. Ability to use a selected methods for computationally hard problems.
Recommended prerequisites
Prerequisite knowledge and skills
Formal language theory and theory of computability on master level.
Study literature
 Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1846282977
 Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0139153802
 Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 052188473X
Fundamental literature
 Papadimitriou, C. H.: Computational Complexity, AddisonWesley, 1994, ISBN 0201530821
 Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Dostupné online.
 Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0201441241
 DingZhu Du, KerI Ko: Theory of Computational Complexity, 2nd Edition, Wiley 2014, ISBN: 9781118306086
 Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1850322430
Syllabus of lectures
 Introduction. Complexity, time and space complexity.
 Matematical models of computation, RAM, RASP machines and their relation with Turing machines.
 Asymptotic estimations, complexity classes, determinism and nondeterminism from the point of view of complexity.
 Relation between time and space, closure of complexity classes w.r.t. complementation, proper inclusion of complexity classes.
 Blum theorem. Gap theorem.
 Reduction, notion of complete problems, well known examples of complete problems.
 Classes P and NP. NPcomplete problems. SAT problem.
 Travelling salesman problem, Knapsack problem and other important NPcomplete problems
 NP optimization problems and their deterministic solution: pseudopolynomial algorithms, parametric complexity
 Approximation algorithms.
 Probabilistic algorithms, probabilistic complexity classes.
 Complexity and cryptography
 PSPACEcomplete problems. Complexity and formal verification.
Syllabus  others, projects and individual work of students
3 projects dedicated on different aspects of the complexity theory.
Progress assessment
 3 projects  10 points each (recommended minimal gain is 15 points)

Final exam is performed in written form. The maximal amount of points one can get is 70 points
Schedule
Day  Type  Weeks  Room  Start  End  Capacity  Lect.grp  Groups  Info 

Mon  lecture  1., 2., 3., 4., 5., 6., 8., 9., 10. of lectures  A112  11:00  12:50  64  1EIT 1MIT 2EIT 2MIT INTE  NMAT xx  Rogalewicz 
Mon  lecture  7., 11., 12. of lectures  A112  11:00  12:50  64  1EIT 1MIT 2EIT 2MIT INTE  NMAT xx  Lengál 
Mon  lecture  20250505  A112  11:00  12:50  64  1EIT 1MIT 2EIT 2MIT INTE  NMAT xx 
Course inclusion in study plans
 Programme MITEN (in English), any year of study, CompulsoryElective group B
 Programme MITAI, field NADE, NBIO, NCPS, NEMB, NEMB, NGRI, NHPC, NIDE, NISD, NISY, NISY up to 2020/21, NMAL, NNET, NSEC, NSEN, NSPE, NVER, NVIZ, any year of study, Elective
 Programme MITAI, field NMAT, any year of study, Compulsory