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
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