38
правок
Изменения
Нет описания правки
== Связь класса ''PS'' с другими классами теории сложности ==
=== ''P '' ∈ ⊂ ''PS'' ===
====Доказательство:====
Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.
=== ''NP '' ∈ ⊂ ''PS'' ===
====Доказательство:====
