Course details

# Complexity (in English)

SLOa Acad. year 2021/2022 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 space-constructive functions, typical examples of complexity classes. Properties of complexity classes: importance of determinism and non-determinism in the area of computational complexity, Savitch theorem, relation between non-determinism 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 NP-complete 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

Deputy Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Instructor

Course Web Pages

Subject specific learning outcomes and competences

Understanding theoretical and practical limits of arbitrary computational systems. Ability to use a selected methods for computationally hard problems.

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.

Why is the course taught

It is important to know that there exists tasks (often called problems), which can be hardly solved by computers. A technically correct algorithm for these hard tasks often does not work on real inputs. The goal of the course is to familiarize students with theory basics behind the classification of tasks to computationally feasible and (in general) infeasible. Moreover, the course introduce techniques for solving these hard tasks based on approximation and probabilistic algorithms as well as use of hard problems within cryptography.

Prerequisite kwnowledge and skills

Formal language theory and theory of computability on master level.

Study literature

- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
- Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Available online.
- 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
- Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
- 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, RAM, RASP machines and their relation with Turing machines.
- Asymptotic estimations, complexity classes, determinism and non-determinism 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. NP-complete problems. SAT problem.
- Travelling salesman problem, Knapsack problem and other important NP-complete problems
- NP optimization problems and their deterministic solution: pseudo-polynomial algorithms, parametric complexity
- Approximation algorithms.
- Probabilistic algorithms, probabilistic complexity classes.
- Complexity and cryptography
- PSPACE-complete 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: max. 70 points

Schedule

Course inclusion in study plans

- Programme IT-MSC-2, field MBI, MBS, MGM, MPV, MSK, any year of study, Elective
- Programme IT-MSC-2, field MGMe, any year of study, Compulsory-Elective group M
- Programme IT-MSC-2, field MIN, any year of study, Compulsory-Elective group B
- Programme IT-MSC-2, field MIS, 1st year of study, Elective
- Programme IT-MSC-2, field MMM, any year of study, Compulsory-Elective group L
- Programme MITAI, specialisation NADE, NBIO, NCPS, NEMB, NGRI, NHPC, NIDE, NISD, NISY, NMAL, NNET, NSEC, NSEN, NSPE, NVER, NVIZ, any year of study, Elective
- Programme MITAI, specialisation NMAT, any year of study, Compulsory
- Programme MIT-EN, any year of study, Elective