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