Advice (complexity)

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.

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.

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).

Similarly, the class L/poly can be defined as deterministic logspace with a polynomial amount of advice.