On Tally Relativizations of $BP$-Complexity Classes
Shouwen Tang, Osamu Watanabe · SIAM Journal on Computing · 1989
It is known that $AM = BP \cdot NP$. Babai [Proc. 17th Annual ACM Symposium Theory of Computing, 1985, pp. 421–429] and Goldwasser and Sipser [Proc.18th Annual ACM Symposium on Theory of Computing, 1986, pp. 59–68] asked whether $BP \cdot NP{\text{ for almost every set }}B,A \in NP(B)\}$ is equal to $\{ A|$ . This question is still open. In this paper it is shown that (1) for every $k \geqq 0$ and every set $A,A \in BP \cdot \Sigma _k^P $ if and only if for almost every tally set , and (2) for every $k \geqq 0$ and almost every tally set $T,BP \cdot \Sigma _k^P (T) = \Sigma _k^P (T)$. From them are obtained some properties of the “BP-polynomial-time hierarchy” studied by Schoning [Proc. 2nd Annual Conference on Structure in Complexity Theory, 1987, pp. 2–8]. That is, the $BP$-polynomial-time hierarchy has the properties that are precisely parallel to those of the polynomial-time hierarchy. The proofs of these results provide examples of the use of properties of complexity classes specified by relativizations to obtain properties of unrelativized complexity classes.