<p>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. </p>

<p>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.</p>

<p>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.</p>

<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.</p>

CC BY-SA 3.0
2013-12-07T16:30:16.087Z
Yeah, oracle separation seems pretty straightforward in both cases.
domotorp
CC BY-SA 4.0
2020-12-11T10:34:41.323Z
BPP is a class of languages, not of promise problems. The promise-Majority problem is not in BPP, but in promise-BPP.
Emil Jeřábek
CC BY-SA 4.0
2020-12-11T11:14:16.457Z
Note that [Fenner, Fortnow, Kurtz, Li](https://doi.org/10.1016/S0890-5401(03)00018-X) construct an oracle relative to which $\mathrm{P = BPP}$, but $\mathrm{promise\text-P\ne promise\text-BPP}$ (because $\mathrm{NP\ne MA}$).
Emil Jeřábek
CC BY-SA 3.0
2013-12-07T15:35:40.907Z
2013-12-07T15:35:40.907Z
Robin Kothari
<p>Regarding oracle separations, there is an oracle with EBPP = BPP = EXP<sup>NP</sup>, and an oracle with P=⊕P (and hence EBPP=P) and BPP=EXP<sup>NP</sup>.</p>
<p>One construction of BPP=EXP<sup>NP</sup> oracle (including the one in <a href="https://en.wikipedia.org/wiki/BPP_(complexity)" rel="nofollow noreferrer">BPP wikipedia article</a>) is to choose a relativized EXP<sup>NP</sup> 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<sup>NP</sup>, 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).</p>
<p>The P=⊕P and BPP=EXP<sup>NP</sup> oracle is noted <a href="http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html" rel="nofollow noreferrer">here</a>.</p>
<p>In addition to being in BPP and in C<sub>=</sub>P, EBPP is in Mod<sub><span class="math-container">$p$</span></sub>P for odd <span class="math-container">$p$</span> 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.</p>
<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.</p>

CC BY-SA 4.0
2020-12-11T10:32:48.890Z
I don’t see how to “tweak that number” to get it in $\oplus\mathrm P$. How do you do that? The usual ways of “tweaking” the number of witnesses, such as taking Cartesian products or disjoint unions with something, amount to applying polynomial functions to the number of witnesses. Polynomials respect modular congruences, and as such their parity cannot be used to distinguish two numbers that are already congruent modulo a large power of 2 (i.e., $2^{n-2}$ and $3\cdot2^{n-2}$). I can see that $\mathrm{EBPP\subseteq Mod}_p\mathrm P$ for any *odd* prime $p$, but not for $p=2$.
Emil Jeřábek
CC BY-SA 4.0
2020-12-13T16:17:37.700Z
@EmilJeřábek Good point; I corrected my answer (I mistakenly thought that disjoint union would work).
Dmytro Taranovsky
CC BY-SA 4.0
2017-09-11T19:45:15.713Z
2020-12-13T16:17:00.190Z
2020-12-13T16:17:00.190Z
Dmytro Taranovsky
<p>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}}$</p>

<p>Your class $\EBPP$ is a special case of <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aC#cequalsp" rel="nofollow">$\CP$</a>. I think one way of defining $\CP$ is as follows (see Section 2 of <a href="http://mathcs.clarku.edu/~fgreen/papers/cep.pdf" rel="nofollow">this paper</a>). A language $L$ is in $\CP$ if there is a polynomial time verifier $V$ such that</p>

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

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

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

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

