Advice (complexity)
Advice in computational complexity theory refers to the additional information — an advice string — that a computational device receives to assist in solving problems. Unlike an oracle, which can answer arbitrary questions about a specific problem instance, advice depends only on the input length, not on the particular input. This seemingly minor distinction makes advice one of the most consequential concepts in complexity theory, because it formalizes what it means for a system to have memory that scales with the size of its tasks without requiring real-time adaptation to each task's specifics.
The Canonical Classes: P/poly and Beyond
The most significant advice class is P/poly: the set of decision problems solvable by a polynomial-time deterministic Turing machine given a polynomial-length advice string that depends only on the input length. The poly suffix denotes both the polynomial time bound and the polynomial advice bound.
P/poly is equivalently characterized as the class of problems solvable by polynomial-size Boolean circuit families. This equivalence is not superficial: a circuit family for inputs of length n is precisely a non-uniform computational model — the circuit for each n can be entirely different, just as the advice string for each n can be entirely different. The equivalence reveals that advice is the software counterpart to circuit complexity's hardware perspective: both model computation where the machine can vary with the input length.
This connection makes P/poly a natural object of study for cryptography and learning theory. If NP ⊆ P/poly, then polynomial-size circuits could solve NP-complete problems, and the Karp-Lipton Theorem shows that this would collapse the polynomial hierarchy to its second level. The theorem demonstrates that non-uniformity — the power of advice — is not merely a theoretical curiosity but a structural property whose presence or absence has dramatic consequences for the entire complexity landscape.
Advice as a Resource
Advice can be bounded by any function of input length. P/log receives only logarithmic advice; P/quadratic receives polynomial advice of degree 2. The advice hierarchy theorem states that more advice yields strictly more power: P/f(n) ⊂ P/g(n) when f(n) = o(g(n)). This is the non-uniform analogue of the time hierarchy theorem, and it is proved with the same diagonalization technique.
The resource perspective on advice reframes the concept. Advice is not merely "help" given to a machine. It is a measurable resource whose consumption can be quantified, optimized, and bounded. In this framing, a machine with advice is a two-part system: a general-purpose algorithm and a task-specific lookup table. The division between the two parts is itself a design choice, and the optimal division depends on the structure of the problem domain.
The Physical and Philosophical Dimensions
The advice model has surprising physical interpretations. In quantum computing, the class BQP/qpoly captures quantum polynomial time with quantum advice. The advice can be an arbitrary quantum state, not merely classical bits, raising questions about whether quantum advice offers genuine computational power beyond classical advice for the same time bound. The question remains open, and its resolution would clarify the boundary between quantum and classical resources.
More philosophically, advice formalizes the distinction between uniform and non-uniform computation. Uniform computation — a single algorithm that works for all input lengths — is what we typically mean by "a program." Non-uniform computation — a different algorithm for each input length — is what we find in physical systems that have evolved structures at different scales. The DNA molecule contains different "programs" for different developmental stages; the immune system maintains different response patterns for different pathogen sizes; social organizations maintain different protocols for different scales of operation. In all these cases, the system is not adapting in real time but drawing on precomputed knowledge scaled to the problem's size.
The advice model therefore captures something deeper than its technical origins in complexity theory. It captures the idea that systems remember at scale — that the information a system brings to a problem depends on the magnitude of the problem, and that this scale-dependent memory is a structural property of the system, not a temporary adaptation to circumstances.
The Limitations of Advice
Advice is powerful but bounded. An advice string for length n can be arbitrarily complex — there is no computability requirement on how it is generated. This means P/poly contains undecidable problems, a fact that seems paradoxical until one recognizes that P/poly is not a class of feasible computation but of feasible evaluation given precomputed assistance. The advice itself may be uncomputable, even though the evaluation is fast.
This limitation makes advice classes unsuitable as models of practical computation. A machine that requires advice strings of length 10^6 for inputs of length 10^6 is not practical even if the evaluation is polynomial time. The advice must be stored, transmitted, and maintained. Advice classes are therefore best understood as structural tools — they reveal what is possible with idealized assistance, not what is achievable with realistic resources.
The tendency to treat advice classes as practical models is the same error as treating P as the class of "efficiently solvable" problems without considering constant factors, memory hierarchies, or implementation details. Theoretical complexity classes are maps of possibility, not blueprints for engineering. Advice is the most extreme case of this abstraction: it gives the machine everything it needs except the ability to adapt.