The class of decision problems solvable by an NP machine such that
Defined in [PZ83].
Contains Graph Isomorphism; indeed, Graph Isomorphism is low for ⊕P [AK02].
There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].
Equals Mod2^mP for every positive integer m.
The exponential-time analogue of ⊕P.
There exists an oracle relative to which ⊕EXP = ZPP [BBF98].
Has the same relation to L as ⊕P does to P.
Solving a linear system over Z2 is complete for ⊕L [Dam90].
The problem of simulating stabilizer circuits is complete for ⊕L [AG04].
Is not contained in UPPcc [For02].
Does not contain ZPPcc if partial functions are allowed [GPW16b].
The complexity measure associated with ⊕Pcc is equivalent to the log of the rank of the communication matrix over GF(2).
The class of decision problems solvable by an NP machine such that
Defined in [AR88].
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].
The exponential-time analogue of MIP.
In the unrelativized world, equals NEEXP.
There exists an oracle relative to which MIPEXP equals the intersection of P/poly, PNP, and ⊕P [BFT98].
For any k>1: The class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."
Mod2P is more commonly known as ⊕P "parity-P."
For every k, ModkP contains graph isomorphism [AK02].
[Her90] and [BG92] showed that ModkP is the set of unions of languages in ModpP for each prime p that divides k. In particular, if p is prime, then ModpP = Modp^mP for all positive integers m. A further fact is that ModpP is closed under union, intersection, and complement, and low for itself, for p prime.
On the other hand, if k is not a prime power, then there exists an oracle relative to which ModkP is not closed under intersection or complement [BBR94].
For prime p, there exists an oracle relative to which ModpP does not contain EQP [GV02].
The class of decision problems such that whether the answer on input x agrees with the answer on input x-1 (that is, the lexicographic predecessor of x) is solvable in polynomial time. The Turing machine has to decide agreement or disagreement without access to the answer for x-1.
Is contained in E, NT*, and ⊕P. Defined in [GHJ+91] to study ⊕P-complete problems. They show that P, NT, NT*, and ⊕P are either all equal or strictly nested. In particular, they differ with probability 1 relative to a random oracle.
Defined like NT, but with a more general ordering on inputs. A problem L is in NT* if, first, there is a partially defined predecessor function pred(x) in FP that organizes the space of inputs into a forest. The size of the lineage of each x must also be bounded by 2poly(|x|). Second, if L(x) is the Boolean answer to L on input x, then L(x)+L(pred(x)) is computable in polynomial time; or if pred(x) does not exist, L(x) is computable in polynomial time.
Defined in [GHJ+91].
Contains NT and is contained in ⊕P. The inclusions are either both strict or both equalities (whence ⊕P = P as well).
The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF2 contains both ⊕P and NP by using the counter as a witness.
Defined in [CF91], where it was also shown that SF5 = PSPACE.
The complexity of SF2, SF3, and SF4 was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:
(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)