CC BY-SA 3.0
2013-12-06T23:34:17.850Z
It's also a special case of BPP.
Peter Shor 
CC BY-SA 3.0
2013-12-06T23:34:29.163Z
@argentpepper What you believe to be a special case of ${\bf C_=P}$ does not seem to be correct. All ${\bf C_=P}$ machines need to accept OR reject for all inputs. What you are describing is a categorical machine - semantic complexity class. It does not accept nor reject if the probability is 1/2? That cannot be a ${\bf C_=P}$ machine.
Tayfun Pay
CC BY-SA 3.0
2013-12-06T23:34:59.760Z
@PeterShor Exactly
Tayfun Pay
CC BY-SA 3.0
2013-12-09T06:28:43.220Z
@TayfunPay I do not think your comment makes sense. $C_{=}P$ is a set of languages, not machines, so there is no such thing as a $C_{=}P$ machine. argentpepper is right that EBPP is in fact a subset of $C_{=}P$. it's just that it's not clear whether this inclusion is helpful, especially since $C_{=}P$ is a powerful class
Sasho Nikolov
CC BY-SA 3.0
2013-12-09T20:02:42.093Z
Just providing another way of looking at the problem...
argentpepper
CC BY-SA 3.0
2013-12-10T02:22:58.803Z
@SashoNikolov, What do you mean that there is no such thing as a ${\bf C_{=}P}$ machine? Also, which of his definitions are you talking about? The first one? Or the Second one? Is the first definition even equal the second definition? In his first definition do you even need the second bullet? He thinks that both of his definitions are equal but in fact they are not.
Tayfun Pay
CC BY-SA 3.0
2013-12-10T03:47:51.290Z
@TayfunPay the first definition defines $\mathsf{C_{=}P}$, the second defined EBPP. he is just saying that languages $L$ that are in EBPP are also in $\mathsf{C_{=}P}$, because any verifier $V$ that satisfies the condition in the EBPP definition also satisfies the (weaker) condition in the $\mathsf{C_{=}P}$ definition.
Sasho Nikolov
CC BY-SA 3.0
2013-12-06T22:22:04.310Z
2013-12-06T22:22:04.310Z
argentpepper
<p>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?</p>

<p><strong>Motivation.</strong> 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 <a href="http://arxiv.org/abs/1105.4127" rel="noreferrer">http://arxiv.org/abs/1105.4127</a>) 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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-11-28T21:14:33.860Z
I guess you already realize this, but if you relax the constraint to accepting words in the language with probability $3/4 \pm \varepsilon$ for $\varepsilon \geq 1/\text{poly}(n)$ then the classes should be equal.
Huck Bennett
CC BY-SA 3.0
2013-11-30T05:00:22.850Z
@domotorp What is the motivation behind this question? What do you intend to do with this semantic complexity class? Do you see a way of using EBPP somewhere to prove a theorem? Can you elaborate?
Tayfun Pay
CC BY-SA 3.0
2013-11-30T05:07:25.353Z
Check out the paper "Probabilistic Complexity Classes and Lowness" by Uwe Schoning, 1989.
Tayfun Pay
CC BY-SA 3.0
2013-11-30T10:53:47.547Z
@Tayfun: I checked it out but could not find anything relevant. Could you be more specific?
domotorp
CC BY-SA 3.0
2013-12-07T17:09:18.433Z
@HuckBennett: or even $3/4\pm\epsilon$ for $\epsilon\geq \exp(-\mathrm{poly}(n))$.
Colin McQuillan
CC BY-SA 3.0
2014-05-25T16:53:47.340Z
@domotorp: Did you find a good answer to this question? EBPP seems like an interesting class. (And also one-sided error analogs like ERP and co-ERP.)
Robin Kothari
CC BY-SA 3.0
2014-05-25T18:08:44.860Z
@Robin: Nope and eventually I did not think more about the problem. But I am still interested in it, so let me know if you have any related ideas.
domotorp
<cc.complexity-theory><complexity-classes><randomized-algorithms>
In what class are randomized algorithms that err with exactly 25% chance?
domotorp
# In what class are randomized algorithms that err with exactly 25% chance?

(Asked by: username_0 on 2013-11-28)

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.

**Tags:** cc.complexity-theory, complexity-classes, randomized-algorithms
> **Comments:**
> **username_1**: I guess you already realize this, but if you relax the constraint to accepting words in the language with probability $3/4 \pm \varepsilon$ for $\varepsilon \geq 1/\text{poly}(n)$ then the classes should be equal.  
> **username_2**: @domotorp What is the motivation behind this question? What do you intend to do with this semantic complexity class? Do you see a way of using EBPP somewhere to prove a theorem? Can you elaborate?  
> **username_2**: Check out the paper "Probabilistic Complexity Classes and Lowness" by Uwe Schoning, 1989.  
> **username_0**: @Tayfun: I checked it out but could not find anything relevant. Could you be more specific?  
> **username_3**: @HuckBennett: or even $3/4\pm\epsilon$ for $\epsilon\geq \exp(-\mathrm{poly}(n))$.  
> **username_4**: @domotorp: Did you find a good answer to this question? EBPP seems like an interesting class. (And also one-sided error analogs like ERP and co-ERP.)  
> **username_0**: @Robin: Nope and eventually I did not think more about the problem. But I am still interested in it, so let me know if you have any related ideas.  

