Theory of Computation 2021
Tuesdays 14:40–17:40, ruz
Seminars: 16:20 in room M203, also streamed here
Dates and Deadlines
Please send your homework by e-mail to both lecturers.
Homework 1, deadline: October 5, 14:00
Homework 2, deadline: November 2, 14:00
Homework 3, deadline: December 7, 14:00
Colloquium: December 7, 14:40–17:40
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. Inclusions between P, NP and PSPACE. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties.||Problem set 3|
|28.09||Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems.|
|05.10||Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly.|
|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|