On bounded-probability operators and C\(_ =\)P (Q1313771)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On bounded-probability operators and C\(_ =\)P
scientific article

    Statements

    On bounded-probability operators and C\(_ =\)P (English)
    0 references
    0 references
    24 February 1994
    0 references
    \textit{S. Toda} and \textit{M. Ogiwara} [SIAM J. Comput. 21, No. 2, 316-328 (1992; Zbl 0755.68055)] showed that \(\text{PH} \subseteq \text{BP} \cdot \text{C}_ = \text{P}\); that is, the polynomial-time hierarchy is contained in \(\text{C}_ = \text{P}\) with arbitrarily low double-sided error probability. \textit{J. Tarui} [Proc. 8th Ann. Symp., STACS '91, Lect. Notes Comput. Sci. 480, 238-250 (1991; Zbl 0764.94026)] independently proved and improved this result to show that \(\text{PH} \subseteq \text{RP} \cdot \text{C}_ = \text{P}\); that is, the polynomial-time hierarchy is contained in \(\text{C}_ = \text{P}\) with one-sided error probability. This, together with the fact that PH is closed under complement, implies that \(\text{PH} \subseteq \text{ZP} \cdot \text{C}_ = \text{P}\); that is, the polynomial-time hierarchy is contained in \(\text{C}_ = \text{P}\) with zero-sided error probability. We prove that \(\text{BP} \cdot \text{C}_ = \text{P}= \text{RP} \cdot \text{C}_ = \text{P}\) which implies that \(\text{BP} \cdot \text{C}_ = \text{P} \cap \text{co-BP} \cdot \text{C}_ = \text{P}= \text{ZP} \cdot \text{C}_ = \text{P}\). Thus, \(\text{PH} \subseteq \text{BP} \cdot \text{C}_ = \text{P}\) implies that \(\text{PH} \subseteq \text{ZP} \cdot \text{C}_ = \text{P}\) in a straight forward fashion. Besides providing an alternate characterization of the classes \(\text{RP} \cdot \text{C}_ = \text{P}\) and \(\text{ZP} \cdot \text{C}_ = \text{P}\), our result shows that the improvement from double-sided error to zero-sided error can be attributed to the interesting interaction of the operator BP with \(\text{C}_ = \text{P}\). Furthermore, our result demonstrates that the RP operator can be as powerful as the BP operator in a nontrivial case.
    0 references
    computational complexity
    0 references
    probabilistic classes
    0 references
    polynomial-time hierarchy
    0 references

    Identifiers