Class Description

∃BPP: BPP With Existential Operator

The class of problems for which there exists a BPP machine M such that, for all inputs x,

• If the answer is "yes" then there exists a y such that M(x,y) accepts.
• If the answer is "no" then for all y, M(x,y) rejects.

Alternatively defined as NP^BPP.

Contains NP and BPP, and is contained in MA and SBP.

∃BPP seems obviously equal to MA, yet [FFK+93] constructed an oracle relative to which they're unequal! Here is the difference: if the answer is "yes," MA requires only that there exist a y such that for at least 2/3 of random strings r, M(x,y,r) accepts (where M is a P predicate). For all other y's, the proportion of r's such that M(x,y,r) accepts can be arbitrary (say, 1/2). For ∃BPP, by contrast, the probability that M(x,y) accepts must always be either at most 1/3 or at least 2/3, for all y's.

Linked From

MA: Merlin-Arthur

The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that

1. If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
2. If the answer is "no," then for all proofs Arthur accepts with probability at most 1/3.

Defined in [Bab85].

An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).

Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.

Also contained in Σ₂P ∩ Π₂P.

There exists an oracle relative to which BQP is not in MA [Wat00].

Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].

Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size ${\displaystyle n^{k}}$ for any ${\displaystyle k>0}$. In the same paper, the result was used to show that MA/1 cannot be solved on more than a ${\displaystyle 1/2+1/{n^{k}}}$ fraction of inputs having length ${\displaystyle n}$ by any circuit of size ${\displaystyle n^{k}}$. Finally, it was shown that MA does not have arithmetic circuits of size ${\displaystyle n^{k}}$.

See also: MA_E, MA_EXP, OMA.

More about...

SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

1. If the answer is "yes" then f(x) > g(x).
2. If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

• SBP contains MA, WAPP, and ∃BPP.
• SBP is contained in AM and BPP_path.
• There exists an oracle relative to which SBP is not contained in Σ₂P.
• SBP is closed under union.

There exists an oracle relative to which SBP is not closed under intersection [GLM+15].

If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].

More about...