# NP/poly

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/NP/poly
> Markdown URL: https://mediated.wiki/source/NP/poly.md
> Source: https://en.wikipedia.org/wiki/NP%2Fpoly
> Source revision: 1335728011
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computational complexity theory](/source/Computational_complexity_theory), **NP/poly** is a [complexity class](/source/Complexity_class), a [non-uniform](/source/Circuit_complexity) analogue of the class [NP](/source/NP_(complexity)) of problems solvable in [polynomial time](/source/Polynomial_time) by a [non-deterministic Turing machine](/source/Non-deterministic_Turing_machine). It is the non-deterministic complexity class corresponding to the deterministic class [P/poly](/source/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](/source/Advice_(complexity)) function.

It may equivalently be defined as the class of problems such that, for each instance size n, there is a [Boolean circuit](/source/Boolean_circuit) of size polynomial in n that implements a verifier for the problem. That is, the circuit computes a function f(x,y) such that an input x of length n is a yes-instance for the problem if and only if there exists y for which f(x,y) is true.[1]

## Applications

NP/poly is used in a variation of [Mahaney's theorem](/source/Mahaney's_theorem) on the non-existence of sparse [NP-complete](/source/NP-complete) languages. Mahaney's theorem itself states that the number of yes-instances of length n of an NP-complete problem cannot be polynomially bounded unless [P = NP](/source/P_versus_NP_problem). According to the variation, the number of yes-instances must be at least 2^{n^\epsilon} for some \epsilon>0 and for infinitely many n, unless [co-NP](/source/Co-NP) is a subset of NP/poly, which (by the [Karp–Lipton theorem](/source/Karp%E2%80%93Lipton_theorem)) would cause the collapse of the [polynomial hierarchy](/source/Polynomial_hierarchy).[2] The same [computational hardness assumption](/source/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](/source/Kernelization) techniques.[3]

## References

1. Arora, Sanjeev & Barak, Boaz (2009), ["Exercise 7.7"](https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA141), *Computational Complexity: A Modern Approach*, Cambridge University Press, p. 141, ISBN 9781139477369

1. Buhrman, Harry & Hitchcock, John M. (2008), ["NP-hard sets are exponentially dense unless coNP ⊆ NP/poly"](https://ir.cwi.nl/pub/13767), *Twenty-Third Annual IEEE Conference on Computational Complexity*, Los Alamitos, California: IEEE Computer Society, pp. 1–7, [doi:10.1109/CCC.2008.21](https://doi.org/10.1109/CCC.2008.21). ISBN 978-0-7695-3169-4. MR 2513482. [S2CID 2664381](https://api.semanticscholar.org/CorpusID:2664381)

1. Dell, Holger & van Melkebeek, Dieter (2014), ["Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses"](https://drops.dagstuhl.de/opus/volltexte/2010/2504/), *Journal of the ACM*. **61** (4): A23:1–A23:27, [doi:10.1145/2629620](https://doi.org/10.1145/2629620). MR 3250069. [S2CID 1635025](https://api.semanticscholar.org/CorpusID:1635025)

---
Adapted from the Wikipedia article [NP/poly](https://en.wikipedia.org/wiki/NP%2Fpoly) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/NP%2Fpoly?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.