Theory of computing, AMI — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
== General Information == | == General Information == | ||
− | Classes: Tuesdays, 13h00-16h00, room | + | Classes: Tuesdays, 13h00-16h00, for the room see [https://ruz.hse.ru/ruz/main ruz.hse.ru] |
First lecture September 8. | First lecture September 8. |
Версия 13:20, 9 сентября 2020
General Information
Classes: Tuesdays, 13h00-16h00, for the room see ruz.hse.ru
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. | Problem list 1 |
15.09 | Time and space hierarchy theorem. Time and 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 |