Теория сложности (старая трешовая версия) — различия между версиями

Версия 23:18, 2 июня 2010

Лекция 1. Вводная

Начнем курс с введения понятий DTIME и DSPACE.

DTIME(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга , где [math]|x|[/math] — длина входа [math]x[/math].

DSPACE(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга .

Аналогичным образом введем классы NSPACE и NTIME, использующие недетерминированную машину Тьюринга взамен детерминированной (в течении всего курса префикс D соответствует детерминизму, а N — недетерминизму).

Рассмотрим и докажем теоремы о емкостной и временной иерархии.

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что , выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).

Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций [math]f\,\![/math] и [math]g\,\![/math] таких, что , выполняется DTIME(g(n)) ≠ DTIME(f(n)).

Через понятия классов DSPACE, DTIME, NSPACE и NTIME будет дано определение многим сложностным классам, в том числе P и NP.

Класс P — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально:

P=[math]\bigcup_{i=0}^{\infty}[/math]DTIME[math](in^i)[/math]

В свою очередь, при разрешении языка из класса NP используется недетерминированная машина:

NP=[math]\bigcup_{i=0}^{\infty}[/math] NTIME[math](in^i)[/math]

Дадим определение класса NP на языке сертификатов:

NP= (Первое равенство доказывается в статье NP)

Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка co-). Например, класс co-NP.

Практика 1

Сведение по Куку задачи факторизации к языку из NP

Лекция 2

Теорема Кука

Практика 2

Лекция 3

Практика 3

Практика, которой на самом деле не было

NP-полнота задачи о раскраске графа

Лекция 4

Лекция 5

Лекция 6

Практика 6

Лекция 7

Теорема Карпа-Липтона

Практика 7

Лекция 8

Практика 8

Лемма Шварца-Зиппеля

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13

Класс PCP

@@ Строка 23: / Строка 23: @@
 Дадим определение класса '''NP''' на языке сертификатов:
 *'''NP'''=<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex> (Первое равенство доказывается в статье '''[[NP]]''')
+Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка '''co-'''). Например, класс '''[[co-NP]]'''.
-*[[Класс co-NP]]
 *[[Сведение по Карпу]]
 *[[Сведение по Куку]]