Теорема о временной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Доказательство)
(→‎Доказательство)
Строка 4: Строка 4:
 
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.
 
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.
  
−
Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, работая не более <math> f(|<m,x>|)\,\!</math> времени <math>\}\,\!</math> .
+
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)</tex> не допускает, работая не более <tex> f(| \langle m,x \rangle |)\,\!</tex> времени <tex>\}\,\!</tex> .
  
−
Пусть <math>L \in DTIME(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.
+
Пусть <tex>L \in DTIME(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0\,\!</tex> такая, что <tex>L(m_0)=L\,\!</tex>.
  
−
Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.  
+
Рассмотрим <tex>m_0( \langle m_0,x \rangle )\,\!</tex>.  
  
−
Пусть <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>. Таким образом, получаем противоречие.
+
Пусть <tex>m_0\,\!</tex> допускает <tex> \langle m_0,x \rangle \,\!</tex>. Тогда <tex> \langle m_0,x \rangle \in L</tex>, в силу определения <tex>m_0\,\!</tex>. Но в <tex>L</tex> по определению не может быть пары <tex> \langle m_0,x \rangle \,\!</tex>, которую допускает <tex>m_0\,\!</tex>, так как <tex>m_0 \in DTIME(f)</tex>. Таким образом, получаем противоречие.
  
−
Если <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> времени. Получаем противоречие.  
+
Если <tex>m_0\,\!</tex> не допускает <tex> \langle m_0,x \rangle \,\!</tex>, то <tex> \langle m_0,x \rangle ,\!</tex> не принадлежит языку <tex>L\,\!</tex>. Это значит, что либо <tex>m_0\,\!</tex> допускает <tex> \langle m_0,x \rangle \,\!</tex>, либо не допускает, работая больше времени <tex>f(| \langle m_0,x \rangle |)\,\!</tex>. Но  <tex>L \in DTIME(f)</tex>, поэтому <tex>m_0\,\!</tex> на любом входе <tex>x\,\!</tex> работает не более <tex>f(|x|)\,\!</tex> времени. Получаем противоречие.  
  
−
Следовательно такой машины не существует. Таким образом, <math>L \notin DTIME(f)</math>.
+
Следовательно такой машины не существует. Таким образом, <tex>L \notin DTIME(f)</tex>.
  
−
<math>L \in DTIME(g)</math>, так как можно просимулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары  <math><m_2,x> \in L</math> рассмотрим <math>m_2(<m_2,x>)\,\!</math>. Если <math>m_2\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_2,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина работает не более <math>f(|<m_2,x>|)\,\!</math> времени, а <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, <math>m_1\,\!</math> будет работать не более <math>g(|<m_2,x>|)\,\!</math> времени.  
+
<tex>L \in DTIME(g)</tex>. Возьмеме такую машину Тьюринга <tex>m_1\,\!</tex>, которой дается на вход пара <math><m_2,x> \in L</math> и она симулирует нужное количество шагов машины <tex>m_2\,\!</tex> на входе <tex>x\,\!</tex>. Если <tex>m_2\,\!</tex> завершила работу и не допустила, то <tex>m_1\,\!</tex> допускает <tex><m_2,x>\,\!</tex>. В другом случае не допускает. <tex>m_1\,\!</tex> будет работать не более <tex>g(|<m_2,x>|)\,\!</tex> времени.  
  
  
−
Получается, что <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>
+
Получается, что <tex>L \in DTIME(g(n)) \setminus DTIME(f(n))</tex> и <tex>L \neq \empty</tex>. Следовательно, <tex>DTIME(g(n)) \neq DTIME(f(n))</tex>
  
 
Теорема доказана.
 
Теорема доказана.

Версия 17:46, 18 марта 2010

Формулировка

Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций [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 = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)[/math] не допускает, работая не более [math] f(| \langle m,x \rangle |)\,\![/math] времени [math]\}\,\![/math] .

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

Рассмотрим [math]m_0( \langle m_0,x \rangle )\,\![/math].

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

Если [math]m_0\,\![/math] не допускает [math] \langle m_0,x \rangle \,\![/math], то [math] \langle m_0,x \rangle ,\![/math] не принадлежит языку [math]L\,\![/math]. Это значит, что либо [math]m_0\,\![/math] допускает [math] \langle m_0,x \rangle \,\![/math], либо не допускает, работая больше времени [math]f(| \langle m_0,x \rangle |)\,\![/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]\lt m_2,x\gt \in L[/math] и она симулирует нужное количество шагов машины [math]m_2\,\![/math] на входе [math]x\,\![/math]. Если [math]m_2\,\![/math] завершила работу и не допустила, то [math]m_1\,\![/math] допускает [math]\lt m_2,x\gt \,\![/math]. В другом случае не допускает. [math]m_1\,\![/math] будет работать не более [math]g(|\lt m_2,x\gt |)\,\![/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]

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_временной_иерархии&oldid=376»