Theory of Computation 2021
Tuesdays 14:40–17:40, ruz
Lectures: 14:40 in room M303 zoomlink 26/10
Seminars: 16:20 in room M302 zoomlink 26/10
Dates and Deadlines
Please send your homework by e-mail to both lecturers.
Homework 1, deadline: October 5, 14:00; the deadline for the extra problems is November 2, 14:00
Homework 2, deadline: November 2, 14:00
Homework 3, deadline: December 7, 14:00
Colloquium: December 7, 14:40–17:40
Some homework assignments contain extra problems. Let us call all other problems normal. The weight of each problem (whether normal or extra) in the overall homework grade is 8/n, where n is the total number of normal problems in all homework assignments. Partial credit is possible for some problems.
If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10.
|07.09||Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples (one, two). Time and space complexity. Complexity classes P, PSPACE, EXP.||Problem set 1|
|14.09||Time and space hierarchy theorem. Time and space constructible functions.||Problem set 2|
|21.09||Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.||Problem set 3|
|28.09||Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems.||Problem set 4|
|05.10||Inclusions between P, NP, and PSPACE. Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly.||Problem set 5|
|12.10||P is a subset of P/poly, Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT.||Problem set 6|
|26.10||Space complexity. Classes L, NL, PSPACE and NPSPACE. Directed Reachability is in SPACE(log^2 n). Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s.||Problem set 7|
|02.11||Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB.|
|09.11||Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly.|
|16.11||Streaming algorithms: finding the majority element, computation of the moment F2 in logarithmic space.|
|23.11||Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch.|
|30.11||Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP.|
|14.12||Complexity of clustering: an exact algorithm for maximising the inter-cluster distance and an approximate algorithm for minimising the intra-class distance.|
For interested students, there are 3 lectures in parameterized complexity.
14 Sept: Fixed parameter tracktability and examples, presentation.
21 Sept: Topics from chapters 1 and 2 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
28 Sept: The W-hierarchy, chapter 13 in the same book.
|Bruno Bauwens, S834, Zoom||14:00-20:00|
|Sergei Obiedkov, T915, Zoom||16:30–18:00||16:30–18:00|