Class Description

⊕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 Mod2^mP for every positive integer m.

Linked From

⊕EXP: Parity EXP

The exponential-time analogue of ⊕P.

There exists an oracle relative to which ⊕EXP = ZPP [BBF98].

More about...


⊕L: Parity L

Has the same relation to L as ⊕P does to P.

Contains SL [KW93].

Solving a linear system over Z2 is complete for ⊕L [Dam90].

The problem of simulating stabilizer circuits is complete for ⊕L [AG04].

⊕L⊕L = ⊕L [BDH+92], [HRV00].

More about...


⊕Pcc: Communication Complexity ⊕P

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

More about...


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

More about...


MIPEXP: Exponential-Time Multi-Prover Interactive Proof

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

More about...


ModkP: Mod-k Polynomial-Time

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

Defined in [CH89], [Her90].

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

More about...


NT: Near-Testable

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.

More about...


NT*: Near-Testable With Forest Ordering

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

More about...


SFk: Width-k Bottleneck Turing Machines

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:

SF4 is contained in BP ⊕PMod_3P ^ ⊕P ^ Mod_3P ^ ⊕P

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

More about...