Theory of computing, AMI — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
! Date !! Summary !! Problem list | ! Date !! Summary !! Problem list | ||
|- | |- | ||
| − | || 08.09 || Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || <!-- [https://www.dropbox.com/s/lxoenwqohopsoca/prob_1.pdf?dl=0 Problem list 1 ] --- | + | || 08.09 || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || <!-- [https://www.dropbox.com/s/lxoenwqohopsoca/prob_1.pdf?dl=0 Problem list 1 ] ---> |
| − | + | ||
|- | |- | ||
| − | || | + | || 15.09 || <span style="color:gray"> Time and space hierarchy theorem. Space constructable functions. </span> || |
|- | |- | ||
| − | || | + | || 22.09 || <span style="color:gray"> 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. </span> || |
|- | |- | ||
| − | || | + | || 29.09 || <span style="color:gray"> Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. </span> || |
|- | |- | ||
| − | || | + | || 06.10 || <span style="color:gray"> NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG </span> || |
|- | |- | ||
| − | || | + | || 13.10 || <span style="color:gray"> NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT </span> || |
|- | |- | ||
| − | || | + | || 20.10 || <span style="color:gray"> 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. </span> || |
|- | |- | ||
| − | || | + | || 03.11 || <span style="color:gray"> PSPACE-completeness of formula game and generalized geography. Oracle computation definitions. There exists a language A for which P^A = NP^A. </span> || |
|- | |- | ||
| − | || | + | || 10.11 || <span style="color:gray"> 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. </span> || |
|- | |- | ||
| − | || | + | || 17.11 || <span style="color:gray"> 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. [http://theory.stanford.edu/~tim/w15/l/l1.pdf Roughgarden's lecture notes] </span> |
|| | || | ||
|- | |- | ||
| − | || | + | || 24.11 || <span style="color:gray"> 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 [https://epdf.pub/communication-complexity.html download] </span> |
|| | || | ||
|- | |- | ||
| − | || | + | || 01.12 || <span style="color:gray"> 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) </span> |
|| | || | ||
|- | |- | ||
| − | || | + | || 08.12 || <span style="color:gray"> Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. </span> |
|| | || | ||
|- | |- | ||
| − | || | + | || 22.12 || <span style="color:gray"> Questions from students about exercises and homework. Poly time reductions on graphs and NP-completeness of Hamiltonion graphs. Solving [http://www.mi-ras.ru/~podolskii/files/computability1819/exam171222.pdf the exam of 2 years ago]. </span> |
|| | || | ||
<!-- | <!-- | ||
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]). | 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]). | ||
| − | |||
|- | |- | ||
|| 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] | ||
Версия 15:03, 31 августа 2020
General Information
Classes: Tuesdays, time?, room?
First lecture September 8.
Dates and Deadlines
Homework 1, deadline: 6 October, before the lecture
Homework 2, deadline: 3 November, before the lecture
Homework 3, deadline: 8 December, before the lecture
Course Materials
In the first 9 lectures, we follow Sipser's book "Introduction to the theory of computation" Chapters 3, 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 |
|---|---|---|
| 08.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | |
| 15.09 | Time and space hierarchy theorem. Space constructable functions. | |
| 22.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. | |
| 29.09 | Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
| 06.10 | NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG | |
| 13.10 | NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT | |
| 20.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. | |
| 03.11 | PSPACE-completeness of formula game and generalized geography. Oracle computation definitions. There exists a language A for which P^A = NP^A. | |
| 10.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. | |
| 17.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 | |
| 24.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 | |
| 01.12 | 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) | |
| 08.12 | Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. | |
| 22.12 | Questions from students about exercises and homework. Poly time reductions on graphs and NP-completeness of Hamiltonion graphs. Solving the exam of 2 years ago. |
|
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Sergei Obiedkov, room T915 | |||||
| Bruno Bauwens, room S834 |
