In what class are randomized algorithms that err with exactly 25% chance?

Question

Suppose I consider the following variant of BPP, which let us call E(xact)BPP: A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/4 probability and every word not in the language with exactly 1/4 probability. Obviously EBPP is contained in BPP but are they equal? Has this been studied? What about the similarly definable ERP?

Motivation. My main motivation is that I wanted to know what the complexity theoretic analogue of the ``correct in expected value'' randomized algorithm of Faenza et al. (see http://arxiv.org/abs/1105.4127) would be. First I wanted to understand what decision problems such an algorithm can solve (with worst case polynomial running time). Let us denote this class by E(xpected)V(alue)PP. It is easy to see that USAT $\in$ EVPP. Also easy to see that EBPP $\subset$ EVPP. So this was my motivation. Any feedback about EVPP is also welcome.

In fact, their algorithm always outputs a nonnegative number. If we denote the decisions problems recognizable by such an algorithm by EVP(ositive)PP, then we still have USAT $\in$ EVPPP. While EBPP might not be a subset of EVPPP, we have ERP $\subset$ EVPPP. Maybe using these we can define a (nonnegative) rank for decision problems.

Answer 1

On a side note, it's not clear that EBPP is a robust class. For example, if instead of allowing the algorithm to flip an unbiased coin, if it were given an unbiased 3-sided coin, or a 6-sided die, it's not clear that you get the same class. BPP remains the same if you change these details.

Anyway, your primary question is whether EBPP is equal to BPP or not. It seems to me that EBPP is closer to P than it is to BPP. Consider the query complexity or oracle version of these classes where they have access to a large input string and have to make queries to learn bits of this string. If you have a P algorithm that computes a function $f$ with $Q$ queries, then there exists an exact representing polynomial of degree $Q$ for $f$ over $\mathbb{R}$. (This is the usual polynomial method argument.) On the other hand, if you have a BPP algorithm, then you get a degree $Q$ polynomial over $\mathbb{R}$ that approximates $f$ in the sense that its value is close to the value of $f$ at every input.

Given an EBPP algorithm for a function $f$, we can construct a polynomial that outputs 1/4 when the answer is NO and 3/4 when the answer is YES. By subtracting 1/2 and multiplying by 2, you can get an exact representing polynomial, just like in the case of P. This suggests to me that EBPP is closer to P.

This observation can also be used to show an oracle separation between EBPP and BPP. Consider the promise-Majority problem where you're promised that the input has either more than 2N/3 1s or less than N/3 1s and you have to decide which is the case. This is clearly in BPP. Using the polynomial argument described above it can be shown that this function requires $\Omega(N)$ queries for an EBPP machine. But note that you can also prove an oracle separation the other way, between P and EBPP. So maybe oracle results don't say much for this problem? Or maybe what they say is that it will be hard to show equality in either direction.

Answer 2

Regarding oracle separations, there is an oracle with EBPP = BPP = EXP^NP, and an oracle with P=⊕P (and hence EBPP=P) and BPP=EXP^NP.

One construction of BPP=EXP^NP oracle (including the one in BPP wikipedia article) is to choose a relativized EXP^NP complete problem, and proceeding recursively on the input size (for that problem), fix results for problem instances of that size, and then provide answers to that problem if queried with the input and a filler (of appropriate length) that has not been fixed. For EBPP=EXP^NP, instead of almost always giving the correct answers, we can give just enough wrong answers to make the counts exactly right. There is also an oracle in which the zero error analog of EBPP (exactly 1/2 probability of reporting failure) equals EXP (and an oracle with P=⊕P but ZPP=EXP).

The P=⊕P and BPP=EXP^NP oracle is noted here.

In addition to being in BPP and in C₌P, EBPP is in Mod_$p$P for odd $p$ since we can reduce probability to number of witnesses and then tweak that number. However, simple-minded tweaking does not seem to work for getting it in ⊕P.

In the unrelativized world, BPP probably equals P, but the evidence is even stronger for EBPP. EBPP depends on the exact number of paths in a way that, unless an unexpected cancellation holds, appears essentially impossible to harness.

Answer 3

This is a partial answer; maybe it will inspire someone else to provide a better one. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$

Your class $\EBPP$ is a special case of $\CP$. I think one way of defining $\CP$ is as follows (see Section 2 of this paper). A language $L$ is in $\CP$ if there is a polynomial time verifier $V$ such that

• if $x$ is in $L$, then $\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$, and
• if $x$ is not in $L$, then $\Pr_w[V(x, w) \text{ accepts}] \neq \frac{3}{4}$.

(The completeness probability can essentially be any fixed fraction; I chose $\frac{3}{4}$ so that it matches the probability given in your question.)

One way of defining $\EBPP$ is as follows. A language $L$ is in $\EBPP$ if there is a polynomial time verifier $V$ such that

• if $x$ is in $L$, then $\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$, and
• if $x$ is not in $L$, then $\Pr_w[V(x, w) \text{ accepts}] = \frac{1}{4}$.