bn:01281175n
Noun Concept
Categories: Computational complexity theory
EN
low
EN
In computational complexity theory, a language B is said to be 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 at unit cost. Wikipedia
English:
complexity
Definitions
Sources
EN
In computational complexity theory, a language B is said to be 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 at unit cost. Wikipedia
A concept in computational complexity theory Wikipedia Disambiguation
Wikipedia
Wikidata
EN
Low