zbMATH — the first resource for mathematics

A decisive characterization of BPP. (English) Zbl 0616.68049
The complexity class BPP (defined by J. Gill [SIAM J. Comput. 6, 675-695 (1977; Zbl 0366.02024)]) contains problems that can be solved in polynomial time with bounded error probability. A new and simple characterization of BPP is given. It is shown that a language L is in BPP iff (x\(\in L\to \exists^+y\forall zP(x,y,z))\wedge (x\not\in L\to \forall y\exists^+z\neg P(x,y,z))\) for a polynomial-time predicate P and for \(| y|,| z| \leq poly(| x|)\). The formula \(\exists^+yP(y)\) with the random quantifier \(\exists^+\) means that the probability Pr(\(\{\) \(y| P(y)\})\geq +\epsilon\) for a fixed \(\epsilon\). This characterization allows a simple proof that BPP\(\subseteq ZPP^{NP}\), which strengthens the result of C. Lautemann [Inf. Process. Lett. 17, 215-217 (1983; Zbl 0515.68042)] and M. Sipser [Proc. 15th Ann. ACM Symp. Theory of Computing, 330-335 (1983)] that BPP\(\subseteq \Sigma_ 2^ p\cap \Pi_ 2^ p\). Several other results about probabilistic classes can be proved using similar techniques, e.g. \(NP^ R\subseteq ZPP^{NP}\) and \(\Sigma_ 2^{p,BPP}=\Sigma_ 2^ p\).

68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
68W99 Algorithms in computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
94A60 Cryptography
Full Text: DOI