Theory of Computing

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

General Information


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
Homework 3 + Extra Problems deadline: November 24, 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
Proof of Newman's theorem, distributional complexity and the characterization of public coin communication complexity, the discrepancy method. Problem list 9
Randomized communication complexity of IP. Streaming algorithms. Finding the majority element. Deciding whether there is a most frequent element is hard. One-sided probabilistic complexity of disjointness. Problem list 10 Updated: 22.11.17
Property testing: definitions, testing of halfplanes, sorted listed, connectedness of graphs, testing of linearity. Lecture notes. Complete rewrite: 20.11.17 Problem list 11 Updated: 22.11.17


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
Vladimir Podolskii 16:40–18:00, room 621
Bruno Bauwens 15:05–18:00, room 620 15:05–18:00, room 620