Theory of Computation 2022 — различия между версиями
м |
Bbauwens (обсуждение | вклад) |
||
Строка 42: | Строка 42: | ||
|| 12.09 || Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/jqz33aqwfl992tc/prob_2.pdf?dl=0 Problem set 2] | || 12.09 || Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/jqz33aqwfl992tc/prob_2.pdf?dl=0 Problem set 2] | ||
|- | |- | ||
− | + | || 19.09 || Because of various problems, the materials of last 2 weeks were repeated. || [https://www.dropbox.com/s/05iiwsdpggfjuul/prob_3.pdf?dl=0 Problem set 3] <span style="color:red">update 19.09</span> | |
− | || [https://www.dropbox.com/s/05iiwsdpggfjuul/prob_3.pdf?dl=0 Problem set 3] | + | |
|- | |- | ||
− | || 26.09 || | + | || 26.09 || Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness. || |
|- | |- | ||
− | || 3.10 || | + | || 3.10 || Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. || |
|- | |- | ||
− | || 10.10 || P | + | || 10.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.|| |
|- | |- | ||
− | || 17.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. || | + | || 17.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. || |
+ | |- | ||
+ | || 31.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. || | ||
|- | |- | ||
− | || | + | ||07.11 || PSPACE completeness of generalized geography. Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || |
|- | |- | ||
− | || | + | || 14.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. Most of it is also [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| |
|- | |- | ||
− | || | + | || 21.11 || Streaming algorithms: finding the majority element, computation of the number of different elements <!-- ''F''<sub>2</sub>--> in logarithmic space. See Chapts 6.1-6.2 in [https://home.ttic.edu/~avrim/book.pdf foundations of datascience] by Avrim Blum and others. Another nice chapter in [http://theory.stanford.edu/~tim/w15/l/l1.pdf Tim Roughgarden's lecture notes] || |
|- | |- | ||
− | || | + | || 28.11 || Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. |
|- | |- | ||
− | || | + | || 05.12 || Colloquium. || |
− | + | ||
|- | |- | ||
− | + | || 12.12 || Approximation algorithms and complexity of clustering [https://www.dropbox.com/s/wvtcsl6crkj8zeq/tc-12-approximation.pdf?dl=0 Slides.] | |
− | + | ||
− | || 12.12 || | + | |
|| [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] | || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] | ||
|} | |} | ||
− | For interested students, | + | For interested students: parameterized complexity. We review topics from chapters 1, 2, 3, 13 in "Parameterized algorithms" by Cygan, Fomin and others, 2016. |
+ | |||
+ | 19 Sept: Fixed parameter tracktability and examples. Kernels. [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. | ||
− | + | 26 Sept: exercises on chapters 2 and 3, treewidth | |
− | + | 3 Oct: The W-hierarchy, chapter 13 in the same book. | |
− | |||
= Office hours = | = Office hours = | ||
− | Bruno Bauwens: | + | Bruno Bauwens: Mondays 14h-20h. Fridays 18h-20h. Also on Tuesdays, but warn ahead: brbauwens -a- gmail.com |
Alexey Talambutsa: First contact by email. | Alexey Talambutsa: First contact by email. |
Версия 21:29, 19 сентября 2022
Содержание
Classes
Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa
Seminars: Monday 14:40 - 16:00 by Pavel Zakharov
Dates and Deadlines
Homeworks 1, 2, 3: September 26
Homeworks 4, 5: October 10
Homeworks 6, 7, 8: November 7
Homeworks 9, 10, 11: November 28
Grading
Colloquium: 35%
Homework: 35%
Exam: 30%
Homework Grading
Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems.
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10.
If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
Summary | Problem list | |
---|---|---|
05.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem set 1 |
12.09 | Time and space hierarchy theorems. Time and space constructible functions. | Problem set 2 |
19.09 | Because of various problems, the materials of last 2 weeks were repeated. | Problem set 3 update 19.09 |
26.09 | Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness. | |
3.10 | Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. | |
10.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. | |
17.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. | |
31.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. | |
07.11 | PSPACE completeness of generalized geography. 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. | |
14.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. Most of it is also here | |
21.11 | Streaming algorithms: finding the majority element, computation of the number of different elements in logarithmic space. See Chapts 6.1-6.2 in foundations of datascience by Avrim Blum and others. Another nice chapter in Tim Roughgarden's lecture notes | |
28.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. | |
05.12 | Colloquium. | |
12.12 | Approximation algorithms and complexity of clustering Slides. | Sample exam |
For interested students: parameterized complexity. We review topics from chapters 1, 2, 3, 13 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
19 Sept: Fixed parameter tracktability and examples. Kernels. presentation.
26 Sept: exercises on chapters 2 and 3, treewidth
3 Oct: The W-hierarchy, chapter 13 in the same book.
Office hours
Bruno Bauwens: Mondays 14h-20h. Fridays 18h-20h. Also on Tuesdays, but warn ahead: brbauwens -a- gmail.com
Alexey Talambutsa: First contact by email.