Class Description

FewP: NP With Few Witnesses

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 at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.

Defined in [AR88].

Is contained in ⊕P [CH89].

There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].

Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].

Contained in Few.

See also the survey [Tor90].

Linked From

⊕P: Parity P

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

1. If the answer is 'yes,' then the number of accepting paths is odd.
2. If the answer is 'no,' then the number of accepting paths is even.

Defined in [PZ83].

Contains Graph Isomorphism; indeed, Graph Isomorphism is low for ⊕P [AK02].

Contains FewP [CH89].

There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].

Equals Mod_2^mP for every positive integer m.

More about...

APP: Amplified PP

Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,

1. If the answer is "yes" then 1 > f(x)/g(1ⁿ) > 1-2^-p(n).
2. If the answer is "no" then 0 < f(x)/g(1ⁿ) < 2^-p(n).

Defined in [Li93], where the following was also shown:

• APP is contained in PP, and indeed is low for PP.
• APP is closed under intersection, union, and complement.

APP contains AWPP [Fen02].

The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.

Contains FewP [Li93] and contains YQP*, YMA*, and YP* [Yir24].

More about...

Few: FewP With Flexible Acceptance Mechanism

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

1. The number of accepting paths a is bounded by a polynomial in the size of the input x.
2. For some polynomial-time predicate Q, Q(x,a) is true if and only if the answer is 'yes.'

Also called FewPaths.

Defined in [CH89].

Contains FewP, and is contained in P^FewP [Kob89] and in SPP [FFK94].

See also the survey [Tor90].

More about...

LogFewNL: Logspace-Bounded FewP

Same as FewP but for logspace-bounded (i.e. NL) machines.

Defined in [BDH+92], where it was also shown that LogFewNL is contained in ModZ_kL for all k>1.

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, Mod_kP, 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 SPP^FewP = 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 FP^SPP.

More about...