Low (complexity)

From Wikipedia, the free encyclopedia

In computational complexity theory, it is said that a complexity class B is low for a complexity class 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 instantly. Informally, this means that the problems in B are "easy to solve" for a machine which can solve problems in A; it can simulate many oracle queries to B without threatening to exceed its resource bounds. Results and relationships that establish one class is low for another are often called lowness results.

Lowness is stronger than containment. If B is contained in A, then every problem in B is also in A, and so a type of machine that can solve all problems in A can solve all problems in B. This allows us to compare the power of classes of machines. For example, because NP is contained in PSPACE, we know that any problem which can be solved by a nondeterministic Turing machine in polynomial time can also be solved by an ordinary deterministic Turing machine in polynomial space. Similarly, if B is low for A, then B must be contained in A, and moreover, machines solving problems in A can solve problems in B so efficiently that they achieve no power from being given the ability to solve them instantly.

[edit] Results

Some trivial lowness results are:

  • P is low for itself (because polynomial algorithms are closed under composition)
  • 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.

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. [1]
  • BQP is low for PP. 1 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}).2 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 ZPPNP, showing that an efficient Las Vegas algorithm with access to an NP oracle can easily solve graph isomorphism as well. 4
  • Amplified PP is low for PP.3

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.

[edit] References

1. L. Fortnow and J. D. Rogers. Complexity limitations on quantum computation. In Proceedings of IEEE Complexity '98, p.202-209. 1998.

2. V. Arvind and P. Kurur. Graph isomorphism is in SPP. Electronic Colloquium on Computational Complexity, TR02-037. 2002.

3. L. Li. On the Counting Functions. PhD thesis, University of Chicago. 1993.

4. Vikraman Arvind and Johannes Köbler. Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, ISBN 3-540-67141-2, p.431-442. 2000.