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:

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:

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:

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)