Изменения

Перейти к: навигация, поиск

Класс PS

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

Навигация