Изменения

Рассмотрим язык <tex>L \in \mathrm{IP}</tex>, а также . Пусть <tex>V</tex> {{---}} ''Verifier'' и , соответствующий <tex>L</tex>, <tex>p(n)</tex> {{---}} время его работы, <tex>f(n)</tex> {{---}} количество его запросов к ''Prover'''у. Напишем программу, соответствующие этому языкураспознающую язык <tex>L</tex> на полиномиальной памяти. Так как <tex>U(x)</tex> <tex>n \leftarrow |x|</tex> '''for'Verifier'' ограничен полиномиальным временем работы<tex>P \leftarrow Prover[f(n), то можно считатьp(n)]</tex> //(1) <tex>count \leftarrow 0</tex> '''for''' <tex>r \in \{0, что размер вероятностной ленты1\}^{p(n)}</tex> //(2) '''if''' <tex>V(x, размер ответов r)\bigm{|}_{P} = 1</tex> <tex>count</tex>++ '''Proverif'' 'а и количество дополнительной памяти, используемой <tex dpi = "160">\frac{count}{2^{p(n)}} \ge \frac{2}{3}</tex> '''return'Verifier'' 1 'ом тоже ограничены некоторым полиномом. Построим программу, которая будет перебирать все возможные вероятностные ленты и для каждой из них будет симулировать работу ''Verifierreturn'' 'а, перебирая 0 В цикле <tex>(1)</tex> перебираются все возможные ответы ''Prover'' 'аы, а затем вернет наиболее часто встречающийся результаткоторые отвечают на <tex>f(n)</tex> запросов, возвращаемый каждый ответ имеет размер <tex>p(n)</tex>. В цикле <tex>(2)</tex> перебираются все вероятностные ленты размера <tex>p(n)</tex>. Так как <tex>V</tex> {{---}} корректен, то если нашелся ''VerifierProver'' 'ом, при котором <tex>V</tex> допускает слово с вероятностью, большей <tex>\frac{2}{3}</tex>, то данное слово принадлежит <tex>L</tex>, иначе {{---}} не принадлежит. Данная Очевидно, что данная программа использует полиномиальное количество требует полином дополнительной памяти. Значит <tex>L \in \mathrm{PS}</tex>. Поэтому , следовательно <tex>\mathrm{IP} \subset \mathrm{PS}</tex>.