Automata and Computational Complexity

In the winter semester 2026/2027, I teach a course on automata and computational complexity for students of mathematics at master's level [NMMB415]. The lecture and practicals happen on Tuesdays between 15:40 and 18:50 in room K3.

If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.

We have video recordings (links below), but some parts of the recordings are missing due to equipment failures.

date topics material
30. 9. Architecture of modern computers. Representation of data in memory. CPU and its instructions (see an example). High-level languages, compilers and interpreters. Operating systems and virtual memory. Tricks for faster execution: caching, pipelining, executing more instructions simultanously, branch prediction. notes video1 video2
7. 10. Towards a formal model of computation. Alphabets and strings. Turing machines, their syntax and semantics. Computable and partially computable functions and sets. Example: recognizing 0n1n. Variants of Turing machines: one-way-infinite tape, multiple tapes, randomized, with oracle, interactive.
Exercises: recognize binary strings with even number of 1s, reverse a binary string, add and multiply binary numbers. 		video notes
14. 10. Random access machines and their equivalence with Turing machines. Computable and partially computable sets, classes R and RE. Enumerable sets are equal to partially computable sets. Universal language and diagonal language.
Exercises: Monotonically enumerable sets are equal to computable sets. Both R and RE are closed under union and intersection. 		video notes
21. 10. Post's theorem. Further examples of non-decidable languages. Reductions, hardness and completeness. Non-decidability of semantic properties: Rice's theorem (without proof). Relative computability, R[A] and RE[A]. Arithmetical hierarchy, classes Σn, Πn, and Δn, relationship with quantified formulas (without proof).
Exercises: find reductions between languages Lhalt, Lempty, Ltotal, Leq, Lfin and their complements. Place these languages within the arithmetical hierarchy. 		video notes
28. 10. No lecture today: Choose your holiday.
4. 11. Plan: Execution time and time complexity. Power of multiple tapes: Ω(n2) lower bound for 1-tape machines deciding palindromes, reduction of k-tape to 1-tape machine in time O(T(n)2), reduction of k-tape to 2-tape machine in time O(T(n) log T(n)) [proof omitted]. Time complexity classes DTIME(f), P, DTIMEF(f), and PF. Polynomial-time reductions. Reduction of SAT to Independent Set.
Exercises: Reduction of 3-Coloring to SAT, Independent Set to Clique and back. 		notes

Grading

To complete the course, you need to pass an exam and obtain class credit (in any order).

The exam covers theory presented at the lecture: definitions, theorems, and their proofs. You are allowed to use a cheat sheet on a single A4 page, which you wrote (or typed) yourself.

To obtain credit, you need to solve homework exercises worth at least 100 points. There will be several exercise sets during the semester, worth at least 150 points in total. To submit solutions, please use the Postal Owl (use this link to enroll).

Sources

This page is maintained by Martin Mareš