Конструируемая по времени функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
Функция <tex>f(x)\,\!</tex> называется конструируемой по времени, если за <tex>t(n)\,\!</tex> времени можно симулировать <tex>n\,\!</tex> шагов <tex>f(x)\,\!</tex>, где <tex>t(n)\,\!</tex> некотороя функция, называемая скоростью симуляции.
+
Функция <tex>f(x)</tex> называется конструируемой по времени, если можно вычислить <tex>f(x)</tex> по <tex>x</tex> за время меньшее <tex>f(x)</tex>.

Версия 18:44, 18 марта 2010

Определение

Функция [math]f(x)[/math] называется конструируемой по времени, если можно вычислить [math]f(x)[/math] по [math]x[/math] за время меньшее [math]f(x)[/math].