Изменения

=== ''P'' ⊆ ''PS'' ===

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.