Класс PS

Определение

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

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

Альтернативное определение

[math] PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)[/math]

Связь класса PS с другими классами теории сложности

P ∈ PS

NP ∈ PS

L ∈ P

Класс NPS

Классом [math]NPS (NPSPACE)\,\![/math] называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.