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.
Attributes | Values |
---|---|
rdfs:label |
|
rdfs:comment |
|
sameAs | |
Subject | |
prov:wasDerivedFrom | |
Wikipage page ID |
|
page length (characters) of wiki page |
|
Wikipage revision ID |
|
Link from a Wikipage to another Wikipage |
|
has abstract |
|
foaf:isPrimaryTopicOf | |
is Link from a Wikipage to another Wikipage of | |
is foaf:primaryTopic of |