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

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

Пусть можно просимулировать [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], выполняется [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] \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]

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