Theory of Computing 2019 2020 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| (не показано 8 промежуточных версии этого же участника) | |||
| Строка 11: | Строка 11: | ||
Homework 1, deadline: 4 October, before the lecture <br> | Homework 1, deadline: 4 October, before the lecture <br> | ||
Homework 2, deadline: 8 November, before the lecture <br> | Homework 2, deadline: 8 November, before the lecture <br> | ||
| − | Homework 3, deadline: | + | Homework 3, deadline: 8 December, <span style="color:red">2 days extension</span> |
| − | + | ||
| − | + | ||
| − | <span style="color:red"> | + | |
| − | + | ||
| − | + | ||
== Colloquium == | == Colloquium == | ||
| Строка 22: | Строка 17: | ||
Date and time: December 13, 15:10<br> | Date and time: December 13, 15:10<br> | ||
Room: R405<br> | Room: R405<br> | ||
| − | [https://www.dropbox.com/s/rbjd1hsuhtbmvzq/col.pdf?dl=0 Program] | + | [https://www.dropbox.com/s/rbjd1hsuhtbmvzq/col.pdf?dl=0 Program] <span style="color:red">Updated: 11.12.19 (question 7 of part 2 is removed)</span> |
== Course Materials == | == Course Materials == | ||
| Строка 61: | Строка 56: | ||
|| [https://www.dropbox.com/s/zn0nn6rzxvyjtwd/prob_11.pdf?dl=0 Problem list 11] <span style="color:red">Updated HW-problem: 22.11.19</span> | || [https://www.dropbox.com/s/zn0nn6rzxvyjtwd/prob_11.pdf?dl=0 Problem list 11] <span style="color:red">Updated HW-problem: 22.11.19</span> | ||
|- | |- | ||
| − | || 29/11 || | + | || 29/11 || Nondeterministic communication complexity. D(f) < O(N^0(f) N^1(f)). Deterministic complexity vs number of leafs in a protocol tree. Randomized communication complexity: definitions. Functions EQ, GT, MCE. Newman's theorem (only the statement) |
| − | || | + | || [https://www.dropbox.com/s/km4wkungoh0qplt/prob_12.pdf?dl=0 Problem list 12] |
|- | |- | ||
| − | || 6/12 || | + | || 6/12 || Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. |
| + | || [https://www.dropbox.com/s/daj8me2wtt7b5eg/prob_13.pdf?dl=0 Problem list 13] | ||
| + | |- | ||
| + | || 20/12 || Questions from students about exercises and homework. Poly time reductions on graphs and NP-completeness of Hamiltonion graphs. (If interested, one-shot complexity of the disjointness problem, this is not for the exam.) Solving [http://www.mi-ras.ru/~podolskii/files/computability1819/exam171222.pdf the exam of 2 years ago]. | ||
|| | || | ||
<!-- | <!-- | ||
| + | Lower bound for randomized 1-shot communication complexity of set disjointness, see Roughgarden's [http://theory.stanford.edu/~tim/w15/l/l2.pdf lecture notes]). </span> | ||
| + | |||
|- | |- | ||
|| 11/12 || Linear programming is in NP, NP-completeness of Hamiltonian path, TQBF as a game, PSPACE-completeness of generalized geography. Various other NP-complete problems. || [https://www.dropbox.com/s/cifs60rf6vpfn3i/prob_14.pdf?dl=0 Problem list 14] | || 11/12 || Linear programming is in NP, NP-completeness of Hamiltonian path, TQBF as a game, PSPACE-completeness of generalized geography. Various other NP-complete problems. || [https://www.dropbox.com/s/cifs60rf6vpfn3i/prob_14.pdf?dl=0 Problem list 14] | ||
|- | |- | ||
| − | || | + | ||---> |
|} | |} | ||
Текущая версия на 18:09, 18 декабря 2019
Содержание
General Information
Classes: Fridays, 15:10-18:00, R406
Dates and Deadlines
Homework 1, deadline: 4 October, before the lecture
Homework 2, deadline: 8 November, before the lecture
Homework 3, deadline: 8 December, 2 days extension
Colloquium
Date and time: December 13, 15:10
Room: R405
Program Updated: 11.12.19 (question 7 of part 2 is removed)
Course Materials
In the first 10 lectures, we follow Sipser's book "Introduction to the theory of computation" Chapters 7, 8, 9 (not Theorem 9.15), and Section 10.2.
If you need some background in math, consider these two sourses:
Lecure notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
| Date | Summary | Problem list |
|---|---|---|
| 06.09 | Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem list 1 Updated: 07.09.19 |
| 13.09 | Universal Turing machine. Space hierarchy theorem. Space constructable functions. | Problem list 2 |
| 20.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 list 3 |
| 27.09 | Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | Problem list 4 |
| 04.10 | NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG | Problem list 5 |
| 11.10 | NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT | Problem list 6 |
| 18.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 constructable s. | Problem list 7 |
| 01.11 | PSPACE-completeness of formula game and generalized geography. Oracle computation definitions. There exists a language A for which P^A = NP^A. | Problem list 8 |
| 08.11 | There is an oracle B such that P^B is not equal to NP^B. Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. | Problem list 9 |
| 15/11 | Streaming algorithms: finding the majority element, computation of the moment F_2 in logarithmic space, lower-bound for exact and probabilistic computation of F_0 using one-shot communication complexity. Roughgarden's lecture notes | Problem list 10 |
| 22/11 | Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Book: Nisan and Kushilevich: communication complexity, 1997 download | Problem list 11 Updated HW-problem: 22.11.19 |
| 29/11 | Nondeterministic communication complexity. D(f) < O(N^0(f) N^1(f)). Deterministic complexity vs number of leafs in a protocol tree. Randomized communication complexity: definitions. Functions EQ, GT, MCE. Newman's theorem (only the statement) | Problem list 12 |
| 6/12 | Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. | Problem list 13 |
| 20/12 | Questions from students about exercises and homework. Poly time reductions on graphs and NP-completeness of Hamiltonion graphs. (If interested, one-shot complexity of the disjointness problem, this is not for the exam.) Solving the exam of 2 years ago. |
For interested students: lecture notes on quantum computation
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Vladimir Podolskii, room S830 | |||||
| Bruno Bauwens, room S834 | 14-18h | 18-19h |
