Изменения

<tex>\mathrm{T}(p,x)}</tex> — время работы программы р на входе х.}}{{Определение|definition=<tex>\mathrm{S}(p,x)}</tex> — объем памяти, требуемый программе р для выполнения на входе х.}} {{Определение|definition=<tex>\mathrm{TS}(f,g)}</tex> — класс языков, для которых существует детерминированная программа, разрешающая их с данными ограничениями времени и памяти.

<tex>\mathrm{DTIME}(f(n))} = \{ </tex> — класс языков <tex>L \mid \exists </tex> , для которых существует детерминированная программа <tex>p : L(p)=L</tex> и для любого <tex>x \forall xin L</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{T}(p,x)} = O(f(n)) \}</tex>.

<tex>\mathrm{DSPACE}(f(n))} = \{ </tex> — класс языков <tex>L \mid \exists </tex> , для которых существует детерминированная программа <tex>p : L(p)=L</tex> и для любого <tex>x \forall xin L</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{S}(p,x)} = O(f(n)) \}</tex>.