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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Формулировка ==
 
== Формулировка ==
'''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} t(f(n))/g(n) = 0</tex>, выполняется <tex>DTIME(g(n)) \ne DTIME(f(n))</tex>.
+
Пусть можно просимулировать <tex>n</tex> шагов машины Тюринга на другой машине Тьюринга за время <tex>t(n)</tex>.
 +
 
 +
Для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <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'')).
  
 
== Доказательство ==
 
== Доказательство ==
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.
+
Зафиксируем <tex>f</tex> и <tex>g</tex>.
  
 
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)</tex> не допускает, работая не более <tex> f(| \langle m,x \rangle |)\,\!</tex> времени <tex>\}\,\!</tex> .
 
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)</tex> не допускает, работая не более <tex> f(| \langle m,x \rangle |)\,\!</tex> времени <tex>\}\,\!</tex> .
  
Пусть <tex>L \in DTIME(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0\,\!</tex> такая, что <tex>L(m_0)=L\,\!</tex>.
+
Пусть <tex>L \in DTIME(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L\,\!</tex>.
  
 
Рассмотрим <tex>m_0( \langle m_0,x \rangle )\,\!</tex>.  
 
Рассмотрим <tex>m_0( \langle m_0,x \rangle )\,\!</tex>.  
  
Пусть <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>. Таким образом, получаем противоречие.
+
Пусть <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\,\!</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> времени. Получаем противоречие.  
+
Если <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> времени. Получаем противоречие.  
  
 
Следовательно такой машины не существует. Таким образом, <tex>L \notin DTIME(f)</tex>.
 
Следовательно такой машины не существует. Таким образом, <tex>L \notin DTIME(f)</tex>.
  
<tex>L \in DTIME(g)</tex>. Возьмеме такую машину Тьюринга <tex>m_1\,\!</tex>, которой дается на вход пара <tex> \langle m_2,x \rangle  \in L</tex> и она симулирует нужное количество шагов машины <tex>m_2\,\!</tex> на входе <tex>x\,\!</tex>. Если <tex>m_2\,\!</tex> завершила работу и не допустила, то <tex>m_1\,\!</tex> допускает <tex> \langle m_2,x \rangle \,\!</tex>. В другом случае не допускает. <tex>L(m_1) = L</tex> и <tex>m_1</tex> будет работать не более <tex>g(| \langle m_2,x \rangle  |)\,\!</tex> времени.  
+
<tex>L \in DTIME(g)</tex>. Возьмем такую машину Тьюринга <tex>m_1</tex>, которой дается на вход пара <tex> \langle m_2,x \rangle  \in L</tex> и она симулирует <tex>f(| \langle m_2,x \rangle  |)</tex> шагов машины <tex>m_2</tex> на входе <tex>x</tex>. Если <tex>m_2</tex> завершила работу и не допустила, то <tex>m_1</tex> допускает <tex> \langle m_2,x \rangle </tex>. В другом случае не допускает. <tex>L(m_1) = L</tex> и <tex>m_1</tex> будет работать не более <tex>g(| \langle m_2,x \rangle  |)</tex> времени, так как по условию <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex>.  
  
 
Получается, что <tex>L \in DTIME(g(n)) \setminus DTIME(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DTIME(g(n)) \neq DTIME(f(n))</tex>
 
Получается, что <tex>L \in DTIME(g(n)) \setminus DTIME(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DTIME(g(n)) \neq DTIME(f(n))</tex>
  
 
Теорема доказана.
 
Теорема доказана.

Текущая версия на 19:06, 4 сентября 2022

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

Пусть можно просимулировать [math]n[/math] шагов машины Тюринга на другой машине Тьюринга за время [math]t(n)[/math].

Для любых двух конструируемых по времени функций [math]f\,\![/math] и [math]g\,\![/math] таких, что [math] \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0[/math], выполняется DTIME(g(n)) ≠ DTIME(f(n)).

Доказательство

Зафиксируем [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[/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] \langle m_2,x \rangle \in L[/math] и она симулирует [math]f(| \langle m_2,x \rangle |)[/math] шагов машины [math]m_2[/math] на входе [math]x[/math]. Если [math]m_2[/math] завершила работу и не допустила, то [math]m_1[/math] допускает [math] \langle m_2,x \rangle [/math]. В другом случае не допускает. [math]L(m_1) = L[/math] и [math]m_1[/math] будет работать не более [math]g(| \langle m_2,x \rangle |)[/math] времени, так как по условию [math] \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0[/math].

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

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