Class Description

C=P: Exact-Counting Polynomial-Time

The class of decision problems solvable by an NP machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'

Equals coNQP [FGH+98].

Linked From

BC=P: Bounded-Error C=P

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

  1. If the answer is 'yes' then exactly 1/2 of the computation paths accept.
  2. If the answer is 'no' then either at most 1/4 or at least 3/4 of the computation paths accept.

(Here all computation paths have the same length.)

Defined in [Wat15], where it was shown that BC=P admits efficient amplification and is closed under union, intersection, disjunction, and conjunction, and that coRP ⊆ BC=P ⊆ BPP.

More about...

C=L: Exact-Counting L

Has the same relation to L as C=P does to P.

C=LC=L = LC=L [ABO99].

More about...

coC=P: Complement of C=P

Equals NQP [FGH+98].

More about...

coNQP: Complement of NQP

Equals C=P [FGH+98].

More about...

EP: NP with 2k Accepting Paths

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

  1. If the answer is 'no,' then all computation paths reject.
  2. If the answer is 'yes,' then the number of accepting paths is a power of two.

Contained in C=P, and in ModkP for any odd k. Contains UP.

Defined in [BHR00].

More about...

LWPP: Length-Dependent 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 the difference of these numbers equals a function f(|x|) computable in polynomial time (i.e. FP). Here |x| is the length of the input x, and ``polynomial time means polynomial in |x|, the length of x, rather than the length of |x|.

Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)

Contained in WPP and AWPP.

Contains SPP.

Also, contains the graph isomorphism problem [KST92].

Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].

More about...

SPP: Stoic 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 these numbers differ by 1.

We may additionally require that all paths make the same number of binary nondeterministic choices, but then the second condition has to be modified so that if the answer is "yes", the number of accepting and rejecting paths differ by 2. (If the total number of paths is even then the numbers can't differ by 1.)

Defined in [FFK94], where it was also shown that SPP is low for PP, C=P, ModkP, and SPP itself. (I.e. adding SPP as an oracle does not increase the power of these classes.)

Independently defined in [OH93], who called the class XP.

Contained in LWPP, C=P, and WPP among other classes.

Contains FewP; indeed, FewP is low for SPP, so that SPPFewP = SPP [FFK94].

Contains the problem of deciding whether a graph has any nontrivial automorphisms [KST92].

Indeed, contains graph isomorphism [AK02].

Contains a whole gaggle of problems for solvable black-box groups: solvability testing, membership testing, subgroup testing, normality testing, order verification, nilpotetence testing, group isomorphism, and group intersection [Vin04]

[AK02] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in FPSPP.

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