Introduction to Computational Complexity

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Theoretical Computer Science

Synopsis:

On-site lectures and tutorials supported by an e-learning platform with materials, streamed and recorded lectures, and proseminars. Emphasis is placed on active student engagement and discussion.

Requirements:

Knowledge of graph theory and graph algorithms in scope of BIE-AG1, as well as formal languages and non-determinism in scope of BIE-AAG is assumed. Knowledge from BIE-AG2 is beneficial.

Syllabus of lectures:

1. Deterministic Turing machines, computation, and the universal Turing machine.

2. Undecidability, the Halting problem, time complexity, class P, Time Hierarchy Theorem (without proof).

3. Nondeterministic Turing machines, computation, and the universal Turing machine; examples of computations; class NP.

4. Many-one reductions, NP-hardness and NP-completeness, Cooks theorem (without proof), examples of reductions (Independent Set, etc.).

5. Influence of numeric input strong and weak NP-hardness, pseudopolynomial algorithms (dynamic programming for the knapsack problem and related problems).

6. Space complexity, classes DSPACE and NSPACE, Savitchs theorem.

7. Solving hard problems using SAT solvers.

8. Solving hard problems using ILP solvers.

9. Mildly exponential algorithms for hard problems. Held-Karp algorithm. Use of the principle of multiple inclusion. Efficient recursive algorithms.

10. Approximation algorithms for hard problems. Examples for Vertex Cover using LP and for other problems such as k-Center.

11. FPT algorithms and kernelization for hard problems. Examples for Vertex Cover and possibly other problems.

12. Heuristic methods for tackling hard problems. Local Search and its variants. Metaheuristics.

13. Oracle Turing machines and the polynomial hierarchy.

Syllabus of tutorials:

1. Design of simple Turing machines

2. Restrictions on Turing machines, reducing the number of tapes

3. Design of non-deterministic Turing machines, characterization of the class NP

4. Design of polynomial-time reductions

5. Design of more advanced polynomial-time reductions

6. Design of pseudo-polynomial-time algorithms

7. Formulation of problems as SAT problems

8. Formulation of problems as ILP problems

9. Design of moderately exponential algorithms

10. Design of approximation algorithms

11. Design of FPT algorithms

12. Design of heuristic algorithms

Study Objective:

The aim of the course is to introduce students to the fundamental concepts of computability theory and the basics of complexity theory, particularly undecidability, NP-hardness, and NP-completeness. It also covers the fundamentals of space complexity. The course then presents various approaches to tackling hard computational problems in particular, SAT and ILP solvers, the design of mildly exponential algorithms, approximation algorithms, parameterized algorithms, and heuristics.

Study materials:

1. Arora, S., Barak, B: Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 0521424267.

2. Wigderson, A.: Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press, 2019. ISBN 9780691189130.

3. Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 052188473X.

Note:

This course is taught in Czech.

Further information:

bude doplněno

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master specialization Computer Security, in Czech, 2026 (compulsory course in the program)
• Master specialization Computer Systems and Networks, in Czech, 2026 (compulsory course in the program)
• Master specialization Computer Science, in Czech, 2026 (compulsory course in the program)
• Master specialization Programming Languages, in Czech, 2026 (compulsory course in the program)
• Master specialization Artificial Intelligence, in Czech, 2026 (compulsory course in the program)
• Master programme, for the phase of study without specialisation, ver. for 2026 and higher (compulsory course in the program)