Editing Advice (complexity)

{{short description|Computational input that relies on the length but not content of the input}}
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''.

The most common complexity class involving advice is '''[[P/poly]]''' 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]] 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]].  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.<ref>{{citation|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|page=113|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA113|zbl=1193.68112}}.</ref>

Because of this equivalence, '''P/poly''' is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by [[Circuit complexity#Uniformity|polynomial-size non-uniform]] Boolean circuits.

'''P/poly''' contains both '''P''' and '''[[BPP (complexity)|BPP]]''' (Adleman's theorem). It also contains some [[undecidable problem|undecidable]] problems, such as the unary version of every undecidable problem, including the [[halting problem]]. Because of that, it is not contained in [[DTIME]] (''f''(''n'')) or [[NTIME]] (''f''(''n'')) for any ''f''.

Advice classes can be defined for other resource bounds instead of '''P'''. For example, taking a [[nondeterministic algorithm|non-deterministic]] polynomial time Turing machine with an advice of length ''f''(''n'') gives the complexity class '''[[NP (complexity)|NP]]/''f''(''n'')'''. If we are allowed an advice of length 2<sup>''n''</sup>, 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<sup>''n''</sup> and advice of more than exponential length is not meaningful.

Similarly, the class '''[[L/poly]]''' can be defined as [[L (complexity)|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.<ref>{{cite journal | last1=Reinhardt | first1=Klaus | last2=Allender | first2=Eric | title=Making nondeterminism unambiguous | zbl=0947.68063 | journal=SIAM J. Comput. | volume=29 | number=4 | pages=1118–1131 | year=2000 | doi=10.1137/S0097539798339041 | citeseerx=10.1.1.55.3203 }}</ref>  This may be proved using an [[isolation lemma]].<ref>{{cite book | last1=Hemaspaandra | first1=Lane A. | last2=Ogihara | first2=Mitsunori | title=The complexity theory companion | zbl=0993.68042 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-67419-5 | url-access=registration | url=https://archive.org/details/complexitytheory0000hema }}</ref>
* It is known that '''coNEXP''' is contained in '''NEXP/poly'''.<ref>[[Lance Fortnow]], [http://oldblog.computationalcomplexity.org/2004/01/little-theorem.html A Little Theorem] {{Webarchive|url=https://web.archive.org/web/20190805141748/http://oldblog.computationalcomplexity.org/2004/01/little-theorem.html |date=2019-08-05 }}</ref>
* If '''NP''' is contained in '''P/poly''', then the polynomial time hierarchy collapses ([[Karp-Lipton theorem]]).

==References==
{{reflist}}

{{DEFAULTSORT:Advice (Complexity)}}
[[Category:Computational complexity theory]]