In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, an advice string is an extra input to a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
that is allowed to depend on the length ''n'' of the input, but not on the input itself. A
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
is in the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
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
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equiva ...
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
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...
correctly deciding the problem on all inputs of length ''n''. One direction of the equivalence is easy to see. If, for every ''n'', there is a polynomial size Boolean circuit ''A''(''n'') deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. 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
Thomas Cook Group plc was a global travel group, headquartered in the United Kingdom and listed on the London Stock Exchange from its formation on 19 June 2007 by the merger of Thomas Cook AG — successor to Thomas Cook & Son — an ...
. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit.
Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by
polynomial-size non-uniform Boolean circuits.
P/poly contains both P and
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
(Adleman's theorem). It also contains some
undecidable problems, such as the unary version of every undecidable problem, including the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
. Because of that, it is not contained in
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
(''f''(''n'')) or
NTIME In computational complexity theory, the complexity class NTIME(''f''(''n'')) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time ''O''(''f''(''n'')). Here ''O'' is the big O notation, ''f'' is ...
(''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''). If we are allowed an advice of length 2
''n'', we can use it to encode whether each input of length ''n'' is contained in the language. Therefore, any boolean function is computable with an advice of length 2
''n'' and advice of more than exponential length is not meaningful.
Similarly, the class
L/poly In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly.
Forma ...
can be defined as
deterministic logspace with a polynomial amount of advice.
Known results include:
* The classes NL/poly and UL/poly are the same, i.e. nondeterministic logarithmic space computation with advice can be made unambiguous. This may be proved using an
isolation lemma
In theoretical computer science, the term isolation lemma (or isolating lemma) refers to randomized algorithms that reduce the number of solutions to a problem to one, should a solution exist.
This is achieved by constructing random constraints suc ...
.
* It is known that coNEXP is contained in NEXP/poly.
[ Lance Fortnow]
A Little Theorem
/ref>
* If NP is contained in P/poly, then the polynomial time hierarchy collapses ( Karp-Lipton theorem).
References
{{DEFAULTSORT:Advice (Complexity)
Computational complexity theory