Теорема о временной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Формулировка == '''Теорема о временной иерархии''' утверждает, что для любых двух [[Конструи…»)
(нет различий)

Версия 11:06, 14 марта 2010

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

Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций [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].