Изменения
Нет описания правки
'''[[Класс IP|IP]]''' = '''[[Класс PS|PS]]'''
== Доказательство ==
# <math>IP \subset PS</math>
Рассмотрим язык <math>L \in IP</math>. Чтобы детерменированная машина Тьюринга <math>m</math> могла установить принадлежность слова <math>x</math> языку <math>L</math>, ей нужно перебрать все ответы <math>P</math> и вероятностные ленты <math>V</math>, просимулировав <math>V</math> с этими данными. Ясно, что эти действия потребуют не более <math>p(|x|)</math> памяти, а значит <math>L \in PS</math>.
# <math>PS \subset IP</math>
