Low (complexity)
Encyclopedia
In computational complexity theory
, a complexity class
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. 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.
Results and relationships that establish one class as low for another are often called lowness results.
is low for itself because polynomial-time algorithms are closed under composition. Informally, this is true because a polynomial-time algorithm can make polynomially many queries to other polynomial-time algorithms, retaining its polynomial running time. PSPACE
is also low for itself, and this can be established by exactly the same argument. Similarly, L
is low for itself because it can simulate log space oracle queries in log space, reusing the same space for each query.
BPP is also low for itself and the same arguments almost work for BPP, but one has to account for errors, making it slightly harder to show that BPP is low for itself. Similarly, the argument for BPP almost goes through for BQP
, but we have to additionally show that quantum queries can be performed in coherent superposition.
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 because it implies that the polynomial hierarchy
collapses to the first level, whereas it is widely believed that the hierarchy is infinite. The converse to this statement is not true. If a class is closed under complement, it does not mean that the class is low for itself. An example of such a class is EXP
, which is closed under complement, but is not low for itself.
Some of the more complex and famous results regarding lowness of classes include:
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
B is said to be low for a complexity class A if AB = A; that is, A with an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
for B is equal to A. Such a statement implies that an abstract machine
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
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.
Results and relationships that establish one class as low for another are often called lowness results.
Results
Several natural complexity classes are known to be low for themselves. For instance, PP (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
is low for itself because polynomial-time algorithms are closed under composition. Informally, this is true because a polynomial-time algorithm can make polynomially many queries to other polynomial-time algorithms, retaining its polynomial running time. PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
is also low for itself, and this can be established by exactly the same argument. Similarly, L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
is low for itself because it can simulate log space oracle queries in log space, reusing the same space for each query.
BPP is also low for itself and the same arguments almost work for BPP, but one has to account for errors, making it slightly harder to show that BPP is low for itself. Similarly, the argument for BPP almost goes through for BQP
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
, but we have to additionally show that quantum queries can be performed in coherent superposition.
Every class which is low for itself is closed under complement
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its 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 because it implies that the polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
collapses to the first level, whereas it is widely believed that the hierarchy is infinite. The converse to this statement is not true. If a class is closed under complement, it does not mean that the class is low for itself. An example of such a class is EXP
Exp
Exp may stand for:* Exponential function, in mathematics* Expiry date of organic compounds like food or medicines* Experience points, in role-playing games* EXPTIME, a complexity class in computing* Ford EXP, a car manufactured in the 1980s...
, which is closed under complement, but is not low for itself.
Some of the more complex and famous results regarding lowness of classes include:
- Both Parity P (
) and BPP are low for themselves. These were important in showing Toda's theoremToda's theoremToda's theorem was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...
. - BQPBQPIn computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
is low for PPPP (complexity)In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
In other words, a randomized algorithmRandomized algorithmA randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
that can be run an unbounded number of times can easily solve all the problems that a quantum computerQuantum computerA quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
can solve efficiently. - The graph isomorphism problemGraph isomorphism problemThe graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
is low for Parity P (
). 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. - Amplified PP is low for PPPP (complexity)In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
.
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.