165
правок
Изменения
→Формулировка
Пусть можно просимулировать <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>, выполняется <tex>'''DTIME'''(''g''(''n'')) \&ne ; '''DTIME'''(''f''(''n''))</tex>.
== Доказательство ==
