2026-09-20 · article P versus NPcircuit complexitynegation-limited circuits

P versus NP — where the ladder of negations stops

Each claim carries one of the following labels, which grade how firmly it is established.

Leanmachine-checked — there is none on this page paperproved, not machine-checked; “re-examined” is added where the proof was read again on a separate occasion and did not break paper · not re-examineda proof is written down but has not been through a second reading computationchecked on this machine, within the range stated; not a claim made to the outside knowna known theorem, or a check of the literature; † marks a standard fact cited without fetching the original

Can every problem whose answers can be checked in polynomial time also be solved in polynomial time?
(If so, P = NP. In the language of circuits: showing that some function in NP has no polynomial-size circuits — NP ⊄ P/poly — would imply P ≠ NP.)

A “circuit” here is a diagram of AND, OR and NOT gates wired together to compute a Boolean function, and the number of gates is its size. P/poly is the class of functions computable by polynomial-size circuits. To show that a function is hard is to prove a lower bound: “any circuit computing this function needs at least this many gates”.

Past attempts have stopped at one of three barriers. A barrier is a theorem saying “no argument of this type can settle P versus NP”, and three are known. known

• Relativization — an argument that still works when the machines are given an “oracle” (an imaginary device that answers any question in one step) cannot be used.
• Natural proofs — an argument that proves hardness through “a property held by most functions and efficiently decidable” cannot work if strong pseudorandom generators (devices producing sequences that no efficient computation can tell from random) exist.
• Algebrization — an argument that still works when one side is given a polynomial extension of the oracle (a low-degree extension) cannot be used either.

The roads taken, and where each stopped:

ACC⁰ and TC⁰ are families of constant-depth circuits (the former allows gates that count modulo a number, the latter majority gates); NEXP and NQP are the classes of nondeterministic exponential and quasi-polynomial time. perm (the permanent) and det (the determinant) are two polynomials built from a square matrix; the goal of geometric complexity theory is to show that the permanent cannot be expressed by a determinant of polynomial size.

The only existing technique that avoids all three barriers at once is, in effect, Williams's method. The way it avoids them comes down to “opening the object”: it touches the description of a circuit itself rather than an oracle (non-relativizing, non-algebrizing), and it treats a single point rather than a population of functions (not large). Williams 2013 shows, as an equivalence for NEXP lower bounds, that constructivity is unavoidable and largeness is unnecessary. What is forbidden is using “a property held by many functions and computable”. Whether the same equivalence holds for NP has not been checked here.

Many failed “proofs” run straight into one of the three — they still go through with an oracle attached, or they would give the same conclusion for XORSAT, perfect matching and the Tardos function, or they amount to distinguishing random functions from pseudorandom ones. Woeginger's web page collecting claimed “proofs” of P versus NP has 115 entries (62 for P = NP, 50 for P ≠ NP, 3 for undecidability). known

Monotone circuits (0 negations) have exponential lower bounds; general circuits have only 3.1n. One numerical parameter connects the two continuously — the number t of negation gates the circuit may use. The road of raising t one rung at a time is what this article calls the “ladder”. known

• Markov's theorem: the number of negations necessary and sufficient to compute f is I(f) = ⌈log₂(d(f) + 1)⌉, where d(f) is the largest number of times the value changes 1 → 0 along an increasing chain of inputs (a sequence in which the bits of the input are switched on one at a time). Hence ⌈log₂(n + 1)⌉ negations suffice for every function of n variables.
• Fischer's theorem: restricting a circuit to ⌈log(n + 1)⌉ negations costs size 2C + O(n² log² n). So a superpolynomial lower bound for a function in NP against circuits with ⌈log(n + 1)⌉ negations is already NP ⊄ P/poly.

From here on, NC¹ is the class of functions computable by circuits of depth about log n and polynomial size (the same power as polynomial-size formulas).

What carries the NC¹ result is Rossman's Lemma 1.3 (Holley's monotone coupling). “1/2 + δ hard” means that no circuit of the given size answers correctly, on an input drawn at random, with probability reaching 1/2 + δ. If the distribution satisfies the FKG lattice condition (a condition guaranteeing positive correlations) and the monotone function f is balanced under it (its two values are equally likely), then

