Теорема Шамира

Формулировка

IP = PS

Доказательство

1. [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].

1. [math]PS \subset IP[/math]