Class Description

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:

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

Linked From

A0PP: One-Sided Analog of AWPP

Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.

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

Kuperberg ([Kup09]) showed that A0PP = SBQP.

More about...


∃BPP: BPP With Existential Operator

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

Alternatively defined as NPBPP.

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.

More about...


NIPZK: Non-Interactive PZK

Defined in [M08] based on [DDPY98],[BFM88].

Contained in PZK and coSBP.There are oracles separating NIPZK from PZK, coNIPZK, and SBP [BCHTV17], [DGPV20].

[M08] showed a complete promise-problem for NIPZK, called Uniform (UN). Instances in UN are circuits with n+1 output bits. The first n bits represent the uniform distribution, and the last bit is 1 with probability at least 2/3. For instances not in UN, when the last bit is 1, at most 1/3 of the strings of length n can appear as the output of the circuit. The problem is to decide which is the case. [DGPV20] showed Uniform is in coSBP.

More about...


PZK: Perfect Zero Knowledge

Same as SZK, but now the two distributions must be identical, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)

Contained in SZK and HVPZK.There are oracles separating PZK from SZK, coPZK, NIPZK, and coSBP. [BCHTV17], [DGPV20].

See also: CZK.

More about...


SBPcc: Communication Complexity SBP

The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least α and no-inputs are accepted with probability at most α/2 where α is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/α).

Does not contain coNPcc [Raz92] [GW14].

Contains MAcc but does not equal it, since SBPcc is not closed under intersection [GLM+15].

Contained in AMcc and in PostBPPcc.

The complexity measure corresponding to SBPcc is equivalent to the "corruption bound" [GW14].

More about...


WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

  1. If the answer is "yes" then 2p(|x|) ≥ f(x) > (1+ε) 2p(|x|)-1.
  2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

More about...