Викиконспекты - Вклад участника [ru]

Теорема о временной иерархии

2010-03-14T19:34:38Z

Fedor: /* Формулировка */

== Формулировка ==
'''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <math>f\,\!</math> и <math>g\,\!</math> таких, что <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, выполняется <math>DTIME(g(n)) \ne DTIME(f(n))</math>.
== Доказательство ==
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.

Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, работая не более <math> f(|<m,x>|)\,\!</math> времени <math>\}\,\!</math> .

Пусть <math>L \in DTIME(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.

Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.

Пусть <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>. Тогда <math><m_0,x> \in L</math>, в силу определения <math>m_0\,\!</math>. Но в <math>L</math> по определению не может быть пары <math><m_0,x>\,\!</math>, которую допускает <math>m_0\,\!</math>, так как <math>m_0 \in DTIME(f)</math>. Таким образом, получаем противоречие.

Если <math>m_0\,\!</math> не допускает <math><m_0,x>\,\!</math>, то <math><m_0,x>\,\!</math> не принадлежит языку <math>L\,\!</math>. Это значит, что либо <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>, либо не допускает, работая больше времени <math>f(|<m_0,x>|)\,\!</math>. Но <math>L \in DTIME(f)</math>, поэтому <math>m_0\,\!</math> на любом входе <math>x\,\!</math> работает не более <math>f(|x|)\,\!</math> времени. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, <math>L \notin DTIME(f)</math>.

<math>L \in DTIME(g)</math>, так как можно просимулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина работает не более <math>f(|<m_3,x>|)\,\!</math> времени, а <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, <math>m_1\,\!</math> будет работать не более <math>g(|<m_3,x>|)\,\!</math> времени.

Получается, что <math>L \in DTIME(g(n)) \setminus DTIME(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DTIME(g(n)) \neq DTIME(f(n))</math>

Теорема доказана.

Конструируемая по времени функция

2010-03-14T08:14:31Z

Fedor: Новая страница: «== Определение == Функция <math>f(x)\,\!</math> называется конструируемой по времени, если за <math>t(n)\,\!…»

== Определение ==
Функция <math>f(x)\,\!</math> называется конструируемой по времени, если за <math>t(n)\,\!</math> времени можно симулировать <math>n\,\!</math> шагов <math>f(x)\,\!</math>, где <math>t(n)\,\!</math> некотороя функция, называемая скоростью симуляции.

Теорема о временной иерархии

2010-03-14T08:06:02Z

Fedor: Новая страница: «== Формулировка == '''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструи…»

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

2010-03-14T08:04:27Z

Fedor: /* Лекция 1 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[PS-полнота задачи Generalized geography]]

Класс DTIME

2010-03-14T08:03:40Z

Fedor: Новая страница: «== Определение == Классом <math>DTIME(f(n))\,\!</math> называется множество языков, для которых существ…»

== Определение ==

Классом <math>DTIME(f(n))\,\!</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.

<math>DTIME(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, T(m,x) \le f(|x|) \}</math>, где <math>|x|\,\!</math> <math>-\,\!</math> длина <math>x\,\!</math>.

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

2010-03-14T08:00:43Z

Fedor: /* Лекция 1 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[PS-полнота задачи Generalized geography]]