Class Description

coC₌P: Complement of C₌P

Equals NQP [FGH+98].

Linked From

A₀PP: 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:

• A₀PP contains QMA, AWPP, and coC₌P.
• A₀PP is contained in PP.
• If A₀PP = PP then PH is contained in PP.

Kuperberg ([Kup09]) showed that A₀PP = SBQP.

More about...

NQP: Nondeterministic Quantum Polynomial-Time

The class of decision problems solvable by a QTM in polynomial time such that a particular '|Accept>' state has nonzero amplitude at the end of the computation, if and only if the answer is 'yes.' Since it has an exact amplitude condition, NQP has the same technical caveats as EQP. Or it would, except that it turns out to equal coC₌P [FGH+98].

Defined in [ADH97].

Contrast with QMA.

More about...

WPP: Wide PP

The class of decision problems solvable by an NP machine such that

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. If the answer is "yes," then their difference exactly equals a function f(x) computable in polynomial time (i.e. FP).

Defined in [FFK94].

Contained in C₌P ∩ coC₌P, as well as AWPP.

Contains SPP and LWPP.

More about...