1632
правки
Изменения
м
=== Вывод ===
rollbackEdits.php mass rollback
Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <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>.
