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