2026-09-20 · article P versus NPcircuit complexityformula size

Formula size as a function on truth tables

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

A truth table lists the value of a function on every input. At n = 4 there are 16 inputs, so a truth table is a string of 16 bits, and there are 65,536 functions in all. An exact table of L over all of them is available, so hardness itself can be treated as a single function on truth tables {0,1}¹⁶ — that is, L is studied as a function that takes a 16-bit string and returns a number.

Terms used in the table: the total influence I(P) (also called total sensitivity) is the sum, over all bits, of the probability that flipping that bit changes the value. The Fourier weight is the size of each component when a function is decomposed into a sum of parity functions (XORs of some of the variables); the degree is the number of variables in the parity. A random set is a set chosen at random with the same density. Khrapchenko's bound is the classical inequality L ≥ |E|²/(|A||B|), where A is a set of inputs on which f is 1, B a set on which f is 0, and |E| the number of edges (pairs differing in one bit) between them. A linear programme is the problem of optimizing a linear objective under linear inequality constraints.

L moves by at most n under a 1-bit flip of the truth table (the Lipschitz property: a small change to the input changes the output only a little). paper · not re-examinedHence the total influence of the hardness property P_s = {L ≥ s} is about half that of a random set of the same density, and summed over s this is an identity. The weight concentrates at low degree, and what it points to is the quantity used by Khrapchenko's lower bound (total sensitivity). On the Fourier side Khrapchenko's quantity fits on one line, and under the uniform measure it is the square of the total influence:

The Lipschitz property is elementary and may well be known; the identity is one line of a layer-cake formula (the identity that slices a value at each threshold s and adds the slices up).

What Khrapchenko counts are the edges separating 1 from 0. Raise the unit of counting to 2-dimensional faces (subcubes — the sets of inputs obtained by fixing some variables and letting the rest vary freely; 24 of them at n = 4, and C(n, 2)2ⁿ⁻² in general) and count them by the type of the restriction (the function f confined to that face) — N₁, the number of faces on which exactly one corner differs from the others (the restriction is of AND or OR type); N_adj, the number on which the two 1s share an edge (the restriction is a single variable); and N_diag, the number on which the two 1s are diagonal (the restriction is XOR). This triple is invariant under the group that preserves L (the set of transformations that leave L unchanged: negating inputs, permuting variables, negating the output), so it is eligible as material for a lower bound.

For a regression approximating L by a linear expression in the triple, the explained variance rises from 76% for edges alone to 93%, and the heaviest term is the number of faces on which the restriction is XOR. But a regression is not a lower bound: used as one, this formula fails for half of the functions. The shape that can be proved as a lower bound is determined exactly by a linear programme constrained by all functions:

Since n = 4 is exhaustive, this is a finite verification over all 65,536 functions, and it can be checked in integer arithmetic alone. computationThe 334 functions that attain equality pin the coefficients down one at a time: the 1/12 on N_adj is fixed by the literal x₁ (φ = (0, 12, 0), L = 1), the 1/3 on N₁ by x₁x₂ ∨ x₃x₄ (φ = (10, 8, 0), L = 4), and the 2/3 on N_diag by XOR₄ (φ = (0, 0, 24) with L = 16, so 16/24). The regression coefficient 0.8988 is 1.35 times 2/3 — too large to be a lower bound, which is why the regression fails on half the functions. This explicit inequality, and the measurement that at n = 4 it exceeds Khrapchenko's bound without falling below it for a single function, were not found in the range searched; the framework of optimizing lower bounds on a complexity measure by linear programming is itself standard.

Carried to n = 5 with the same coefficients, the inequality is broken by the single literal x₁. Every face containing direction 1 is of the adjacent type, so N_adj = (n − 1)2ⁿ⁻²: at n = 4 this is 12, exactly equality, while at n = 5 it is 32 against a left-hand side that is still 12. paper · not re-examinedThe coefficients were stuck to the number of faces (24 → 80). Divided by that number, the density form does not fail on the side where L is exact — the 662,176 functions of n = 5 with at most 7 leaves. Solving the linear programme on that corner alone, however, disagrees with the n = 4 answer down to the sign of the coefficient on N_adj, and returns almost the same shape (a constant term and small coefficients) as the negative control in which L is shuffled (a control experiment that runs the same procedure with the values of L scrambled, and should find nothing). As long as only the easy side is in view, the linear programme is saying no more than “L ≥ a constant”. computation

Generalizing face types to the types of k-dimensional subcubes puts every lower bound of this kind inside a linear programme. For a type T (a set of k-variable functions that are carried to one another by permuting the variables), let ν_T(f) be the fraction of k-dimensional subcubes whose restriction has type T. Among bounds of the form L(f) ≥ Σ_T c_Tν_T(f), the strongest value for a given g is, by linear-programming duality (the mirror problem with the same optimal value),

