Изменения

Классом <mathtex>PS (PSPACE)\,\!</mathtex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<mathtex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </mathtex>, где <mathtex>m-\,\!</mathtex> детерминированная машина Тьюринга, <mathtex>S-\,\!</mathtex> расход памяти, <mathtex>|x|-\,\!</mathtex> длина <mathtex>x\,\!</mathtex>.

<mathtex> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</mathtex> == Связь класса ''PS'' с другими классами теории сложности == === ''P '' ∈ ''PS'' === === ''NP '' ∈ ''PS'' === === ''L '' ∈ ''P'' === == Класс ''NPS'' == Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.