38
правок
Изменения
Нет описания правки
== Связь класса ''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> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
