The class of decision problems solvable by an NP machine such that
Defined in [FFK94].
Contained in C=P ∩ coC=P, as well as AWPP.
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 solvable by an NP machine such that
Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)
Contained in RP, EP, and ModkP for every odd k. Contained in EQP by the Deutsch-Jozsa algorithm.
Defined in [BB92], where it was called C==P[half] (C==P being an alternative name for WPP, that apparently didn't catch on or stick). The name used here is from [BS00]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.
The class of decision problems solvable by an NP machine such that
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.)
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].
The class of decision problems solvable by an NP machine such that
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.