38
правок
Изменения
→Вывод
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>
По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - — строгое.
== Класс ''NPS'' ==
Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
