Изменения

<tex>\mathrm{T(p,x)}</tex> — ограничение по времени.<tex>\mathrm{S(p,x)}</tex> — ограничение по памяти.<tex>\mathrm{TS(p,x)}</tex> — ограничение и по времени и по памяти.

Введём понятия <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>, аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму, а <tex>\mathrm{N}</tex> — недетерминизму).

<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>.

<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>.

Через понятия классов <tex>\mathrm{DSPACE}</tex>, <tex>\mathrm{DTIME}</tex>, <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].