Probabilistic complexity classes and lowness (Q1263979)

Following A. Selman one defines \(A\in P_{pos}(B)\) if and only if there is an oracle machine M working within polynomial time s.t. \(A=L(M^{(B)})\) and whenever \(X\subseteq Y\), then \(L(M^{(X)})\subseteq L(M^{(Y)})\). Similarly one defines \(A\in NP_{pos}(B)\). Furthermore, a class \({\mathcal C}\) is said to be closed under \(P_{pos}\) if \(A\in P_{pos}(B)\) and \(B\in {\mathcal C}\) implies \(A\in {\mathcal C}\). Similarly, closure under \(NP_{pos}\) is defined. For any class \({\mathcal C}\) the probabilistic class of BP\({\mathcal C}\) is defined as follows: \(A\in BP{\mathcal C}\) if and only if there exists a \(B\in {\mathcal C}\), an \(\epsilon >0\) and a polynomial p s.t. for all inputs x \[ (1)\quad \Pr ob[(x,y)\in B\quad \leftrightarrow \quad x\in A]\quad >\quad +\epsilon, \] where \(y\in \Sigma^{p(| x|)}\) is randomly chosen under uniform distribution. The first main result concerns probability amplification. Let \({\mathcal C}\) be closed under \(P_{pos}\) and \(A\in BP{\mathcal C}\). Then for any polynomial q there exists a set \(B\in {\mathcal C}^ s.\)t. (1) holds with \(1-2^{-q(n)}\) instead of \(+\epsilon\). This amplification of probability can even be strengthened to hold for initial segments: \[ \Pr ob[\bigwedge_{| x| \leq n}((x,y)\in B\quad \leftrightarrow \quad x\in A]>1-2^{-q(n)}. \] The second main result concerns a simulation of statements that hold with high probability by two alternating quantifiers as it is known from \(BPP\subseteq \Sigma^ P_ 2\cap \Pi^ P_ 2\). It is proved that BP\({\mathcal C}\subseteq coNP({\mathcal C})\) provided that \({\mathcal C}\) is closed under \(NP_{pos}\). For classes closed under \(NP_{pos}\) one can reach the stronger result \(x\in A\to \Pr ob((x,y)\in B)=1\), \(x\not\in A\to \Pr ob((x,y)\not\in B)>1-2^{-q(n)}\). Further results are: If \({\mathcal C}\) is closed under \(NP_{pos}\) and under disjoint union, then the assumption co\({\mathcal C}\subseteq BP{\mathcal C}\) implies \(\Sigma^ P_ n({\mathcal C})\subseteq PB{\mathcal C}\) for all \(n\geq 0\). For each \(k\geq 0\), \(\Sigma^ P_ 2(BP\Sigma^ P_ k)\subseteq \Sigma^ P_{k+2}\), and for all \(k\geq 1\), \(\Sigma^ P_ 2(BP\Sigma^ P_ k\cap BP\Pi^ P_ k)=\Sigma^ P_{k+1}\).