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^{n}1^{n}.
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^{2}) 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. | 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 with of time 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 |
8. 12. | Plan: 2-SAT is NL-complete. Hierarchy theorems. |
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.
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.
Enrollment token for this course is 3119a42ba7f4
.
Sources
- 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)