NP versus P/poly

NP versus P/poly

Definitions and mathematical statement

A Boolean circuit is a finite directed acyclic computation with binary AND/OR gates, unary NOT gates, input bits, constants, and one output. Define $\mathsf{P/poly}$ by \[ L\in\mathsf{P/poly}\ \Longleftrightarrow\ \exists C,k\ \forall n\ge0\ \exists C_n: |C_n|\le C(n+1)^k,\quad C_n(x)=1_L(x)\ (|x|=n). \] All nodes are counted. No algorithm for generating $C_n$ is required. With $\mathsf{NP}$ defined by polynomially checkable witnesses, determine whether $\mathsf{NP}\subseteq\mathsf{P/poly}$. Different languages may have different size bounds.

Formulation and concept references: [S1].

Short English statement

Can every efficiently verifiable decision problem be solved by small circuits when a different circuit may be chosen separately for each input length?

Research attempt

Scope and literature check.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026 by checking the catalogue, deriving a counting construction, and then looking for the first place where it fails to yield an NP lower bound. The circuit basis and the convention that input and constant nodes count are retained. Unbounded search for the appropriate circuit is permitted in $\mathsf{P/poly}$; a lower bound on the time needed to find circuits would not settle this question.

The circuit/advice equivalence and Karp--Lipton implication in [S1], Sections 6.1--6.2, were checked. The latter says that $\mathsf{NP}\subseteq\mathsf{P/poly}$ collapses the polynomial hierarchy to its second level; a collapse is a consequence, not a contradiction already known to be impossible. The original nonuniform-to-uniform work is [E1]. The counting argument below is deliberately elementary and self-contained; it is not claimed to improve known circuit lower bounds.

Write $s_L(n)$ for the least number of nodes in a circuit for the length-$n$ characteristic function of $L$. A negative answer needs \[ \exists L\in\mathsf{NP}\ \forall C>0\ \forall k\ge1\ \exists n: s_L(n)>C(n+1)^k. \] Equivalently, one fixed NP language must beat each fixed polynomial bound on infinitely many lengths. The word "fixed" applies to the language and its verifier before choosing the exponent to be defeated. A family of languages indexed by that exponent does not suffice.

Attack plan: make the counting witness explicit.

There are $2^{2^n}$ Boolean functions on $n$ bits but only $2^{O(s\log(n+s))}$ circuits with at most $s$ gates. This proves that most functions require large circuits, but it does not place their truth tables inside a language with an NP verifier. A natural repair is to select the first missing truth table. The following construction makes that selection fully uniform, bounds its working storage, and identifies an additional failure: the selected language still has polynomial-size circuits.

Lemma 12.1: an explicit fixed-exponent diagonalization.

For every fixed integer $k\ge1$, there is a language $L_k$ in $\mathsf{PSPACE}\cap\mathsf{P/poly}$ such that, for all sufficiently large $n$, no circuit of at most $n^k$ nodes computes its length-$n$ restriction. A deterministic decider can use $O(n^k\log(n+2))$ work bits and $2^{O(n^k\log(n+2))}$ time.

Proof. Put $s=n^k$ and $q=n+s+2$. Every circuit with at most $s$ internal gates can be listed in topological order. For each gate allow at most four types and two source indices in a pool of size $q$; unused source slots and invalid choices only increase the count. There are at most $q$ choices for the output. Summing over the possible number of gates yields the explicit upper bound \begin{equation}\label{wsref-0-61-31-32-3a-63-6f-75-6e-74} N=(s+1)q(4q^2)^s. \end{equation} Every circuit of at most $s$ total nodes occurs in this larger class. Repeated encodings of the same circuit or function do not hurt the bound. The integer $N$ has \[ B=\lceil\log_2(N+1)\rceil =O(n^k\log(n+2)) \] bits. For all sufficiently large $n$, $B<2^n$.