---

## 3 answers

### Answer by username_4 on 2013-12-07. Score: 11

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.

> **Comments:**
> **username_0**: Yeah, oracle separation seems pretty straightforward in both cases.  
> **username_5**: BPP is a class of languages, not of promise problems. The promise-Majority problem is not in BPP, but in promise-BPP.  
> **username_5**: Note that [Fenner, Fortnow, Kurtz, Li](https://doi.org/10.1016/S0890-5401(03)00018-X) construct an oracle relative to which $\mathrm{P = BPP}$, but $\mathrm{promise\text-P\ne promise\text-BPP}$ (because $\mathrm{NP\ne MA}$).  

---

### Answer by username_6 on 2017-09-11. Score: 2

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

One construction of BPP=EXPNP oracle (including the one in [BPP wikipedia article](https://en.wikipedia.org/wiki/BPP_(complexity))) is to choose a relativized EXPNP 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=EXPNP, 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=EXPNP oracle is noted [here](http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html).

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.

> **Comments:**
> **username_5**: I don’t see how to “tweak that number” to get it in $\oplus\mathrm P$. How do you do that? The usual ways of “tweaking” the number of witnesses, such as taking Cartesian products or disjoint unions with something, amount to applying polynomial functions to the number of witnesses. Polynomials respect modular congruences, and as such their parity cannot be used to distinguish two numbers that are already congruent modulo a large power of 2 (i.e., $2^{n-2}$ and $3\cdot2^{n-2}$). I can see that $\mathrm{EBPP\subseteq Mod}_p\mathrm P$ for any *odd* prime $p$, but not for $p=2$.  
> **username_6**: @EmilJeřábek Good point; I corrected my answer (I mistakenly thought that disjoint union would work).  

---

### Answer by username_7 on 2013-12-06. Score: 1

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$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aC#cequalsp). I think one way of defining $\CP$ is as follows (see Section 2 of [this paper](http://mathcs.clarku.edu/~fgreen/papers/cep.pdf)). 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}$.

> **Comments:**
> **username_8**: It's also a special case of BPP.  
> **username_2**: @argentpepper What you believe to be a special case of ${\bf C_=P}$ does not seem to be correct. All ${\bf C_=P}$ machines need to accept OR reject for all inputs. What you are describing is a categorical machine - semantic complexity class. It does not accept nor reject if the probability is 1/2? That cannot be a ${\bf C_=P}$ machine.  
> **username_2**: @PeterShor Exactly  
> **username_9**: @TayfunPay I do not think your comment makes sense. $C_{=}P$ is a set of languages, not machines, so there is no such thing as a $C_{=}P$ machine. argentpepper is right that EBPP is in fact a subset of $C_{=}P$. it's just that it's not clear whether this inclusion is helpful, especially since $C_{=}P$ is a powerful class  
> **username_7**: Just providing another way of looking at the problem...  
> **username_2**: @SashoNikolov, What do you mean that there is no such thing as a ${\bf C_{=}P}$ machine? Also, which of his definitions are you talking about? The first one? Or the Second one? Is the first definition even equal the second definition? In his first definition do you even need the second bullet? He thinks that both of his definitions are equal but in fact they are not.  
> **username_9**: @TayfunPay the first definition defines $\mathsf{C_{=}P}$, the second defined EBPP. he is just saying that languages $L$ that are in EBPP are also in $\mathsf{C_{=}P}$, because any verifier $V$ that satisfies the condition in the EBPP definition also satisfies the (weaker) condition in the $\mathsf{C_{=}P}$ definition.  

---

