# RRLS v0.18 — Algebraic Rank Wall ## Status **P = NP is not proved.** v0.18 identifies an exact global fiber-occupancy invariant for Boolean CNF and then measures the cost of making it complete. --- ## 1. Exact Boolean Nullstellensatz rank Encode each clause C by the polynomial p_C over GF(2) that equals 1 exactly on Boolean assignments falsifying C. Work in the Boolean quotient x_i^2 = x_i. Let M_d(F) contain the coefficient vectors of all monomial multiples m * p_C whose resulting multilinear degree is at most d. Then a degree-d algebraic UNSAT certificate exists exactly when 1 is in RowSpan_GF(2)(M_d(F)). At full Boolean degree n this hierarchy is complete for finite Boolean formulas. The implementation was checked against brute force on 30 small random CNFs: 30/30 exact agreement. So this is not a heuristic score. A positive row-span result is an exact UNSAT certificate in the implemented Boolean-ring system. --- ## 2. Measured degree wall | family | scale | cases | variables | clauses | median_degree | capped | median_last_rows | median_seconds | |:---------------|--------:|--------:|------------:|----------:|----------------:|---------:|-------------------:|-----------------:| | 3XOR-as-CNF | 8 | 1 | 8 | 44 | 3 | 0 | 148 | 0.00281944 | | 3XOR-as-CNF | 10 | 1 | 10 | 52 | 3 | 0 | 178 | 0.00749049 | | 3XOR-as-CNF | 12 | 1 | 12 | 60 | 3 | 0 | 205 | 0.013766 | | 3XOR-as-CNF | 14 | 1 | 14 | 68 | 3 | 0 | 231 | 0.0242567 | | pigeonhole-raw | 3 | 1 | 6 | 12 | 3 | 0 | 195 | 0.000592117 | | pigeonhole-raw | 4 | 1 | 12 | 34 | 5 | 0 | 21304 | 0.0731891 | | pigeonhole-raw | 5 | 1 | 20 | 75 | nan | 1 | 1.5e+06 | 20.8388 | | random3-unsat | 8 | 2 | 8 | 40 | 4 | 0 | 810 | 0.00737787 | | random3-unsat | 10 | 2 | 10 | 50 | 4.5 | 0 | 3236.5 | 0.0335715 | | random3-unsat | 12 | 2 | 12 | 60 | 4.5 | 0 | 5634 | 0.0891992 | | random3-unsat | 14 | 2 | 14 | 70 | 5 | 0 | 15075 | 0.278859 | Notable observations: - globally inconsistent 3-XOR encoded as CNF refuted at degree 3 throughout the tested sizes; - random UNSAT 3-SAT required degree 4–5 in the tested range; - raw pigeonhole rose from degree 3 (3 pigeons) to degree 5 (4 pigeons); - the 5-pigeon / 4-hole encoding has 20 Boolean variables and did not refute by the degree-7 run before hitting the 1,500,000-row cap. The last item is a resource-capped experiment, not a degree lower-bound proof. --- ## 3. Why degree is the computational coordinate The degree-d Boolean monomial feature space has N(n,d) = sum_(i=0)^d binom(n,i) coordinates. For fixed d: N(n,d) = n^O(d), so constant degree gives polynomial-size linear algebra. For d growing proportionally with n, the feature space is exponential. Thus this rank formulation transforms SAT into a very precise question: > Can every UNSAT instance be canonically represented/refuted in a polynomial-size > algebraic feature space? Polynomial Calculus / Nullstellensatz lower-bound theory shows that high degree is required for important formula families, so the answer is no for this fixed algebraic proof language. --- ## 4. Affine Rotation Invariance — exact theorem Let phi be an invertible affine transformation of Boolean GF(2) coordinates. Suppose F has a degree-d certificate sum_i q_i f_i = 1 with every product q_i f_i of degree at most d. Apply phi: sum_i phi(q_i) phi(f_i) = 1. An affine substitution does not increase polynomial degree. Therefore phi(F) has a degree-d certificate. Applying phi^(-1) gives the reverse implication. Hence d_NS(F) = d_NS(phi(F)). So **no invertible affine rotation of the Boolean coordinates can reduce the minimum Nullstellensatz refutation degree.** The benchmark confirms the theorem numerically: every tested affine basis had zero successes at degree one below baseline, and the truncated row-space ranks were invariant. | case | n | baseline_degree | target_degree | rotation_steps | trials | successes | caps | median_rank | max_rank | median_seconds | |:------------------|----:|------------------:|----------------:|-----------------:|---------:|------------:|-------:|--------------:|-----------:|-----------------:| | pigeonhole-4x3-d5 | 12 | 5 | 4 | 4 | 20 | 0 | 0 | 755 | 755 | 0.0218906 | | pigeonhole-4x3-d5 | 12 | 5 | 4 | 8 | 20 | 0 | 0 | 755 | 755 | 0.0237811 | | pigeonhole-4x3-d5 | 12 | 5 | 4 | 16 | 20 | 0 | 0 | 755 | 755 | 0.0295961 | | pigeonhole-4x3-d5 | 12 | 5 | 4 | 32 | 20 | 0 | 0 | 755 | 755 | 0.0406624 | | random3-n10-d5 | 10 | 5 | 4 | 4 | 30 | 0 | 0 | 331 | 331 | 0.0159033 | | random3-n10-d5 | 10 | 5 | 4 | 8 | 30 | 0 | 0 | 331 | 331 | 0.0169106 | | random3-n10-d5 | 10 | 5 | 4 | 16 | 30 | 0 | 0 | 331 | 331 | 0.0243482 | | random3-n10-d5 | 10 | 5 | 4 | 32 | 30 | 0 | 0 | 331 | 331 | 0.0362657 | | random3-n14-d5 | 14 | 5 | 4 | 4 | 20 | 0 | 0 | 774 | 774 | 0.0803929 | | random3-n14-d5 | 14 | 5 | 4 | 8 | 20 | 0 | 0 | 774 | 774 | 0.0883687 | | random3-n14-d5 | 14 | 5 | 4 | 16 | 20 | 0 | 0 | 774 | 774 | 0.113301 | | random3-n14-d5 | 14 | 5 | 4 | 32 | 20 | 0 | 0 | 774 | 774 | 0.164124 | | random3-n8-d4 | 8 | 4 | 3 | 4 | 30 | 0 | 0 | 40 | 40 | 0.00300648 | | random3-n8-d4 | 8 | 4 | 3 | 8 | 30 | 0 | 0 | 40 | 40 | 0.00299004 | | random3-n8-d4 | 8 | 4 | 3 | 16 | 30 | 0 | 0 | 40 | 40 | 0.00433908 | | random3-n8-d4 | 8 | 4 | 3 | 32 | 30 | 0 | 0 | 40 | 40 | 0.00594362 | This is a significant correction to the earlier RRLS intuition. Linear coordinate rotation can reveal sparse formulas such as parity, but it cannot lower this particular algebraic proof-degree invariant. --- ## 5. Nonlinear reversible coordinates v0.18 next tested exact Toffoli-style Boolean automorphisms x_i -> x_i XOR (x_j x_k). Unlike affine transformations, these can change degree, and the degree-d row-space rank did change. Measured: | case | n | baseline_degree | target_degree | trials | successes | caps | min_rank | median_rank | max_rank | total_seconds | |:------------------|----:|------------------:|----------------:|---------:|------------:|-------:|-----------:|--------------:|-----------:|----------------:| | pigeonhole-4x3-d5 | 12 | 5 | 4 | 220 | 0 | 0 | 740 | 742 | 749 | 4.82676 | | random3-n10-d5 | 10 | 5 | 4 | 360 | 0 | 0 | 286 | 306 | 321 | 5.92699 | | random3-n14-d5 | 14 | 5 | 4 | 220 | 0 | 0 | 621 | 700 | 737 | 18.8444 | | random3-n8-d4 | 8 | 4 | 3 | 168 | 0 | 0 | 27 | 33 | 39 | 0.478215 | No tested single-Toffoli map lowered the minimum refutation degree by one for the four chosen hard instances. This is an empirical failure of a small nonlinear transform family, not an impossibility theorem for nonlinear reversible transformations. --- ## 6. Relation to known algebraic proof complexity The experiment is now directly in the territory of Polynomial Calculus, Nullstellensatz, Gröbner-basis algorithms and Ideal Proof System research. Known results establish high Polynomial Calculus degree for expander-based formula families and exponential size for functional pigeonhole variants. 2026 work also gives an unconditional exponential bit-size lower bound for a strong Polynomial Calculus system augmented with extension variables and a square-root rule on the Binary Value Principle over Q. Therefore "lift to monomials and perform rank" and "add arbitrary extension names" are not universal polynomial solutions by themselves. --- ## 7. What survives from RRLS The successful RRLS canonicalizers still fit the same pattern: XOR -> linear rank over GF(2) 2-SAT -> SCC invariant Horn -> closure invariant ALLDIFFERENT-> matching invariant The important distinction is that these canonicalizers choose a feature space of polynomial dimension **without searching all features**. The universal missing link would be an algorithm that takes arbitrary F and computes, in polynomial time, a polynomial-dimensional feature algebra A_F such that fiber nonemptiness is decided by polynomial-time operations in A_F. That would be a real P=NP algorithm. No such universal feature-algebra canonicalizer is proved here. --- ## 8. Strongest current formulation Define a canonicalizer C(F) -> (basis B_F, operators O_F, invariant I_F) such that: 1. C runs in polynomial time; 2. |B_F| is polynomial in |F|; 3. operators are exact and polynomial-time; 4. I_F decides whether the solution fiber is empty; 5. recursive composition/projection stays inside polynomial-dimensional bases. For Polynomial Calculus, B_F is the degree-d monomial basis. The failure mode is that the required d can grow. For XOR, B_F is merely the linear coordinate basis and rank is enough. The remaining challenge is to find a basis family that adapts as powerfully as RRLS wants without hiding exponential work in basis discovery or basis size. That is the wall after v0.18.