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

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

Версия 17:33, 4 сентября 2018

General Information

Grading

Dates and Deadlines

Course Materials

Date Summary Problem list
3/9 Time and space hierarchy theorems (see also Sipser Section 9.1) Problem list 1
10/9 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.

In the first lectures, we follow Sipser's book Introduction to the theory of computation.