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,
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].
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.
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.
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.
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.
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].
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,
Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.