Low (complexity)
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 AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which 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 which 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).
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 others 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:
Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely because it implies that the polynomial hierarchy collapses to the first level, whereas it is widely believed that the hierarchy is infinite. The converse to this statement is not true. If a class is closed under complement, it does not mean that the class is low for itself. An example of such a class is EXP, which is closed under complement, but is not low for itself.
...
Wikipedia