paper · not re-examinedThat is, the least L-cost of a mixture that reproduces g's profile of types. It is the level-k instance of a hierarchy of linear programmes whose only constraints are local statistics (the frequencies of the types of restrictions to subcubes of size k). The strength is decided there, so proving a large lower bound for g requires that no easy function shares g's profile.

The functions all of whose 2-faces are diagonal are exactly the 2 functions XOR_n and its negation (all second differences are 0 ⟺ degree ≤ 1 as a polynomial over the two-element field F₂, and full support gives XOR_n). Since the only function sharing that profile is its own negation, level 2 alone gives V₂(XOR_n) = L(XOR_n) exactly. paper · not re-examinedThat value equals n² only when n is a power of 2: L(XOR₃) = 10, which is 1 above Khrapchenko's 9. computationknownOver all of n = 4, level 2 (6 types, 24 faces) determines L exactly for 113 of the 328 profiles and level 3 (22 types, 8 faces) for 324 of 400. Raising the level makes it strictly stronger. computationThe obstacle is not a ceiling on the linear form but a collision of profiles: the number of types at level k is of order 2^2k/(2^kk!) (a sketch), so local statistics with k = O(1) cannot tell functions apart.

Measuring Khrapchenko's quantity with a different evaluator does not move the ceiling. From |E| ≤ n·min(|A|, |B|) one gets Kh ≤ n², and the Koutsoupias-type bound L ≥ σ_max(M)²known, which measures the spectrum (the largest singular value σ_max) of the bipartite adjacency matrix M (the matrix of edges between A and B), gives Ko ≤ n² from σ_max(M) ≤ n; allowing the freedom to choose subsets changes nothing. paper · not re-examinedEquality moreover requires M to be n-regular on both sides, and since the cube is connected the colouring propagates to the whole of it and f must be parity — the ceiling is attained by XOR_n and its negation only. Of the 114 hardest functions at n = 4, this family proves the true value 16 for 2 of them; for the rest it reaches 15, 14 or 12. In value Ko is much closer to L, yet its correlation with L is lower. Correlation is scale-invariant, so this is not a matter of a constant factor: moving to the spectrum also picks up information in directions unrelated to L. computation

Instead of trying evaluators one at a time, one can measure the best lower bound obtainable in principle from a given invariant. With the invariant taken to be the Fourier weight profile W(f) = (W₀, …, W_n), the best obtainable from it is B(f) = min{L(g) : W(g) = W(f)}. At n = 4 there are only 144 distinct profiles (coarser than the 222 NPN classesknown — the classes of functions carried to one another by negating inputs, permuting variables and negating the output), yet the ceiling reaches 16 = max L, and it is reached not by the 2 XOR functions but by all 114 functions with L = 16. Those 114 occupy exactly 4 profiles, and no easy function is mixed into those 4 classes. The confusion is on the easy side: the largest loss, 6, occurs in the profile whose weight sits entirely at degree 2 — the class in which x_i ⊕ x_j with L = 4 lives together with a function with L = 10. computationReduce the invariant to just the two numbers total influence and density, and the ceiling is again reached by the 2 XOR functions only.

But B is defined using the exact table of L as an oracle (a device that simply hands over the answer); it is not a usable method of proof. What is measured is the information content of the profile — “at n = 4 there is still room to look at the weights alone and not mistake which functions are hardest” — and no more. At n = 5 the exhaustive table of L (2³² functions) is out of reach, so the same measurement cannot be made, and L is exact only on the corner with few leaves. Every number here is confined to n = 4 and to that corner of n = 5, and none of it touches the barriers (it is caught by none of the three barriers of the first page, and it advances past none of them either).

And whether the family of methods is changed or the level is raised, the function that reaches the ceiling is one and the same. Counting edges, its spectral version, and level 2 of the linear programme over type densities all give n² for XOR_n exactly, and all fall short of the true value for every other hardest function. “The hardest functions” and “the functions whose hardness can be proved” barely overlap.

• How strong the linear programme over type densities is for n ≥ 5. Levels 2 and 3, computed over all of n = 4, have not been carried to the side of n = 5 where L is exact (the 662,176 functions with at most 7 leaves). The negative control for level 3 (solving the same programme with L shuffled) has not been run either.
• Quantifying the collision of profiles. The counting of types against functions at level k (that k = O(1) cannot tell functions apart) has not been made quantitative, and how the slack 0.571 of the bound from φ alone grows with n has not been measured.
• Gaps on the faces and the evaluators: a classification of the 334 equality cases into orbits of the group; the exact value of L(XOR₅) (at least Khrapchenko's 25, with no upper bound from a construction measured either); the reason the spectral version correlates less well than Khrapchenko (which directions of information are mixed in). The measurement of Fourier weight profiles does not extend to n = 5, where no exact exhaustive table of L exists.

No claim on this page is machine-checked.

References