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