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 is 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)
* 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. [http://www.cs.rutgers.edu/~allender/538/murata3.ps.gz]
* 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.

References

1. L. Fortnow and J. D. Rogers. [http://xxx.lanl.gov/abs/cs.CC/9811023 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. [http://eccc.hpi-web.de/eccc/ "Electronic Colloquium on Computational Complexity"] , [http://eccc.hpi-web.de/eccc-reports/2002/TR02-037/index.html 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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Low-complexity art — was introduced by Jürgen Schmidhuber in 1997 [J. Schmidhuber. Low complexity art. Leonardo, Journal of the International Society for the Arts, Sciences, and Technology, 30(2):97–103, 1997. http://www.jstor.org/pss/1576418 ] . He characterizes it… …   Wikipedia

  • Low Complexity Subband Codec — Pour les articles homonymes, voir SBC. Low Complexity Subband Codec (SBC) est un codec de compression audio et vidéo spécialement conçu pour les applications audio et vidéo de Bluetooth. Il permet la transmission de flux de haute qualité (128… …   Wikipédia en Français

  • Low Complexity Subband Codec — Der Low Complexity Subband Codec (SBC) ist ein Audio Codec, der im Funkstandard Bluetooth definiert wurde und bisher auch nur dort genutzt wird. SBC muss im Bluetooth Profile A2DP (Advanced Audio Distribution Profile) obligatorisch unterstützt… …   Deutsch Wikipedia

  • Low — may refer to:*Low (complexity), a relationship between complexity classes in computational complexity theory *Low Island (disambiguation) *Low pressure area, a region where the atmospheric pressure is lowest with relation to the surrounding area… …   Wikipedia

  • Low Rate Picture Transmission — The Low Rate Picture Transmission (LRPT) is a digital transmission system, intended to deliver images and data from an orbital weather satellite directly to end users via a VHF radio signal. It is used aboard polar orbiting, near Earth weather… …   Wikipedia

  • low — low1 [lō] adj. [ME lah < ON lagr, akin to MDu lage, MLowG læge < IE base * legh , LIE1] 1. a) of little height or elevation; not high or tall b) not far above the ground [low clouds] 2. depress …   English World dictionary

  • Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… …   Wikipedia

  • complexity — /keuhm plek si tee/, n., pl. complexities for 2. 1. the state or quality of being complex; intricacy: the complexity of urban life. 2. something complex: the complexities of foreign policy. [1715 25; COMPLEX + ITY] * * * ▪ scientific theory… …   Universalium

  • low — I. intransitive verb Etymology: Middle English loowen, from Old English hlōwan; akin to Old High German hluoen to moo, Latin calare to call, summon, Greek kalein Date: before 12th century moo II. noun Date: 1549 the deep sustained sound… …   New Collegiate Dictionary

  • Low-performance equipment — In telecommunication, the term low performance equipment has the following meanings: * Equipment that has imprecise characteristics that do not meet system reliability requirements. * In military communications, equipment that has insufficiently… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.