27
правок
Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{DTIME(f(n))} = \{ L \mid \exists </tex> детерминированная программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{T(p,x)} = O(f(n)) \}</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE(f(n))} = \{ L \mid \exists </tex> детерминированная программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{S(p,x)} = O(f(n)) \}</tex>.
}}
