Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Advice (complexity)
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, an advice string is an extra input to a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> that is allowed to depend on the length <i>n</i> of the input, but not on the input itself. A <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> is in the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> P/<i>f</i>(<i>n</i>) if there is a polynomial time Turing machine <i>M</i> with the following property: for any <i>n</i>, there is an advice string <i>A</i> of length <i>f</i>(<i>n</i>) such that, for any input <i>x</i> of length <i>n</i>, the machine <i>M</i> correctly decides the problem on the input <i>x</i>, given <i>x</i> and <i>A</i>. </p><p>The most common complexity class involving advice is <a href="/facts/P%2fpoly/cHXNlnYJ">P/poly</a> where advice length <i>f</i>(<i>n</i>) can be any polynomial in <i>n</i>. P/poly is equal to the class of decision problems such that, for every <i>n</i>, there exists a polynomial size <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuit</a> correctly deciding the problem on all inputs of length <i>n</i>. One direction of the equivalence is easy to see. If, for every <i>n</i>, there is a polynomial size Boolean circuit <i>A</i>(<i>n</i>) 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 <i>A</i>(<i>n</i>) as the advice, the machine will correctly decide the problem on all inputs of length <i>n</i>. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of <a href="/facts/Cook%2527s_theorem/6WN3aUyL">Cook's theorem</a>. 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. </p><p>Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by <a href="/facts/Circuit_complexity/6EzA9Tty">polynomial-size non-uniform</a> Boolean circuits. </p><p>P/poly contains both P and <a href="/facts/BPP_(complexity)/6woy25bz">BPP</a> (Adleman's theorem). It also contains some <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a> problems, such as the unary version of every undecidable problem, including the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a>. Because of that, it is not contained in <a href="/facts/DTIME/oyVAQfHk">DTIME</a> (<i>f</i>(<i>n</i>)) or <a href="/facts/NTIME/AqQII2Q8">NTIME</a> (<i>f</i>(<i>n</i>)) for any <i>f</i>. </p><p>Advice classes can be defined for other resource bounds instead of P. For example, taking a <a href="/facts/Nondeterministic_algorithm/UubLdp3D">non-deterministic</a> polynomial time Turing machine with an advice of length <i>f</i>(<i>n</i>) gives the complexity class <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>/<i>f</i>(<i>n</i>). If we are allowed an advice of length 2<i>n</i>, we can use it to encode whether each input of length <i>n</i> is contained in the language. Therefore, any boolean function is computable with an advice of length 2<i>n</i> and advice of more than exponential length is not meaningful. </p><p>Similarly, the class <a href="/facts/L%2fpoly/odwQxMdD">L/poly</a> can be defined as <a href="/facts/L_(complexity)/vCMV0edS">deterministic logspace</a> with a polynomial amount of advice. </p><p>Known results include: </p> <ul><li>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 <a href="/facts/Isolation_lemma/sAKV3gSS">isolation lemma</a>.</li> <li>It is known that coNEXP is contained in NEXP/poly.</li> <li>If NP is contained in P/poly, then the polynomial time hierarchy collapses (<a href="/facts/Karp-Lipton_theorem/yxtvuKDk">Karp-Lipton theorem</a>).</li></ul>