== BPP входит в PS ==
Либо я слепой, либо ещё что-то, <tex>BPP \subset PP</tex> (так как <tex>\forall p \forall x P(p(x) = [x \in L]) \geq \frac 2 3 \Rightarrow P(p(x) = [x \in L]) > \frac 1 2</tex>). Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не нашёл. Доказываетсяболее чем полиномиальное количество вероятностных бит, наверное, несложно, но мне лень думатьтак как сама работает за полиномиальное время.{Тогда программа для <tex>\mathrm{TODO|t=ЗАПИЛИТЬ}PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
== Интерактивное доказательство для GNI ==
