Theory of Computing — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м (Changed section about homeworks)
Строка 32: Строка 32:
 
  || Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Non-deterministic complexity. Communication complexity classes P, NP, coNP, intersection of NP and coNP.
 
  || Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Non-deterministic complexity. Communication complexity classes P, NP, coNP, intersection of NP and coNP.
 
  || [http://www.mi.ras.ru/~podolskii/files/computability/prob_7.pdf Problem list 7]
 
  || [http://www.mi.ras.ru/~podolskii/files/computability/prob_7.pdf Problem list 7]
 +
|-
 +
|| D(f)=O(N^0(f)N^1(f)). Randomized communication complexity, definitions. R(EQ)=O(1). N^1(f) vs. R^1(f). Newman's theorem, formulation.
 +
|| [http://www.mi.ras.ru/~podolskii/files/computability/prob_8.pdf Problem list 8]
 
|}
 
|}
  

Версия 22:34, 20 октября 2017

General Information

Grading

Dates and Deadlines

Homework 1 deadline: September 29, 2017, 23:59 AoE
Homework 1, Extra Problems deadline: October 6, 2017, before seminar
Homework 2 + Extra Problems deadline: November 3, 2017, before lecture

Course Materials

Summary Problem list
Complexity classes P, PSPACE, EXP. Time and space hierarchy theorems (see also Sipser Section 9.1) Problem list 1
Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Complexity class NEXP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. NP-completeness: CIRC-SAT, 3-SAT. Problem list 2
NP-completeness: NAE-3-SAT, Exactly-1-3-SAT, IND-SET, Subset-SUM, 3-COLORING. Problem list 3
Space complexity. Classes PSPACE and NPSPACE. Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) (additional material). Interpretation of PSPACE in terms of games. Problem list 4
Probabilistic computation. Probabilistic machines, the class BPP, prime testing and Carmichael numbers, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Problem list 5
Definition of Sigma_2 and Pi_2. BPP is in Sigma_2 and Pi_2. Computations with oracles, its simple properties. There are oracles A and B such that P^A is equal to NP^A and P^B is not equal to NP^B. Problem list 6 Updated: 07.10.17
Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Non-deterministic complexity. Communication complexity classes P, NP, coNP, intersection of NP and coNP. Problem list 7
D(f)=O(N^0(f)N^1(f)). Randomized communication complexity, definitions. R(EQ)=O(1). N^1(f) vs. R^1(f). Newman's theorem, formulation. Problem list 8

Homework

Send homework assignments via Dropbox (the link is in the telegram group chat), or submit them in person to one of the teachers or the teaching assistant (Gleb Posobin) before the deadline.

Homework results

Results for extra problems

Office hours

Person Monday Tuesday Wednesday Thursday Friday
1
Vladimir Podolskii 16:40–18:00, room 621
2
Bruno Bauwens 15:05–18:00, room 620 15:05–18:00, room 620