Bachelor
2026/2027
Theory of Computation
ID 1160030
Type:
Elective course (Applied Mathematics and Information Science)
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
3 year, 1, 2 module
Open to:
students of one campus
Language:
English
ECTS credits:
5
Contact hours:
56
Course Syllabus
Abstract
The aim of computational complexity is to classify computational problems by their difficulty. Here, difficulty, is measured by various resources needed to provide answers, such as computation time, space, randomness, circuits sizes. In particular, we train to distinguish polynomial time solvable problems and NP-hard problems. The latter are believed to require exponential time for worst case instances, and hence, in applications, one needs to restate the problem, use heuristics, or optimize exhaustive searches. The latter, is studied theoretically in the field of parameterized complexity
Learning Objectives
- Know the parameterized complexity classes FPT, W[i], XP. Apply kernelization technique to obtain FPT-algorithms
- Know famous streaming algorithms, such as SpaceSaving, CountMinSketch to find the most frequent element
- Oracle computation and understand the diagonalization barrier in solving the P vs NP problem
- Prove that PSPACE = NPSPACE and that the TQBF problem is PSPACE complete
- Know the proof of the Cook-Levin theorem: 3SAT is NP-complete
Expected Learning Outcomes
- Definitions of Turing machines. Classes TIME(f(n)) and SPACE(f(n)). Time and space hierarchy theorems
- Definitions of the classes L, NL, P, NP, PSPACE, EXP, NEXP, EXPSPACE, BPP, RP, #P, and inclusions between them. Know some famous problems in these classes
- In particular, distinguishing between problems in P, that are NP-complete, and that are PSPACE-complete
Course Contents
- Computational models and resource bounds
- Nondeterminism, NP, and reductions
- The Cook–Levin theorem
- Time and space hierarchy theorems
- Space complexity and Savitch's theorem
- The Immerman–Szelepcsényi theorem
- PSPACE-completeness
- Boolean circuits and nonuniformity
- Circuit size and parallel computation
- The polynomial hierarchy
- Randomized computation
- The Sipser–Gács–Lautemann theorem
- Communication complexity
- Streaming algorithms and sketches
