Theory of computing, AMI — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 36: | Строка 36: | ||
|- | |- | ||
|| 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. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || <!-- [https://www.dropbox.com/s/lxoenwqohopsoca/prob_1.pdf?dl=0 Problem list 1 ] ---> | ||
− | |||
− | |||
|- | |- | ||
+ | <span style="color:gray"> | ||
|| 13.09 || Universal Turing machine. Space hierarchy theorem. Space constructable functions. || | || 13.09 || Universal Turing machine. Space hierarchy theorem. Space constructable functions. || | ||
</span> | </span> |
Версия 14:50, 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. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | |
13.09 | Universal Turing machine. Space hierarchy theorem. Space constructable functions. |
|
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. | |
27.09 | Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
04.10 | NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG | |
11.10 | NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT | |
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. | |
01.11 | PSPACE-completeness of formula game and generalized geography. Oracle computation definitions. There exists a language A for which P^A = NP^A. | |
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. | |
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 | |
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 | |
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) | |
6/12 | Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. | |
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. |
|
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Sergei Obiedkov, room T915 | |||||
Bruno Bauwens, room S834 |