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 seminar

Course Materials

Summary Problem list
Complexity classes P, PSPACE, EXP. Time and space hierarchy theorems (see also Sipser Section 9.1) Problem list 1 Updated: 11.09.17
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


Send homework assignments by email to posobin+hw[at], or submit them in person to one of the teachers or the teaching assistant (Gleb Posobin) before the deadline.

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