Theory of Computing
Материал из Wiki - Факультет компьютерных наук
Версия от 13:17, 1 декабря 2017; Vpodolskii (обсуждение | вклад)
Содержание
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
Homework 4 + Extra Problems deadline: December 17, 2017, 23:59 Moscow time
Colloquium
Date and time: December 11, 12:10
Room: TBA
Program
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. Version 25.11.17 | Problem list 11 Updated: 22.11.17 |
Property testing: connectedness of graphs (cont.) and testing of monotonicity. (See notes from the previous lecture.) | Problem list 12 |
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.
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 |