Изменения

|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не успеет сможет использовать памятьболее, размер которой превосходит чем полиномиальное значение. Тогда любой язык из количество памяти, следовательно <tex>L \mathrm{P}</tex> принадлежит <tex>in \mathrm{PS}</tex>.

|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, такой, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины, а для . Для этого необходим полиномиальный размер памяти. Тогда любой язык из Из этого следует, что <tex>L \mathrm{NP}</tex> принадлежит <tex>in \mathrm{PS}</tex>.