Изменения

Классом <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(in^i*)</tex> == Связь класса ''PS'' с другими классами теории сложности == === ''P'' ⊆ ''PS'' =======Доказательство==== Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.  === ''NP'' ⊆ ''PS'' =======Доказательство==== Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex> Заметим также, что=== ''L'' ⊆ ''P'' =======Доказательство==== Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^i{c\log n}=poly(n) </tex> времени. === Вывод ===----<tex> L \subseteq P \subseteq NP \subseteq PS </tex> По [[Теорема о емкостной иерархии|теореме о емкостной иерархии]] <tex> L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. В настоящий момент общепринятая точка зрения, что все приведенные включения - строгие. == Класс ''NPS'' == Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью. В соответствии с [[Теорема Сэвича. Совпадение классов NPS и PS#Теорема Сэвича|теоремой Сэвича]] <tex>PS=NPS</tex>, поэтому обычно в теории сложности оперируют с классом <tex>PS</mathtex>.