The price of 1 negation is that the provable correlation margin δ is halved, so the usable t is at most about log₂(1/δ). The margin obtainable against monotone NC¹ is δ = n^−1/2+ε, and the climb stops at (1/2 − ε) log n. What breaks is not on the side of circuit structure but on the side of the strength of the average-case lower bound for monotone circuits (a lower bound on the success rate over random inputs). The same “1 negation = a factor of 2” appears for the alternation number that can be handled (Markov), for the number of independent copies that can be protected (Jukna), and for size (Fischer).

Raising t alone is not enough. There is an explicit monotone multi-output function in P that requires superpolynomial size unless log n − O(log log n) or more negations are allowed (Jukna, Theorem 10.21). The corresponding question for an explicit monotone function with a single output (Research Problem 10.23 there) is open. known

From here on the number of variables is written N (quotations from the literature keep n). A “measure” is a probability distribution on the inputs. The uniform measure draws every input with equal probability; a product measure draws each variable independently; an exchangeable measure is one in which the probability depends only on the weight |x| of the input (the number of bits that are on).

The ceiling n^−1/2 is a matter of principle

Every monotone function agrees with one of 0, 1, x₁,…,x_n, MAJ (the majority function) with probability 1/2 + Ω(log n/√n) (O'Donnell–Wimmer 2009). All of these are in monotone NC¹, so under the uniform measure no monotone function can be 1/2 + o(log n/√n) hard for monotone NC¹. Rossman states this limit in his paper himself, and writes that under a product distribution one cannot hope for hardness better than 1/2 + n^−1/2 even against polynomial-size monotone circuits. known

Where the 1/2 comes from fits on one line. If the measure is exchangeable (determined by the weight |x| alone) and f is balanced, then with φ(s) the density of f on the layer of weight s,

paper · not re-examinedThe correlation with a threshold is “the speed at which φ leaves 1/2 (the slope) × the number of layers over which the weight spreads”. The Kruskal–Katona theorem forces a slope of at least 1/n to log n/n, and under the uniform measure the weight spreads over √n layers, which gives log n/√n. The 1/2 comes from the fact that under a product measure the Hamming weight (the weight |x|) lives on only √N layers. The same √N appears in two other places: every function is 0.01-approximated by a circuit with (1/2) log n + O(1) negations (Blais–Canonne–Oliveira–Servedio–Tan); and pseudorandom functions require log n − O(1) negations, but that proof does not carry over to weak pseudorandom functions — random samples concentrate around the middle layer and no chain can be built (Guo–Malkin–Oliveira–Rosen). known

Changing the product measure does not lower the ceiling: with σ² the variance of the weight, under any product measure a monotone function agrees with some threshold with probability 1/2 + c/(σ√(log σ)), and this floor — the margin of agreement that even simple functions always achieve, beyond which hardness cannot go — is lowest for the uniform measure, where σ is largest (the proof is of a known type). paper · not re-examinedFor general measures satisfying the FKG lattice condition no proof is attached.

The band lemma, and the top of the ladder

paperre-examined. A band is the part of the input space on which the weight is confined to a range. On a band a ≤ |x| ≤ b made of L layers of weight, any circuit of size s can be converted into a circuit with ⌈log₂L⌉ negations, size 2s + poly(N) and depth +O(log N). L = 1 is Berkowitz's slice functions and L = N + 1 is Fischer's theorem; this is the interpolation between them. The proof is just Fischer's construction restricted to the band; the statement with these dimensions was not found in the range searched, but it should be regarded as folklore (a fact known to specialists though not written up in a paper).

Applied to the band N/2 ± √N under the uniform measure (L = 2√N + 1; the mass outside the band is below 0.28):

If an explicit f ∈ mSAC¹ is 1/2 + 0.2 hard under the uniform measure for NC¹ circuits with (1/2) log₂N + 2 negations, then f ∉ NC¹, that is, NC¹ ≠ LOGCFL. paperre-examined

mSAC¹ is the monotone version of LOGCFL, a class that contains NC¹ and is believed to be larger. NC¹ ≠ LOGCFL is a far weaker separation than P ≠ NP, but it too is open.

This is a statement at constant advantage; to keep a quality of 1/poly the top rises to (1/2) log N + (1/2) log log N + O(1). Rossman's (1/2 − ε) log n is half of the worst-case ladder (of length log n), but on the uniform average-case ladder it is ε log n + O(1) rungs from the top.

The gap on the side of technique, ε log n, remains far larger than the width log log n of the window. Fischer's construction can be read as “binary-search the Hamming weight with ⌈log(n + 1)⌉ threshold queries, and once the layer is known make one monotone query” (the correspondence between circuits with t negations and decision trees of depth t + 1 with monotone queries falls within the framework of Amireddy–Jayasurya–Sarma 2023known; that the dimensions agree has not been checked against the body of that paper). Under the uniform measure this becomes (1/2) log n because the search range is √n layers. The natural-proofs barrier applies to this ladder only on the last O(1) rungs, and conversely applies in full to slice functions (L = 1). paper · not re-examined

Reading the proof of Rossman's Theorem 1.1 (k-CYCLE — the problem of deciding whether a directed graph contains a cycle of length k — is 1/2 + n^−1/2+c hard for small monotone formulas under the critical random graph Γ) lemma by lemma, the only places that use the fact that the input measure Γ is a product measure are the two estimates (23) and (24) of Lemma C.4. Both are Poisson approximations; (24) says that planting a path in Γ changes it by total variation distance (a measure of how different two distributions are) O(k/√n). Janson's inequality and stochastic domination concern the independence of the noise that the prover chooses; the lemma on persistent minterms (a minterm is a minimal input that makes the function true), the lower bound on pathset complexity and the covering for negations (Lemma F.2) do not involve the measure. In Rossman's words, the noise “lives inside the variance of the random graph Γ”. known The proofs of (23) and (24) are deferred to the full version of the paper, whose whereabouts have not been checked.

Replace the input measure by the conditional measure “the number of edges lies in a band of L layers”: paper · not re-examined

• (24) breaks. Planting a path adds k − 1 edges and pushes the mass at the upper end of the band outside, so the total variation distance is at least (k − 1)/L — and a monotone threshold detects it. Holley's monotone coupling is left with a deficit of at least 1/L from the same source. The obstacle has a name: chain length — a monotone step moves the weight, and a chain inside a band of L layers has length at most L.
• Black-box conditioning gives the same value. If f is 1/2 + δ hard under the base measure, the advantage on a band of mass q is at most 2δ/q, which with Rossman's value is O(N^ε/L). With t negations it stays o(1) for t ≤ log₂L − ε log₂N − ω(1). The distance ε log N to the top of the ladder, ⌈log₂L⌉, does not depend on L — narrowing the band lowers the top and the point reached by the same amount.
• The floor on a band is “number of layers × slope”. It is of order (L − 1) log N/N (the log N part is a sketch): 0 at L = 1, and back to log N/√N at L ≈ √N. Computed exactly for the tribes function, it is 0.25, 0.25, 0.25, 0.23 times (L − 1)·slope (n = 264; L = 3, 5, 9, 17). computation
• The trade between floor and noise. Under an exchangeable measure whose weight spreads over L layers, the floor requires δ ≥ c·L·κ (κ the slope per layer) and the technique requires δ ≥ C·w/L (w the weight of the monotone noise). The product is independent of L: δ ≥ √(wκ) ≈ √(w/n). Whatever the width, an exchangeable measure returns to n^−1/2, and Rossman's Γ sits at the optimal point (a statement inside this technique).

The road of narrowing the band does not enter the window. The loss 2^t+1 − 1 in Lemma 1.3 is the loss from summing over the whole space, ignoring the cells cut out by the monotone queries. Let D_j be the sum, over the leaf cells of a tree of monotone queries of depth j − 1, of the mass of monotone pairs covered by the leaf's monotone circuit. Then the mass covered by a circuit with t negations is at most Σ_{j ≤ t+1} D_j, and the trivial bound D_j ≤ 2^j−1D₁ is Lemma 1.3. If D_j ≤ K·D₁ could be shown, the loss would fall to K(t + 1). paper · not re-examinedIn a toy case with queries restricted to dictators (functions that look at a single variable) and f = MAJ_N, D₂/D₁ = 0.583, 0.633, 0.668, 0.766, 0.884, 0.961 (N = 5, 7, 9, 21, 101, 1001; the trivial bound is 2). computationThere is no tool that shows this for queries by general monotone circuits.

The way out of the trade is to make the slope 0 with a measure that is not exchangeable. Rossman's input is a directed graph cycling through k vertex classes (n vertices each); the variables are the N = kn² edges, and Γ is the product measure that includes each edge with probability p ∼ (ln 2)^1/k/n. Let Γ₀ be Γ conditioned on having no k-cycle, and ⊙ a uniform k-cycle.

Weight-neutral planting — the floor is called “the number of paths”

“Planting” means deliberately inserting a structure such as a cycle into a random graph. The question to be decided is “has a cycle been planted?”, and the 1-side and 0-side are the distributions of inputs for which the answer should be 1 and 0. Take the 1-side to be Γ₀ ∪ ⊙ and the 0-side to be Γ₀ ∪ (k edges, 1 drawn uniformly from each edge class). The distributions of the number of edges on the two sides then coincide, and thresholds of the edge count, single edges, and functions of the in-degrees alone or the out-degrees alone have advantage 0. The floor still does not drop. With c = pn, the threshold of P_j, the number of directed paths with j edges, has advantage

For k = 4 this is 0.101·√(k/n) at P₂, and for j = k − 1 with c → 1 about 0.17·k/√n. paper · not re-examinedIn samples, the advantage of P₂ × √(n/k) is 0.097, 0.104, 0.094, 0.098 (k = 4; n = 30, 60, 100, 200), within 8% of the formula. computationThis restates that the right-hand side O(k/√n) of (24) is an equality in order of magnitude, and the same statistic was already the floor under Γ. Even with a neutral measure, the proof itself moves the weight where it compares “the base” with “the base with a path planted” — the comparison needed to say that a cycle is a minterm.

Planting the 2-cover of a cycle

Give the planting on the 0-side the same local structure. Choose 2 vertices from each class and, for each edge class, plant one of the two perfect matchings of K_2,2 (parallel or crossed). If the number of crossings is even the result is 2 k-cycles (the 1-side); if odd, 1 cycle of length 2k (the 0-side); the (in, out) degrees of every vertex agree. The side is the parity of twist bits hidden one in each of the k edge classes. paper · not re-examined

• A function that fails to look at even one edge class has advantage exactly 0 (monotone or not).
• The threshold of the number of paths with d < k edges has advantage O(poly(k)·n^{−⌈k/d⌉/2}) (a sketch). In samples with (n, k) = (30, 4) and 200,145 pairs, the advantage of P₂ is −0.00007 ± 0.00010. computation
• The number of k-edge paths with distinct endpoints correlates with the 0-side at −Θ(√(k/n)) (monotone, but in the opposite direction): −0.0310 ± 0.0003 in samples (n = 30), with ratio 0.76 from n = 30 → 60 (√(1/2) = 0.71). computation

The one-sided floor drops below n^−1/2; the two-sided floor (in absolute value) stays. The statistic that keeps it, however, has n^k+1 terms, and whether it fits in polynomial-size monotone formulas as k → ∞ is not known. In the negative control of the computation (a control experiment that repeats the measurement on pairs that should show no difference; here, pairs with the same kind planted at independent positions) there is one unexplained deviation of size 10⁻³, about 2.6σ, so the resolution of “0” should be read as 10⁻³.

The alternating-sum lemma — extending to negations needs no Holley coupling

Under a weight-neutral measure the two sides have no comparable pairs, and no monotone coupling exists. Even so:

For any two distributions, the advantage of a circuit with t negations and size s is at most 2^t+1·δ₂, where δ₂ is the largest absolute value of the advantage of monotone circuits of size at most (2t + 1)s (two-sided monotone hardness). paper · not re-examined

Corollary: if f ∈ NC¹ then a circuit with ⌈log₂(N + 1)⌉ negations computes f exactly, so δ₂ < 1/(8(N + 1)) under some pair of distributions would give f ∉ NC¹. Under a product measure the ceiling of §03 blocks this line in principle. Under the 2-cover measure the simple statistics found do not obstruct it (d < k/4). So lowering that floor by a proof carries the same weight as NC¹ ≠ NL (NL is the class of nondeterministic logarithmic space, which contains NC¹) — that the floor drops, and that a proof reaches the dropped floor, are different things. Using Rossman's proof as a black box gives, under the 2-cover measure too, up to (1/2 − c) log n negations (the same value). What blocks going further is the (ℓ + 1)k²/√n that Lemma 4.5 pays additively through a union bound. Only the signed difference is small, so a proof that uses cancellation is needed, but counting minterms carries no sign.

A null hypothesis matching the expected number of edges appears in Addario-Berry–Angel–Lugosi–Rácz–Schramm. A treatment, for monotone circuits, of a planting that matches the whole degree sequence, and an explicit form of the alternating-sum lemma, were not found in the range searched; the latter is a one-line argument within the range of folklore.

The model: the inputs are x₁,…,x₄ only (no constant inputs). Gates are binary AND and OR and unary NOT, and size is the number of AND/OR gates (NOT is not counted). C_t(f) is the smallest size of a circuit using at most t NOT gates, C_∞ the value with unlimited negations, C₀ the monotone circuit size. All 65,536 functions are counted by exhaustive enumeration of circuits in canonical form.

The price of a negation appears in one place only

At n = 4 the price of monotonicity is zero, and so is the price of going from 3 negations to 2. A price appears only when the number is cut below what suffices for every function (2, by Markov's theorem), down to 1. The maximum, 4 gates, is taken not by a symmetric function but by a multiplexer, in which both uses of negation are essential (one inside the select signal, one in the selection itself). The ratio 8/4 = 2 is the same number as Fischer's coefficient, but in general it is additive, not multiplicative: the multiplexer with k address bits has d = k and I = ⌈log₂(k + 1)⌉, and for t ≥ I, C_t ≤ C_∞ + O(k log k). paper · not re-examinedIf the select signal is monotone the price is 0 even at n = 4 (x₃ ? x₂ : x₁ has C₁ = C₂ = 3). This shape is specific to the smallness of n = 4; asymptotically an exponential price is already paid at t = 0 by monotone functions.

The symmetric functions are explained by the rigidity that fixes the input of the negation to a unique threshold function (Tanaka–Nishino–Beals). C₁ = 9 for E₁ (exactly 1 one) is the value that carries the whole of C₀ = 7 of the fixed input T₂. computation

A circuit with 1 negation does not decompose into a sum of monotone blocks

A circuit with 1 negation can be written f = M(x, ¬h(x)) with h and M monotone. D₁ is the sum obtained by optimizing separately a monotone circuit for h and a monotone circuit that has ¬h as a free input. If D₁ = C₁ always held, the exponential monotone lower bounds would transfer to negation-limited circuits with a loss of only t stages. It already fails at n = 4.

The source of the gain is sharing in monotone multi-output circuits; it is not specific to negation. The largest observed difference, 6, and the largest γ, 6, occur at the same pair (T₂, T₃), so the inequality is attained exactly at the maximum. The proof of Fischer's theorem is itself a construction by sharing — it builds n threshold functions together in one monotone circuit — and E₂ is its n = 4 version. For the multiplexer the difference is 0, so “the price of a negation” and “the gain from sharing” are different phenomena. A statement that negation-limited size decomposes into the sum of the sizes of monotone blocks was not found in the range searched, Chapter 10 of Jukna's book. The road of climbing the ladder by decomposition turns into a different open problem: multi-output monotone lower bounds.

Controls: six for the negation-limited enumeration (the 166 monotone functions are reproduced; zero violations of the lower-bound side of Markov's theorem; the table for t = 3 agrees with t = 2 in every cell; agreement with an enumeration without pruning; C_t ≥ C_∞ against an independent table; the rigidity theorem). C₂ is exact for 61,184 of 65,536 functions (93.4%) and C₁ for 20,252 of the 23,760 computable with 1 negation (85.2%); the rest have lower bounds only. D₁ is exact for all 23,760 functions (eight controls). An independent implementation reproduces C₁ on 100 functions with C₁ ≤ 6, 100/100; the cells with C₁ from 7 to 9 have not been reproduced.

Exhaustive computation at n = 4 does not touch the barriers. With the truth table in hand anything is decidable in time 2^O(n), so the condition “constructive” is empty; moreover at n = 4 explicit families such as the symmetric functions reach the overall maximum, so the hardness of almost all functions and the hardness of an explicit single point have not yet separated (Knuth too writes that symmetric functions are among the hardest to evaluate when n is small and among the easiest for n ≥ 10known).

In the non-commutative setting (Nisan's algebraic branching programs) the minimal size is given exactly by ranks, but in exhaustive computation for n ≤ 8 the ranks for perm and det coincide completely (both are binomial coefficients). computationWhere they differ is the dimension of the Lie algebra of the stabilizer (the stabilizer is the set of linear transformations that leave the polynomial unchanged, and the dimension of its Lie algebra is the number of its continuous parameters):

What geometric complexity theory actually handles is the padded ℓ^m−nperm_n, but padding adds exactly 1 dimension of symmetry (the simultaneous scaling of ℓ and x), and the determinant side likewise gives 2n² − 1 (7, 17, 31 for n = 2, 3, 4). The difference in continuous symmetry stays linear against quadratic in n. This does not, however, translate into an obstruction. A small stabilizer does not by itself prevent inclusion in an orbit closure (on the boundary the stabilizer can on the contrary grow), and as in §01 the road of occurrence obstructions is closed. The verbatim statement “2n − 1, independent of m” was not found in the range searched, but it is an elementary computation and may be obvious to a specialist.

Where the open items that have moved now stand is collected in What remains. Only what is open at present is listed here.

The side of formula size (De Morgan formula size as a function on truth tables) is on a separate page.

• No tool enters the window (of width log log N). Lemma 1.3 cannot enter because of the ceiling, the road of narrowing the band is closed by chain length, and exchangeable measures return to n^−1/2.
• Multi-output monotone lower bounds. Climbing the ladder by decomposition needs a lower bound on the multi-output monotone complexity of the tuple (h, g⃗). Jukna's Research Problem 10.23, for an explicit monotone function with a single output, is also open.
• A multiplicative version of Lemma 4.5 under the 2-cover measure. Can the additive loss (ℓ + 1)k²/√n be replaced by a conditional form? A question that should begin with a search for counterexamples; not begun.
• Exhaustive computation at t = 2 (the two-stage decomposition D₂ against C₂) has not been begun. The estimate is 90 hours.
• Gaps in the n = 4 tables: the 3,508 functions whose value is undetermined beyond C₁ ≥ 10, the 4,352 undetermined beyond C₂ ≥ 9, the upper bound for 0x1886, 6 pairs for γ. The function-by-function equality D₁ − C₁ = γ has not been measured.
• Gaps on the paper side: the ceiling for general FKG measures; the advantage of path counts under the 2-cover (a sketch); whether the number of k-edge paths with distinct endpoints fits in monotone NC¹ as k → ∞; that Rossman's proof goes through under the planted measures (a sketch).
• The cause of the deviation of about 2.6σ (size 10⁻³) left in the negative control of the computation.
• Checking the originals of the references marked †, the body of Amano–Maruoka 2005, and the full version of Rossman's paper (the proofs of (23) and (24)).

No claim on this page is machine-checked. Of the paper lemmas, only the band lemma and its corollary have been through a second reading, and everything described as not found in the range searched is a short argument within the range of folklore. This line of work is stopped here.

References

Range searched: arXiv searches (negation-limited circuits, monotone circuits average-case, slice functions monotone circuit, pathset complexity, planted cycle detection, and others). Citation lists were not consulted.