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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
! Summary !! Problem list
 
! Summary !! Problem list
 
|-
 
|-
  || Complexity classes P, PSPACE, EXP. Time and space hierarchy theorems (see also Sipser Section 9.1) || [https://www.dropbox.com/s/e4lwwl649sdnwbe/prob_1.pdf?dl=0 Problem list 1] <span style="color:red">Updated: 11.09.17</span>
+
  || Complexity classes P, PSPACE, EXP. Time and space hierarchy theorems (see also Sipser Section 9.1) || [http://www.mi.ras.ru/~podolskii/files/computability/prob_1.pdf Problem list 1] <span style="color:red">Updated: 11.09.17</span>
 
|-
 
|-
 
  || 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.  || [http://www.mi.ras.ru/~podolskii/files/computability/prob_2.pdf Problem list 2]
 
  || 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.  || [http://www.mi.ras.ru/~podolskii/files/computability/prob_2.pdf Problem list 2]

Версия 10:53, 11 сентября 2017

General Information

Grading

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

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
3
Gleb Posobin