Automata and Computational Complexity

In the winter semester 2022/2023, I teach a course on automata and computational complexity for students of mathematics at master's level [NMMB415]. The lecture and practicals happen on Thursdays between 10:40 and 13:50 in room K2.

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
29. 9.	Architecture of modern computers. Representation of data in memory. CPU and its instructions (see an example). Operating systems and virtual memory. Tricks for faster execution: caching, pipelining, executing more instructions simultanously, jump prediction. Parallel machines: symmetric multi-processing, multi-core processors.	video notes-01
6. 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 0ⁿ1ⁿ. Variants of Turing machines: one-way-infinite tape, multiple tapes. Exercises: recognize binary strings with even number of 1s, reverse a binary string, add and multiply binary numbers.	video notes-02
13. 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-03
20. 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]. Arithmetic hierarchy, classes Σ_n, Π_n, and Δ_n, relationship with quantified formulas. Execution time and time complexity. Exercises: find reductions between languages L_halt, L_empty, L_total, L_eq, L_fin and their complements. Place these languages within the arithmetical hierarchy.	video notes-04
27. 10.	Missing proofs on arithmetical hierarchy. Power of multiple tapes: Ω(n²) lower bound for 1-tape machines deciding palindromes, reduction of k-tape to 1-tape machine in time O(T(n)²), 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.	video notes-05
3. 11.	Class NP and NP-completeness, Cook-Levin theorem. More reductions: Independent Set to SAT to 3-SAT to 3,3-SAT to 3D Matching, 3-SAT to 3-Coloring, SAT to Hamiltonian Path. Introduction to circuits. Exercises: 3D Matching to Zero-One Equations, Independent Set to Vertex Cover, E3,E3-SAT is always true.	video notes-06
10. 11.	Fix of Hamiltonian Path reduction. Detour: Combinatorial and Boolean circuits, 2-input Boolean gates are WLOG, question of uniformity. Problems in P have uniform families of polynomial-size circuits. Circuit-SAT and proof of Cook-Levin theorem. Class co-NP and testing tautologies. Landscape of NP, co-NP and related classes. Exercises: Boolean circuits (and their complexity) for operations with n-bit numbers: parity, equality, x>y, x+y, x*y.	video notes-07
17. 11.	No lecture today: Choose your holiday.
24. 11.	Non-deterministic Turing machines, class NTIME(f) and (re)definition of NP as NTIME(poly(n)). Space complexity: classes DSPACE(f), NSPACE(f), (N)PSPACE, (N)L, and (N)EXPTIME. The reachability method, bounds for REACH imply relationships between complexity classes. Composition of space-bounded machines. Savitch's theorem, PSPACE=NPSPACE.	video notes-08
1. 12.	Space complexity: QBF is PSPACE-complete. Intuition behind PSPACE. Alternating Turing machines, ATIME, ASPACE, AP=PSPACE. Polynomial hierarchy, Σ_k-SAT and Π_k-SAT, PH ⊆ PSPACE, collapse of PH. Immerman-Szelepcsényi theorem: NSPACE(f)=co-NSPACE(f). Inside P: classes L and NL, log-space reductions, REACH is NL-complete, circuit evaluation is P-complete. Exercises: If PH has a complete problem, then it collapses. If Π_k = Σ_k, then PH collapses. Log-space algorithms for binary addition, multiplication, counting of cycles in permutations, reachability in forests, distance in trees.	video notes-09
8. 12.	2-SAT: implication graphs, NL-completeness. Hierarchy theorems for deterministic space and time. Relativizing techniques cannot separate P from NP: there exist oracles A and B such that P[A]=NP[A] and P[B]≠NP[B].	video1 video2 notes-10
15. 12.	Circuit complexity: classes SIZE(f), upper and lower bounds for Boolean functions. Machines taking advice, classes DTIME(f)/g and P/poly. There are languages in EEXP \ P/poly. NP ⊆ P/poly implies collapse of PH (without proof). Randomized algorithms: probabilistic Turing machines, classes BPP, RP, co-RP, ZPP. Amplification of probability in RP and BPP. P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE, RP ⊆ NP, ZPP = RP ∩ co-RP. BPP ⊆ P/poly. Exercises: Testing matrix multiplication, x^Ty is an uniformly random bit for x fixed and y uniformly random (over Z₂).	video notes-11
22. 12.	Deterministic finite-state automata (DFAs) and regular languages. Pumping lemma. Non-deterministic automata (NFAs), ε-NFAs and their reduction to DFAs. Closure of regular languages on complement, intersection, union, concatenation, and iteration. Kleene's theorem. Bi-directional automata, DSPACE(1) and NSPACE(1) are the class of regular languages. Exercises: "binary integers divisible by 5" is regular, "word ends with `ara`, `bar`, or `baba`" is regular, "binary word contains the same number of 0s as 1s" is not regular, "`0`ⁿ for n square" is not regular.	video notes-12
5. 1.	Fine-grained complexity. Orthogonal vector hypothesis (OVH), exponential time hypothesis (ETH) and its strong version (SETH). OVH implies lower bounds for NFA acceptance. ETH implies lower bounds for dominating set. SETH implies OVH. OVH implies lower bounds for longest common subsequence (proof sketch).	video1 video2 video3 notes-13

Grading

To complete the course, you need to pass an exam and obtain class credit.

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. See the list of exam requirements.

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.

Sources

All lecture notes in one file
Previous run of this course (Michal Koucký, winter 2021), including notes in Czech
Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
Sanjeev Arora, Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press, 2008.
Christos Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
Martin Mareš: Úvod do automatů (automata theory, in Czech)
Karl Bringmann: Fine-Grained Complexity Theory – lecture notes