In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if A<sup>B</sup> = A; that is, A with an oracle for B is equal to A.

Such a statement implies that an abstract machine that solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines that can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.

Results and relationships that establish one class as low for another are often called lowness results. The set of languages low for a complexity class A is denoted Low(A).

Classes that are low for themselves

Several natural complexity classes are known to be low for themselves. Such a class is sometimes called self-low. Scott Aaronson calls such a class a physical complexity class. Note that being self-low is a stronger condition than being closed under complement. Informally, a class being low for itself means a problem can use other problems in the class as unit-cost subroutines without exceeding the power of the complexity class.

The following classes are known to be self-low:

  • Both Parity P (<math>{\oplus}\hbox{P}</math>) and BPP are low for themselves. These were important in showing Toda's theorem.
  • NP &cap; coNP is low for itself. In other words, a program based around taking the majority decision of an unbounded number of iterations of a poly-time randomized algorithm can easily solve all the problems that a quantum computer can solve efficiently.
  • The graph isomorphism problem is low for parity P (<math>{\oplus}\hbox{P}</math>). This means that if we can determine whether an NP machine has an even or odd number of accepting paths, we can easily solve graph isomorphism. In fact, it was later shown that graph isomorphism is low for ZPP<sup>NP</sup>.
  • Amplified PP is low for PP.
  • NP &cap; coNP is equal to the set of languages low for NP, i.e., Low(NP) = NP &cap; coNP.