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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лекция 1. Вводная)
(Лекция 1. Вводная)
Строка 14: Строка 14:
 
*[[Теорема о временной иерархии]] утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex>, выполняется '''DTIME'''(''g''(''n'')) &ne; '''DTIME'''(''f''(''n'')).
 
*[[Теорема о временной иерархии]] утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex>, выполняется '''DTIME'''(''g''(''n'')) &ne; '''DTIME'''(''f''(''n'')).
  
Через понятия классов '''[[DSPACE]]''', '''[[DTIME]]''', '''[[NSPACE]]''' и '''[[NTIME]]''' будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
+
Через понятия классов '''[[DSPACE]]''', '''[[DTIME]]''', '''[[NSPACE]]''' и '''[[NTIME]]''' будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.  
  
 +
*Класс '''P''' — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально: '''P'''=<tex>\bigcup_{i=0}^{\infty}</tex>'''[[DTIME]]'''<tex>(in^i)</tex>
 +
*В свою очередь, при разрешении языка из класса '''NP''' используется недетерминированная машина: '''NP'''=<tex>\bigcup_{i=0}^{\infty}</tex> '''NTIME'''<tex>(in^i)</tex>
  
 
*[[Класс co-NP]]
 
*[[Класс co-NP]]

Версия 20:04, 2 июня 2010

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

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

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

Через понятия классов 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]

Практика 1

Лекция 2

Практика 2

Лекция 3

Практика 3

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

Лекция 5

Лекция 6

Практика 6

Лекция 7

Практика 7

Лекция 8

Практика 8

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13