53
правки
Изменения
Нет описания правки
== Формулировка ==
Пусть можно просимулировать <tex>n</tex> шагов машины Тюринга на другой машине Тьюринга за время <tex>t(n)</tex>.
Для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <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>.
