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 classP/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.[1]
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 (Adleman's theorem). It also contains some 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 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 2n, 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 2n and advice of more than exponential length is not meaningful.
The classes NL/poly and UL/poly are the same, i.e. nondeterministic logarithmic space computation with advice can be made unambiguous.[2] This may be proved using an isolation lemma.[3]
It is known that coNEXP is contained in NEXP/poly.[4]
If NP is contained in P/poly, then the polynomial time hierarchy collapses (Karp-Lipton theorem).
Referencesedit
^Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, p. 113, ISBN9780521424264, Zbl 1193.68112.
^Reinhardt, Klaus; Allender, Eric (2000). "Making nondeterminism unambiguous". SIAM J. Comput. 29 (4): 1118–1131. CiteSeerX10.1.1.55.3203. doi:10.1137/S0097539798339041. Zbl 0947.68063.
^Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). The complexity theory companion. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN3-540-67419-5. Zbl 0993.68042.
advice, complexity, computational, complexity, theory, advice, string, extra, input, turing, machine, that, allowed, depend, length, input, input, itself, decision, problem, complexity, class, there, polynomial, time, turing, machine, with, following, property. 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 1 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 Adleman s theorem It also contains some 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 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 2n 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 2n and advice of more than exponential length is not meaningful Similarly the class L poly 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 2 This may be proved using an isolation lemma 3 It is known that coNEXP is contained in NEXP poly 4 If NP is contained in P poly then the polynomial time hierarchy collapses Karp Lipton theorem References edit Arora Sanjeev Barak Boaz 2009 Computational Complexity A Modern Approach Cambridge University Press p 113 ISBN 9780521424264 Zbl 1193 68112 Reinhardt Klaus Allender Eric 2000 Making nondeterminism unambiguous SIAM J Comput 29 4 1118 1131 CiteSeerX 10 1 1 55 3203 doi 10 1137 S0097539798339041 Zbl 0947 68063 Hemaspaandra Lane A Ogihara Mitsunori 2002 The complexity theory companion Texts in Theoretical Computer Science An EATCS Series Berlin Springer Verlag ISBN 3 540 67419 5 Zbl 0993 68042 Lance Fortnow A Little Theorem Archived 2019 08 05 at the Wayback Machine Retrieved from https en wikipedia org w index php title Advice complexity amp oldid 1168658250, wikipedia, wiki, book, books, library,
