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.
The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,
Defined in [FFK94].
Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.
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].
This class is parameterized by a constant ε>0. The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability in [(1-ε)α,α] and no-inputs are accepted with probability in [0,α] 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 admit efficient amplification with respect to the ε parameter [GLM+15].
The complexity measure associated with WAPPcc is equivalent to the "(one-sided) smooth rectangle bound" and also to the approximate nonnegative rank of the communication matrix [KMSY14].