Course detail

# Complexity

FIT-SLOaAcad. year: 2017/2018

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.

Supervisor

Department

Nabízen zahradničním studentům

Všech fakult

Learning outcomes of the course unit

Understanding theoretical and practical limits of arbitrary

computational systems. Ability to use a selected methods for

computationally hard problems.

Prerequisites

Formal language theory and theory of computability on master level.

Co-requisites

Not applicable.

Recommended optional programme components

Not applicable.

Recommended or required reading

- 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

- 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

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

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.

Language of instruction

English

Work placements

Not applicable.

Course curriculum

- 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 of lectures:**

**Syllabus - others, projects and individual work of students:**

4 projects dedicated on different aspects of the complexity theory.

Aims

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.

Specification of controlled education, way of implementation and compensation for absences

- 4 projects - 8 points each.
- Final exam: max. 68 points

Classification of course in study plans

- Programme IT-MGR-2 Master's
branch MBI , any year of study, summer semester, 5 credits, elective

branch MPV , any year of study, summer semester, 5 credits, elective

branch MGM , any year of study, summer semester, 5 credits, elective

branch MSK , any year of study, summer semester, 5 credits, elective

branch MBS , any year of study, summer semester, 5 credits, elective

branch MIN , any year of study, summer semester, 5 credits, compulsory-optional

branch MMM , any year of study, summer semester, 5 credits, compulsory-optional - Programme IT-MGR-1H Master's
branch MGH , any year of study, summer semester, 5 credits, recommended

- Programme IT-MGR-2 Master's
branch MIS , 1. year of study, summer semester, 5 credits, elective