View source for NP/poly

In [[computational complexity theory]], '''NP/poly''' is a [[complexity class]], a [[Circuit complexity|non-uniform]] analogue of the class [[NP (complexity)|NP]] of problems solvable in [[polynomial time]] by a [[non-deterministic Turing machine]]. It is the non-deterministic complexity class corresponding to the deterministic class [[P/poly]].

==Definition==
NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded [[Advice (complexity)|advice]] function.

It may equivalently be defined as the class of problems such that, for each instance size <math>n</math>, there is a [[Boolean circuit]] of size polynomial in <math>n</math> that implements a verifier for the problem. That is, the circuit computes a function <math>f(x,y)</math> such that an input <math>x</math> of length <math>n</math> is a yes-instance for the problem if and only if there exists <math>y</math> for which <math>f(x,y)</math> is true.<ref>{{citation|title=Computational Complexity: A Modern Approach|first1=	Sanjeev|last1=Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9781139477369|contribution=Exercise 7.7|contribution-url=https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA141|page=141}}</ref>

==Applications==
NP/poly is used in a variation of [[Mahaney's theorem]] on the non-existence of sparse [[NP-complete]] languages. Mahaney's theorem itself states that the number of yes-instances of length <math>n</math> of an NP-complete problem cannot be polynomially bounded unless [[P versus NP problem|P = NP]]. According to the variation, the number of yes-instances must be at least <math>2^{n^\epsilon}</math> for some <math>\epsilon>0</math> and for infinitely many <math>n</math>, unless [[co-NP]] is a subset of NP/poly, which (by the [[Karp–Lipton theorem]]) would cause the collapse of the [[polynomial hierarchy]].<ref>{{citation
 | last1 = Buhrman | first1 = Harry
 | last2 = Hitchcock | first2 = John M.
 | contribution = NP-hard sets are exponentially dense unless coNP ⊆ NP/poly
 | doi = 10.1109/CCC.2008.21
 | mr = 2513482
 | pages = 1–7
 | publisher = IEEE Computer Society | location = Los Alamitos, California
 | title = Twenty-Third Annual IEEE Conference on Computational Complexity
 | year = 2008| s2cid = 2664381
 | url = https://ir.cwi.nl/pub/13767
 }}</ref>
The same [[computational hardness assumption]] that co-NP is not a subset of NP/poly also implies several other results in complexity such as the optimality of certain [[kernelization]] techniques.<ref>{{citation
 | last1 = Dell | first1 = Holger
 | last2 = van Melkebeek | first2 = Dieter
 | doi = 10.1145/2629620
 | issue = 4
 | journal = Journal of the ACM
 | mr = 3250069
 | page = A23:1–A23:27
 | title = Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
 | volume = 61
 | year = 2014| s2cid = 1635025
 | url = https://drops.dagstuhl.de/opus/volltexte/2010/2504/
 }}</ref>

==References==
{{reflist}}

[[Category:Complexity classes]]