For each $j\in\{0,\ldots,N\}$, let $T_j$ be the $2^n$-bit binary expansion of $j$, padded by leading zeroes, regarded as a truth table in lexicographic input order. These $N+1$ tables are distinct. At most $N$ of them can be computed by the circuits being enumerated. Let $j_n$ be the smallest index whose table is not computed by any such circuit, and define \[ 1_{L_k}(x)=T_{j_n}[x] \qquad(|x|=n). \] Use the zero function at the finitely many lengths where $B\ge2^n$. The choice exists by counting and immediately gives the lower bound.

To compute $j_n$, enumerate $j=0,\ldots,N$. For each $j$, enumerate the valid circuit descriptions and test whether each disagrees with $T_j$ on some input. Test equality by traversing all $2^n$ inputs, evaluating the circuit and one requested bit of $T_j$. Neither a circuit truth table nor the padded string $T_j$ is stored. The nonzero part of $T_j$ is contained in its last $B$ positions, so a requested bit is obtained from the $B$-bit integer $j$ and an $n$-bit position counter. A circuit description uses $O(s\log q)$ bits; its evaluation uses polynomially many additional bits, in fact $O(s+n)$ for gate values and the current input. Reuse this storage for the successive candidates. The circuit enumeration can likewise be implemented with $O(s\log q)$ counters and descriptions.

There are at most $N+1$ candidates, at most $N$ circuit descriptions, and $2^n$ input evaluations per comparison. Thus the time is bounded by $(N+1)N2^n\operatorname{poly}(n,s)$, which is $2^{O(n^k\log(n+2))}$, and the work space is $O(B)$. Both exponents refer to the previously fixed integer $k$.

Finally, $T_{j_n}$ contains at most $B$ ones. A circuit can hardwire all accepted strings of length $n$, test equality with each using $O(n)$ gates, and OR the results. Shared negated inputs and binary trees implement this with $O(nB+n)$ total nodes. Therefore \begin{equation}\label{wsref-0-61-31-32-3a-75-70-70-65-72} s_{L_k}(n)=O(n^{k+1}\log(n+2)), \end{equation} up to adjustment at finitely many lengths. This is a polynomial bound for fixed $k$, so $L_k\in\mathsf{P/poly}$. The enumeration algorithm gives $L_k\in\mathsf{PSPACE}$.$\square$

This is more informative than saying that counting is nonconstructive. The counting witness here is uniformly computable with a polynomial space bound, and nevertheless it provably fails the required nonuniform separation. The construction forces a bound larger than $n^k$, while its choice of small integer truth tables guarantees a somewhat larger polynomial upper bound. Both bounds hold for the same language without contradiction.

Where an NP-certificate argument stalls.

For a candidate $j$ of polynomial bit length, its missing-table property is \begin{equation}\label{wsref-0-61-31-32-3a-71-75-61-6e-74-69-66-69-65-72-73} \forall\text{ circuits }C\text{ in the size bound}\quad \exists x\in\{0,1\}^n:\ C(x)\ne T_j[x]. \end{equation} Each individual disagreement is efficiently checked. But a list with one disagreement for every circuit can have exponential length. Guessing just $j$ does not verify the universal circuit condition. Guessing one circuit and one disagreement does not verify it either, because that reverses the quantifier pattern. Selecting the least missing table additionally requires establishing that earlier candidates were not missing.

Equation (a12:quantifiers) is a precise gap in this route, rather than a theorem that no NP verifier for $L_k$ could exist. The attempted verifier has not supplied a polynomial certificate for that universal condition. Even supplying one would still leave the upper bound (a12:upper) and the need to defeat every polynomial for a single language.

Testing two repairs.

First, let $k$ grow slowly with $n$ and repeat the diagonalization. This can produce a single computable language whose slices eventually beat each fixed power. However its stored circuit descriptions have length $n^{k(n)}$ up to logarithmic factors. If $k(n)$ is unbounded, this is not bounded by any fixed polynomial. The particular decider above then has no polynomial-space guarantee, much less a polynomial NP witness bound. Scheduling a larger exponent at a sparse sequence of lengths does not change this worst-case requirement.

