Class Description

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

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

Linked From

AWPP: Almost WPP

The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,

1. If the answer is "no," then the difference between the number of accepting and rejecting paths is non-negative and at most 2^-poly(n)f(x).
2. If the answer is "yes," then the difference is between (1-2^-poly(n))f(x) and f(x).

Defined in [FFK94].

Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.

Contained in APP [Fen02].

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

WAPP^cc: Communication Complexity WAPP

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 WAPP^cc is equivalent to the "(one-sided) smooth rectangle bound" and also to the approximate nonnegative rank of the communication matrix [KMSY14].

More about...