76
правок
Изменения
Нет описания правки
|statement=Пусть даны две функции <tex>f</tex> и <tex>g</tex> такие, <span title="Здесь Sim(n) — время симуляции n шагов одной машины Тьюринга на другой машине" style="border-bottom: 1px dotted; cursor: help;">что</span> <tex>\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0</tex>, тогда <tex>DTIME(f(n)) \neq DTIME(g(n))</tex>.
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]]. При этом в отличии от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение <tex>f</tex> и <tex>g</tex> поставлено более сильное условие.
Положим <tex>h(n)=Sim^{-1}(\frac{fg(n)g(n)}</tex>, где <tex>Sim^{Sim(f(n))-1})</tex> — обратная к времени симуляции функция, <tex>L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}</tex>. Заметим, что Тогда:* <tex>Sim(h(n))=oL \in DTIME(g(n))</tex> и , поскольку <tex>f(n)=oSim(h(n))</tex>. Тогда:* <tex>L \in DTIME(=g(n))</tex>, поскольку то есть запуск с ограничением <tex>T \leq h(|x|)</tex> осуществляется за <tex>O(g(n))</tex> времени;* <tex>L \notin DTIME(f(n))</tex> (доказывается аналогично соответствующему пункту предыдущей теоремыс учетом соотношения <tex>f(n)=o(h(n))</tex>).
}}