Second, pad an input of length $n$ to length $N=n^d$, with $d$ fixed, hoping to pay for the search. A bound larger than $n^k$ then becomes only a bound larger than $N^{k/d}$, modulo the gates needed to hardwire padding. It still defeats a fixed exponent. If the padding is large enough to make an exponential search polynomial in the padded length, that same size change can make the inherited circuit bound much too small. Neither padding nor renaming the exponent repairs the quantifiers automatically.

A positive answer would require polynomial circuits for an NP-complete language, such as SAT, with arbitrary dependence on input length allowed. No such circuit construction appears here. The absence of an efficient uniform circuit generator cannot be used as evidence against that answer.

Verification.

The counting bound deliberately counts a larger gate model than the target, so the lower bound survives the convention that every node counts. The upper bound explicitly includes the $n$ input nodes, shared negations, equality tests, and output tree. Finitely many exceptional lengths can be hardwired into either description without affecting class membership.

The companion script checks the finite core independently for $n=1,2,3$ with one internal gate: it enumerates every permitted gate and source pair, forms the distinct truth tables, and finds the least omitted table when one exists. At one input every function already occurs; at larger inputs the missing-table selection is well defined. This checks the combinatorial selection, not the asymptotic resource analysis. In particular no experiment is presented as evidence that SAT needs large circuits.

Outcome and next targets.

UNRESOLVED. A fully specified fixed-exponent diagonalization has been proved, together with a polynomial circuit upper bound for its own output. This decisively rejects that construction as a separation from $\mathsf{P/poly}$. Its mathematics is elementary; historical novelty is not claimed. The remaining target is one NP language with superpolynomial circuit complexity. Useful next steps would require a property specific to NP witness relations, a polynomial verifier surviving all exponent choices, and a lower-bound measure controlling unrestricted circuits rather than only one syntactic representation. None has been supplied here.

Sources

• S1 Arora and Barak, Computational Complexity: A Modern Approach, web draft January8,2007, Definitions6.1–6.3 and Theorem6.13; Aaronson, P ?= NP, Conjecture25. https://theory.cs.princeton.edu/complexity/book.pdf. Formulation source.
• S2 Boolean Circuits and P/poly, Cornell CS 6810, February 26, 2026. https://www.cs.cornell.edu/courses/cs6810/2026sp/lec10.pdf. Further reference; not a proof endorsement.
• E1 Richard M. Karp and Richard J. Lipton, Some Connections between Nonuniform and Uniform Complexity Classes, Proceedings of STOC 1980, pp. 302--309. https://doi.org/10.1145/800141.804678. Original nonuniform-to-uniform reference. The precise second-level collapse used here was checked in [S1], Theorem 6.13, which credits improvements by Sipser; consulted 27 September 2026.

NP versus P/poly

Definitions and mathematical statement

A Boolean circuit is a finite directed acyclic computation with binary AND/OR gates, unary NOT gates, input bits, constants, and one output. Define $\mathsf{P/poly}$ by \[ L\in\mathsf{P/poly}\ \Longleftrightarrow\ \exists C,k\ \forall n\ge0\ \exists C_n: |C_n|\le C(n+1)^k,\quad C_n(x)=1_L(x)\ (|x|=n). \] All nodes are counted. No algorithm for generating $C_n$ is required. With $\mathsf{NP}$ defined by polynomially checkable witnesses, determine whether $\mathsf{NP}\subseteq\mathsf{P/poly}$. Different languages may have different size bounds.

Formulation and concept references: [S1].

Short English statement

Can every efficiently verifiable decision problem be solved by small circuits when a different circuit may be chosen separately for each input length?

Research attempt

Current frontier.

