6
правок
Изменения
Новая страница: «== Формулировка == '''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструи…»
== Формулировка ==
'''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <math>f\,\!</math> и <math>g\,\!</math> таких, что <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, выполняется <math>DTIME(g(n)) \ne DTIME(f(n))</math>.
'''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <math>f\,\!</math> и <math>g\,\!</math> таких, что <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, выполняется <math>DTIME(g(n)) \ne DTIME(f(n))</math>.
