Теорема Шамира — различия между версиями
| Строка 2: | Строка 2: | ||
'''[[Класс IP|IP]]''' = '''[[Класс PS|PS]]''' | '''[[Класс 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> | ||