Research check: 27 September 2026. The nonuniform convention is essential: the circuits need not have an efficient generator. The Karp--Lipton consequence of $\mathsf{NP}\subseteq\mathsf{P/poly}$ is a collapse of the polynomial hierarchy, not a known contradiction; see Arora--Barak, Theorem 6.13. [S1]. The 2026 circuit lecture retains this distinction. [S2]. Aaronson, Section 6.2.5, explains the conditional natural-proofs barrier: efficiently recognizable, large truth-table properties useful against small circuits conflict with suitably strong pseudorandom function assumptions. It is not an unconditional prohibition on all circuit lower-bound methods. [E1].

Attack route.

Counting produces hard truth tables but does not put them in $\mathsf{NP}$. A more target-specific route is to exploit SAT self-reducibility and force any candidate circuit to fail on a verifiably satisfiable input. A third route would derive an impossible consequence from the Karp--Lipton collapse, but no such impossibility is presently available in this argument. We investigate whether small test sets can certify the self-reduction route, and distinguish semantic witness circuits from general truth-table properties.

Attempt: the counting argument and its missing verifier.

A circuit with at most $s$ nodes can be described by gate types, at most two predecessors per node, and an output address. With a generous encoding this uses \[ O\left(s\log(n+s+2)\right)\quad\hbox{bits}. \tag{12.1} \] This bound includes input nodes and constants as required in the original statement. Thus the number of functions on $n$ bits computed by such circuits is at most $2^{O(s\log(n+s+2))}$. For any fixed $k$ and $s=n^k$, this is much smaller than the $2^{2^n}$ Boolean functions when $n$ is sufficiently large. Most truth tables escape the bound.

Select the lexicographically first table escaping size $n^k$ by exhaustive enumeration. This defines a function for each $n$, but its value on one input is not accompanied by a polynomial-length witness whose validity we have shown checkable in polynomial time. Moreover, a separate language for each fixed $k$ would not automatically give one $\mathsf{NP}$ language escaping every polynomial size bound. Both the explicit membership condition and the quantifier over exponents remain. Counting alone supplies neither. The standard counting/circuit framework is [S1], Section 6.1; the failed selection procedure is examined here rather than assumed efficient.

Attempt: exact witness-circuit reformulation for SAT.

Fix a conventional padded encoding of CNF formulas with input length $N$, at most $N$ variables, and a polynomial-size verification circuit. If SAT has polynomial-size decision circuits, there are polynomial-size circuits $W_N$ that, on every satisfiable formula of length $N$, output a satisfying assignment. To construct $W_N$, perform the usual prefix search: test satisfiability after fixing the next variable to zero; choose zero if possible and one otherwise. There are at most $N$ queries. Substituted formulas have length polynomial in $N$. Hardwire the SAT decision circuits for all query lengths up to that bound, and combine them using multiplexers and padded encodings. The total number of nodes is still polynomial in $N$, since the exponent of the assumed SAT family is one fixed constant. Correctness follows by induction on the prefix, keeping a satisfiable residual formula at every step.

Conversely, given such a family $W_N$, compute an assignment and evaluate the original formula on it. On a satisfiable input verification accepts; on an unsatisfiable input no assignment can pass. Hence \[ \mathrm{SAT}\in\mathsf{P/poly} \quad\Longleftrightarrow\quad \text{such uniformly correct, nonuniform witness circuits exist.} \tag{12.2} \] By polynomial-time reductions to SAT, the left side is also equivalent to $\mathsf{NP}\subseteq\mathsf{P/poly}$. No generator for $W_N$ is asserted; the word "uniformly" in the right side means correctness on all inputs at that length, not circuit-generation uniformity. One can avoid that word entirely by reading the displayed condition as $\forall F$ of length $N$, if $F$ is satisfiable then $F(W_N(F))=1$. This self-reduction is the ingredient used in the Karp--Lipton proof in [S1].

The hoped-for negative route is now precise: \[ \begin{gathered} \forall C,k\ \exists N\ \forall W\text{ with }|W|\leq C(N+1)^k\\ \exists F\text{ satisfiable of length }N:\quad F(W(F))=0. \end{gathered} \tag{12.3} \] The formula may depend on the candidate circuit. Reversing those last quantifiers would be a serious mistake: one fixed satisfiable formula always has a small circuit that ignores its input and outputs a hardwired satisfying assignment. An exhaustive counterexample search is not a proof that it terminates for every candidate at one common length. A proved termination statement with the quantifiers $12.3$ would suffice, even if the search itself were slow; the missing point is existence, not the computational cost of writing a proof.

