Math Conjectures

NP⊈P/polyNP\nsubseteq P/poly

OPENMajorConjectureProposed c. 1980 · Standard version

Canonical statement

There is a language in NPNP that is not decided by any family (Cn)n≥1(C_n)_{n\geq1} of Boolean circuits of size polynomial in nn, where CnC_n decides membership for all inputs of length nn; in symbols,
NP⊈P/poly. NP\nsubseteq P/poly.
Here NPNP is nondeterministic polynomial time, and P/polyP/poly is the class defined by such polynomial-size, nonuniform circuit families.
View source LaTeX
There is a language in \(NP\) that is not decided by any
family \((C_n)_{n\geq1}\) of Boolean circuits of size polynomial in \(n\),
where \(C_n\) decides membership for all inputs of length \(n\); in
symbols,
\[
  NP\nsubseteq P/poly.
\]
Here \(NP\) is nondeterministic polynomial time, and \(P/poly\) is the
class defined by such polynomial-size, nonuniform circuit families.
TCS-006:[KarpLipton1980][AroraBarak2009][Williams2014Circuit]
Theoretical computer scienceLogic and foundations

Notes

The conjecture asserts that some language in NPNP cannot be decided by any family of polynomial-size Boolean circuits, in symbols NP⊈P/polyNP\nsubseteq P/poly. Since P⊆P/polyP\subseteq P/poly, this is a nonuniform strengthening of P≠NPP\ne NP. Its modern formulation dates from around 1980, when Karp and Lipton studied the consequences of the opposite inclusion [KarpLipton1980].

Karp and Lipton showed that NP⊆P/polyNP\subseteq P/poly would collapse the polynomial hierarchy [KarpLipton1980], which is the main structural evidence for the conjecture. Yet unconditional lower bounds remain scarce: no superpolynomial circuit lower bound is known for any explicit language in NPNP, and the strongest unconditional results concern restricted circuit models, such as Williams's lower bound against nonuniform ACCACC circuits [Williams2014Circuit]. The general theory is developed in Arora and Barak [AroraBarak2009].

The conjecture is open: proving it requires a superpolynomial lower bound against general Boolean circuits for an explicit NPNP problem, a barrier that has resisted all known techniques.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.