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

Версия от 07:51, 11 сентября 2017

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

@@ Строка 10: / Строка 10: @@
 ! 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]
+  || 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 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]