Attempt: an obstruction to small universal test sets.

The following elementary example rules out a proposed shortcut. Let the target function on $\{0,1\}^n$ be identically zero, and let the competitor class include every point indicator \[ d_a(x)=\bigwedge_{i=1}^n \begin{cases}x_i,&a_i=1,\\ \neg x_i,&a_i=0.\end{cases} \qquad(a\in\{0,1\}^n). \] Each competitor has at most $3n+2$ nodes under the original convention, by explicitly counting inputs, negations, AND gates and an optional constant. If a test set $T$ omits $a$, then $d_a$ agrees with the zero function on all of $T$ but differs at $a$. Therefore any test set that certifies equality to this target against every competitor must be the entire cube. This target is extremely easy, yet its exact test-set requirement is exponential.

This does not exclude a SAT-specific test construction using more structure than arbitrary circuit agreement. It does invalidate the lemma "a small target circuit always has polynomially many distinguishing inputs." Random testing fares no better in this example: $q$ uniform queries detect $d_a$ with probability at most $q/2^n$. Thus a compact list of checks cannot be inferred solely from the existence of a small candidate circuit.

Stress test: the collapse is not a contradiction.

For clarity, the known collapse has a direct witness interpretation. For a true formula $\forall u\exists v\,\phi(u,v)$, the assumed SAT circuits can be compiled, as above, into a polynomial-size circuit $W(u)$ choosing a satisfying $v$ for every $u$. Conversely, existence of such a $W$ implies the original quantified formula. Quantifying its polynomial-length circuit description first gives $\exists W\forall u\,\phi(u,W(u))$, a $\Sigma_2^{\mathsf P}$ expression. This yields the Karp--Lipton collapse described in [S1], Theorem 6.13. The argument cannot finish with "the hierarchy cannot collapse," since that assertion has not been proved here.

A witness-circuit obstruction need not be a large property of all truth tables, so it might avoid the hypotheses of a natural-proofs barrier. That observation is not a lower bound or evidence that a particular construction works. Conversely, citing ordinary one-way-function existence alone without checking the quantitative pseudorandomness hypotheses would overstate that barrier. A negative resolution of this entry would imply $\mathsf P\ne\mathsf{NP}$, since uniform polynomial time supplies polynomial-size circuits. This is a dependency warning, not a proof of the harder nonuniform claim.

Outcome.

Outcome: Exploratory approach with unresolved gap. The attempt isolates an exact all-input witness-circuit target and proves that generic small-test-set compression fails even for a constant function. It also audits the two missing steps in a counting attack: placing the chosen language in $\mathsf{NP}$ and handling every polynomial exponent for one language. No superpolynomial SAT circuit lower bound or polynomial-size SAT circuit family is obtained. The auxiliary lemmas are not claimed historically new.

Sources

• S1 Arora and Barak, Computational Complexity: A Modern Approach, web draft January8,2007, Definitions6.1–6.3 and Theorem6.13; Aaronson, P ?= NP, Conjecture25. https://theory.cs.princeton.edu/complexity/book.pdf. Catalogue formulation source.
• S2 Boolean Circuits and P/poly, Cornell CS 6810, February 26, 2026. https://www.cs.cornell.edu/courses/cs6810/2026sp/lec10.pdf. Catalogue research/status reference; not a proof endorsement.
• E1 Scott Aaronson, P =? NP, in John F. Nash Jr. and Michael Th. Rassias (eds.), Open Problems in Mathematics, Springer $2016$, 1--122, Section 6.2.5. https://www.scottaaronson.com/papers/pnp.pdf. Added research source. Natural-proofs barrier and its conditional pseudorandomness hypotheses. Consulted 27 September 2026.