Advice (complexity)
Encyclopedia
In computational complexity theory
, an advice string is an extra input to a Turing machine
which is allowed to depend on the length n of the input, but not on input itself. A decision problem
is in the complexity class
P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A.
The most common complexity class involving advice is P/poly
where advice length f(n) can be any polynomial in n. P/poly is equal to the class of decision problems such that, for every n, there exists a polynomial size Boolean circuit
correctly deciding the problem on all inputs of length n. One direction of the equivalence is easy to see. If, for every n, there is a polynomial size Boolean circuit A(n) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of A(n) as the advice, the machine will correctly decide the problem on all inputs of length n. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of Cook's Theorem
. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit.
Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by polynomial-size non-uniform Boolean circuits.
P/poly contains both P and BPP (Adleman's theorem). It also contains some undecidable
problems, such as the unary version of every undecidable problem, including the halting problem
. Because of that, it is not contained in DTIME
(f(n)) or NTIME
(f(n)) for any f.
Advice classes can be defined for other resource bounds instead of P. For example, taking a non-deterministic
polynomial time Turing machine with an advice of length f(n) gives the complexity class NP
/f(n). If we are allowed an advice of length 2n, we can use it to encode whether each input of length n is contained in the language. Therefore, any boolean function is computable with an advice of length 2n and advice of more than exponential length is not meaningful.
Similarly, the class L/poly
can be defined as deterministic logspace
with a polynomial amount of advice.
Known results include:
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...
, an advice string is an extra input to a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
which is allowed to depend on the length n of the input, but not on input itself. A decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
is in the 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:...
P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A.
The most common complexity class involving advice is P/poly
P/poly
In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class PSIZE of languages that have a polynomial-size circuits...
where advice length f(n) can be any polynomial in n. P/poly is equal to the class of decision problems such that, for every n, there exists a polynomial size Boolean circuit
Boolean circuit
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...
correctly deciding the problem on all inputs of length n. One direction of the equivalence is easy to see. If, for every n, there is a polynomial size Boolean circuit A(n) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of A(n) as the advice, the machine will correctly decide the problem on all inputs of length n. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of Cook's Theorem
Cook's theorem
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete...
. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit.
Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by polynomial-size non-uniform Boolean circuits.
P/poly contains both P and BPP (Adleman's theorem). It also contains some undecidable
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
problems, such as the unary version of every undecidable problem, including the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
. Because of that, it is not contained in DTIME
DTIME
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
(f(n)) or NTIME
NTIME
In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
(f(n)) for any f.
Advice classes can be defined for other resource bounds instead of P. For example, taking a non-deterministic
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...
polynomial time Turing machine with an advice of length f(n) gives the complexity class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
/f(n). If we are allowed an advice of length 2n, we can use it to encode whether each input of length n is contained in the language. Therefore, any boolean function is computable with an advice of length 2n and advice of more than exponential length is not meaningful.
Similarly, the class L/poly
L/poly
In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly....
can be defined as deterministic logspace
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...
with a polynomial amount of advice.
Known results include:
- The classes NL/poly and UL/poly are the same, i.e. nondeterministic logarithmic space computation with advice can be made unambiguous. This is proved using isolation lemmaIsolation lemmaThe isolation lemma, also sometimes known as the isolating lemma, is a lemma in probability theory with several applications in computer science. It was introduced in a paper by Mulmuley, Vazirani and Vazirani, who used it to give a randomized parallel algorithm for the maximum matching...
.
- It is known that coNEXP is contained in NEXP/poly.
- If NP is contained in P/poly, then the polynomial time hierarchy collapses (Karp-Lipton theorem).