Теория сложности (старая трешовая версия)

Материал из Викиконспекты
Версия от 20:25, 2 июня 2010; Ulyantsev (обсуждение | вклад) (Лекция 1. Вводная)
Перейти к: навигация, поиск

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

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

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

Аналогичным образом введем классы NSPACE и NTIME, использующие недетерминированную машину Тьюринга взамен детерминированной (в течении всего курса префикс D соответствует детерминизму, а 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=[math]\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\}[/math] (Первое равенство доказывается в статье NP)


Практика 1

Лекция 2

Практика 2

Лекция 3

Практика 3

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

Лекция 5

Лекция 6

Практика 6

Лекция 7

Практика 7

Лекция 8

Практика 8

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13