Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
== Определение ==
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{DSPACE}(p(n)) </tex>.
}}
{{Определение
|definition=<tex>\mathrm{NPS}</tex> <tex>\mathrm{(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{NSPACE}(p(n))</tex>.
}}
