Anyone generating a random instance is always subject to a limitation imposed by the format. Rules can never enrich randomness, only constrain it. The question is how much freedom remains after that — and whether hardness is hiding in what remains.
A naive generator draws a fixed number of bits for every instance. A large share of that produces no valid instance at all — the format throws it away. A second share does produce valid but indistinguishable instances: mere renaming of variables and signs. What remains after that is the space in which the randomness actually moves.
| Class | Raw bits | valid | symmetry | genuinely free | discard |
|---|
The discard rate lies between 44 and 58 percent across all four classes. Roughly half of the random draw is not freedom but format coercion. That is the limitation, and it is a measurable quantity.
What was sought was a measure that distinguishes between randomly generated problem classes and carries the hardness. Every candidate was pitted against a control that could topple it.
The two classes were compared at different m — 3-SAT at 256 clauses, XORSAT at 55. At equal m the contrast vanishes: 11.3 against 13.7 percent. The symmetry share measures constraint density, not the class.
Computed across 13 classes. The gap does not separate polynomially solvable from NP-hard: 3-XORSAT sits at 1.089, right between 4-SAT and NAE-3-SAT. 4-XORSAT sits at 1.024, below 5-SAT. The measure describes clumping, not computability.
The measure is normalized by |S| and by the constraint's selectivity, and needs no clustering algorithm — it reads the structure straight off the compatibility geometry.
Calibration point. NAE-3-SAT has an exact complement symmetry: with x, ¬x is always also a solution, and both kill the same constraints. The prediction is therefore ρ = 0.500 exactly. Measured: 0.500.
It is reproducible. It is not independent: β is explained to 90 percent by the selectivity of a single constraint (R² = 0.904). The measure is largely another way of writing p_kill.
And it does not separate: 1-in-3-SAT is NP-hard and sits at 0.794, above 2-SAT (polynomial, 0.740). The same class has already toppled three other separations before.
Seven data points, and the shape of the fit was chosen after the fact. So it was pre-registered and tested on a cleanly matched pair: Horn-3-SAT has the same arity and the same selectivity as 3-SAT, but is polynomially solvable. If the residual carries tractability, β(Horn) must be > β(3-SAT).
The prediction did not fail narrowly — it inverted. The residual separation was a 1-in-35 fluke.
Near the threshold the solution set is small enough that a DPLL can output it completely as disjoint sub-cubes. From that one can draw exactly uniformly — no solver, no bias. Verified against brute force, χ²/df = 1.11.
What one can then see: the real clusters, defined as connected components under one-bit jumps within the solution set. Below, the two spaces, fully enumerated, projected onto three principal components.
Yet it is explained. A model that merely scatters three points around a shared center — fit to the measured Hamming distance, with no solution property at all — matches the rate. Exact in two of six rows, and it even overestimates the rest. Real solution sets are, if anything, less majority-closed than uncorrelated points of the same spread.
Geometrically this looks like: three uniformly drawn solutions and their majority point, in the plane of the first two principal components.
The comparison was unequal — exact backbone over all solutions against probSAT over twelve. At twelve samples, every variable with a skewed marginal distribution looks frozen, regardless of the sampler. At equal sample size, uniform drawing overestimates more than probSAT in all five rows.
What remains of the refuted claim is a calibration. The frozen estimator is massively biased at small sample sizes, and how strongly depends almost entirely on how large the backbone actually is.
A measured frozen value of 0.2 from twelve solutions is just as compatible with a true backbone of 0.04 as with 0.15. In that range the estimator carries almost no information.
Roughly half of the drawn bits are format coercion, not freedom. Between 44 and 58 percent across four classes. The space in which randomness is allowed to move is precisely quantified.
The effective number of independent solutions falls straight out of the compatibility geometry, without needing to search the solution space. Calibrated on the known case NAE-3-SAT to three decimal places. That is an instrument, independent of the hypothesis about it having failed.
Mersenne Twister, a congruential generator, and a SHA stream deliver identical ensemble figures. What is being measured belongs to the format, not the randomness source.
DPLL cube decomposition, verified exactly against brute force, χ²/df = 1.11. Runs up to n ≈ 100 near the threshold and delivers the complete solution set including real clusters — no solver, no bias. That is an instrument, independent of the fact that two hypotheses died on it.
At a true value of 0.042, eight solutions overestimate it ninefold, and even 1024 still misses by 20 %. The error is a sampling effect and hits every sampler, not just local search.
Four candidates, four times no separation between polynomial and NP-hard. What the encoding forces is selectivity — how many assignments a single constraint kills. Computability is not contained in it.
The only surviving thread from the previous day: markedly harder at unchanged α, 0 of 12 within budget. The threshold confound is untested — the same control that toppled the sign titration is still outstanding there.