Low (complexity)

In computational complexity theory, it is said that a complexity class B is low for a complexity class A if A^B = 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 instantly. Notice this means lowness implies containment. Informally, lowness means that problems in B are not only solvable by machines which can solve problem in A, but are "easy to solve". An A machine can simulate many oracle queries to B without exceeding its resource bounds. Containment does not always imply lowness -- an A machine with access to an oracle for an A machine can solve any problem in coA by passing the query to the oracle and then negating the result. Thus, any class which is low for itself must be closed under complement.

Results and relationships that establish one class as low for another are often called lowness results.

Results

Some trivial lowness results are:

• P is low for itself (because polynomial algorithms are closed under composition). The same argument almost works for BPP, but we have to account for errors, making it slightly harder to show that it is low for itself. The argument for BPP almost goes through for BQP, but we have to additionally show that quantum queries can be performed in coherent superposition.
• L is low for itself (because it can simulate log space oracle queries in log space, reusing the same space for each query).
• Every class which is low for itself is closed under complement. This is because it can solve a complement problem by simply querying itself and then inverting the answer. 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 not low for itself.

Some of the more complex and famous results regarding lowness of classes include:

• Both Parity P (${\oplus }{\hbox{P}}$) and BPP are low for themselves. These were important in showing Toda's theorem.
• BQP is low for PP In other words, a randomized algorithm that can be run an unbounded number of times can easily solve all the problems that a quantum computer can solve efficiently.
• The graph isomorphism problem is low for Parity P (${\oplus }{\hbox{P}}$). 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^NP.
• Amplified PP is low for PP.

Lowness is particularly valuable in relativization arguments, where it can be used to establish that the power of a class does not change in the "relativized universe" where a particular oracle machine is available for free. This allows us to reason about it in the same manner we normally would. For example, in the relativized universe of BQP, PP is still closed under union and intersection. It's also useful when seeking to expand the power of a machine with oracles, because lowness results determine when the machine's power remains the same.