Advice (complexity)

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Advice (complexity)

In complexity theory, an advice string is extra input given to a Turing machine that can depend on the input length n, but not on the input itself.

- P/f(n): A problem is in P/f(n) if there is a polynomial-time Turing machine M such that for every n there exists an advice string A of length f(n) so that, for every input x with |x| = n, M correctly decides the problem on x using x and A.

- P/poly: The common case is when the advice length f(n) is a polynomial in n. P/poly equals the set of problems for which, for every input length n, there exists a polynomial-size Boolean circuit that correctly decides all inputs of length n. In one direction, if such circuits A(n) exist, a Turing machine can read A(n) as the circuit description and use it to decide any input of length n. In the other direction, a polynomial-time Turing machine can be simulated by a polynomial-size circuit; the advice can encode this circuit. So P/poly is often defined as problems solvable by polynomial-size circuits, or by polynomial-size non-uniform circuits.

- Consequences: P/poly contains both P and BPP (Adleman’s theorem). It even contains some undecidable problems (for example, the unary versions of undecidable problems, including the halting problem) because the non-uniformity of circuits can circumvent decidability. As a result, P/poly is not contained in any time class DTIME(f(n)) or NTIME(f(n)) for any f.

- Advice with other resource bounds: We can define NP/f(n) by nondeterministic polynomial time with advice of length f(n). If we allow 2n-length advice, we can encode, for each input length n, whether each input of length n is in the language, so any boolean function on length-n inputs becomes computable with 2n advice. Longer-than-exponential advice is not meaningful for this purpose.

- L/poly: Deterministic logarithmic-space machines with polynomial advice, denoted L/poly.

- Notes: These ideas help study how much extra information outside the input itself can boost computation, and how non-uniform resources compare to uniform models. There are many known results about these classes.