editor
177
правок
Изменения
м
→Определение
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}poly} \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}poly} \mathrm{NSPACE}(p(n))</tex>.
}}
