Класс PS

2016-03-16T17:32:51Z

77.234.195.209: /* Класс NPS */

== Определение ==

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

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

== Альтернативное определение ==
<tex> 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 |^{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>.

Викиконспекты - Вклад участника [ru]

Класс PS