53
правки
Изменения
→Связь класса PS с другими классами теории сложности
Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>
Заметим также, что
=== ''L'' ⊆ ''P'' ===
====Доказательство====
