Explore relationships

Low (complexity)

In computational complexity theory, a languageB (or a complexity classB) is said to be low for a complexity class A (with some reasonable relativized version of A) if A = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine that solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost.

Use + to expand a branch. Click a topic name to open its summary.