Advice (complexity)
|
|
Advice is a concept in 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 must be 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 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 is more involved and requires to build a Boolean circuit that incorporates both Turing machine and its advice string.
Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits.
P/poly contains both P and BPP. 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 all of the values of f on inputs of length n. Therefore, any function is computable with an advice of length 2n and advice of more than exponential length is not meaningful.