In
computational complexity theory, an
advice string is an extra input to a
Turing machine that is allowed to depend on the length
n of the input, but not on the 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.