1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(i*nin^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 |^{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</tex>.
