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