17
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – Huck Bennett Nov 28 '13 at 21:14
  • 3
    $\begingroup$ @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? $\endgroup$ – Tayfun Pay Nov 30 '13 at 5:00
  • 1
    $\begingroup$ Check out the paper "Probabilistic Complexity Classes and Lowness" by Uwe Schoning, 1989. $\endgroup$ – Tayfun Pay Nov 30 '13 at 5:07
  • 1
    $\begingroup$ @Tayfun: I checked it out but could not find anything relevant. Could you be more specific? $\endgroup$ – domotorp Nov 30 '13 at 10:53
  • 2
    $\begingroup$ @HuckBennett: or even $3/4\pm\epsilon$ for $\epsilon\geq \exp(-\mathrm{poly}(n))$. $\endgroup$ – Colin McQuillan Dec 7 '13 at 17:09
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yeah, oracle separation seems pretty straightforward in both cases. $\endgroup$ – domotorp Dec 7 '13 at 16:30
1
$\begingroup$

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

In addition to being in BPP and in C=P, EBPP is in ⊕P since we can reduce probability to number of witnesses and then tweak that number.

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.

$\endgroup$
0
$\begingroup$

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}$.
$\endgroup$
  • 3
    $\begingroup$ It's also a special case of BPP. $\endgroup$ – Peter Shor Dec 6 '13 at 23:34
  • $\begingroup$ @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. $\endgroup$ – Tayfun Pay Dec 6 '13 at 23:34
  • $\begingroup$ @PeterShor Exactly $\endgroup$ – Tayfun Pay Dec 6 '13 at 23:34
  • 1
    $\begingroup$ @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 $\endgroup$ – Sasho Nikolov Dec 9 '13 at 6:28
  • $\begingroup$ Just providing another way of looking at the problem... $\endgroup$ – argentpepper Dec 9 '13 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.