Definition
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.
Related concepts
BPP (complexity)Boolean circuitCircuit complexityComplexity classComputational complexity theoryCook's theoremDTIMEDecision problemHalting problemIsolation lemmaKarp-Lipton theoremL/polyL (complexity)Lance FortnowNP (complexity)NTIMENondeterministic algorithmP/polySanjeev Arora (computer scientist)Springer-VerlagTuring machineUndecidable problem
7 concepts already in your glossary