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

Версия 19:25, 2 июня 2010

Содержание

1 Лекция 1. Вводная
2 Практика 1
3 Лекция 2
4 Практика 2
5 Лекция 3
6 Практика 3
7 Практика, которой на самом деле не было
8 Лекция 5
9 Лекция 6
10 Практика 6
11 Лекция 7
12 Практика 7
13 Лекция 8
14 Практика 8
15 Лекция 9
16 Лекция 10
17 Лекция 11
18 Лекция 12
19 Лекция 13

Лекция 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] машина Тьюринга , где [math]|x|[/math] — длина входа [math]x[/math].

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

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

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [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.

Практика 1

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

Лекция 2

Теорема Кука

Практика 2

Лекция 3

Практика 3

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

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

Лекция 5

Лекция 6

Практика 6

Лекция 7

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

Практика 7

Лекция 8

Практика 8

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

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13

Класс PCP

@@ Строка 1: / Строка 1: @@
 == Лекция 1. Вводная ==
-Начнем курс с введения понятий '''[[DSPACE]]''' и '''[[DTIME]]'''.
+Начнем курс с введения понятий '''[[DTIME]]''' и '''[[DSPACE]]'''.
 *'''DTIME'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Time(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.
@@ Строка 6: / Строка 6: @@
 *'''DSPACE'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.
-Аналогичным образом введем классы '''[[NSPACE]]''' и '''[[NTIME]]''', используя недетерминированную машину Тьюринга взамен детерминированной.
+Аналогичным образом введем классы '''[[NSPACE]]''' и '''[[NTIME]]''', использующие недетерминированную машину Тьюринга взамен детерминированной.
 Рассмотрим и докажем теоремы о емкостной и временной иерархии.
@@ Строка 15: / Строка 15: @@
 Через понятия классов '''[[DSPACE]]''', '''[[DTIME]]''', '''[[NSPACE]]''' и '''[[NTIME]]''' будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
 *[[Класс co-NP]]