# RRLS v0.19 — Adaptive Feature Algebra ## Status **P = NP is not proved.** v0.19 breaks an important *internal* RRLS wall: the standard low-degree monomial basis is not the right universal measure of algebraic complexity. The correct target is a **polynomially synthesized, problem-adapted feature basis**. --- ## 1. Raw pigeonhole: 137,980 monomials -> 9 synthesized features In v0.18, PHP 5->4 in the standard Boolean Macaulay hierarchy reached: - degree 7 - 137,980 monomial coordinates - 1,500,000 generated rows - resource cap before refutation. v0.19 receives the same unlabeled CNF. It recognizes, from clause incidence alone: - disjoint positive choice groups; - complete within-group incompatibility; - cross-group incompatibility classes; - the induced bipartite assignment geometry. It then synthesizes: one aggregate "chosen count" feature per choice group one aggregate capacity feature per destination group. For PHP 5->4 this is: 5 + 4 = 9 features. Exact certificate: total chosen >= 5 total capacity <= 4 contradiction. Measured comparison: | method | instance | feature_coordinates | generated_relations | status | seconds | |:----------------------------------------------|:-----------|----------------------:|----------------------:|:-------------------------|-------------:| | degree<=7 Boolean monomial Macaulay | PHP 5->4 | 137980 | 1500000 | CAPPED before refutation | 20.8388 | | RRLS synthesized assignment/cardinality basis | PHP 5->4 | 9 | 9 | UNSAT exact | 0.000201238 | No "pigeon" or "hole" labels are supplied to the recognizer. --- ## 2. Scaling of the synthesized basis | family | pigeons | holes | variables | clauses | adaptive_features | matching_size | counting_contradiction | seconds | status | |:-----------|----------:|--------:|------------:|----------:|--------------------:|----------------:|:-------------------------|------------:|:---------| | pigeonhole | 3 | 2 | 6 | 12 | 5 | 2 | True | 0.000101856 | UNSAT | | pigeonhole | 4 | 3 | 12 | 34 | 7 | 3 | True | 0.000120456 | UNSAT | | pigeonhole | 5 | 4 | 20 | 75 | 9 | 4 | True | 0.000201238 | UNSAT | | pigeonhole | 6 | 5 | 30 | 141 | 11 | 5 | True | 0.000423732 | UNSAT | | pigeonhole | 8 | 7 | 56 | 372 | 15 | 7 | True | 0.00087889 | UNSAT | | pigeonhole | 10 | 9 | 90 | 775 | 19 | 9 | True | 0.00202882 | UNSAT | | pigeonhole | 20 | 19 | 380 | 7050 | 39 | 19 | True | 0.0299433 | UNSAT | | pigeonhole | 30 | 29 | 870 | 24825 | 59 | 29 | True | 0.0983383 | UNSAT | | pigeonhole | 40 | 39 | 1560 | 60100 | 79 | 39 | True | 0.263635 | UNSAT | At PHP 40->39: - 1,560 Boolean variables - 60,100 clauses - 79 synthesized aggregate features - exact UNSAT - ~0.26 s in the measured Python implementation. The feature count is linear in the recovered assignment geometry rather than combinatorial in the raw monomial degree. This is the strongest empirical demonstration yet of the RRLS principle: choose the algebra first; then solve. --- ## 3. Why this does not contradict Polynomial Calculus degree lower bounds The v0.18 Macaulay system uses squarefree monomials as its basis. v0.19 changes the **basis language itself** to structured aggregate/cardinality functions. This distinction is real in optimization/proof theory: high-degree custom polynomial subspaces can yield polynomial-time hierarchies that capture inequalities missed by standard bounded-degree Sum-of-Squares bases. So "required monomial degree grows" does not imply "every polynomial-size feature language fails." It only rules out that fixed low-degree monomial language. --- ## 4. Multi-language compilation actually works A single disconnected formula was constructed with four connected regions deliberately chosen so neither all-zero nor all-one trivializes the intended algebra. Measured: | component | language | status | variables | clauses | feature_proxy | |------------:|:--------------------------------|:---------|------------:|----------:|----------------:| | 0 | Horn/closure | SAT | 300 | 650 | 300 | | 1 | 2-SAT/SCC | SAT | 300 | 650 | 600 | | 2 | assignment/matching-cardinality | SAT | 360 | 6498 | 38 | | 3 | GF(2)/rank | SAT | 250 | 992 | 250 | Whole formula: | variables_total | clauses_total | connected_regions | status | seconds | branching | languages | feature_proxy_total | |------------------:|----------------:|--------------------:|:---------|----------:|------------:|:---------------------------------------------------------------------|----------------------:| | 1210 | 8790 | 4 | SAT | 0.134501 | 0 | Horn/closure; 2-SAT/SCC; assignment/matching-cardinality; GF(2)/rank | 1188 | The solver used four different exact coordinate systems in one run and combined their solutions without branching. This is a concrete implementation of: local region -> canonical algebra -> compact exact invariant -> collapse -> combine with other compiled regions. --- ## 5. Hard falsification: generic 3-SAT remains uncompiled The same canonical basis recognizers were run against phase-transition random 3-SAT. They did not force general formulas into a convenient language. | n | cases | SAT | UNSAT | UNKNOWN | compiled_fraction | languages | |----:|--------:|------:|--------:|----------:|--------------------:|:----------------------------| | 30 | 20 | 0 | 0 | 20 | 0 | {"uncompiled residual": 20} | | 40 | 20 | 0 | 0 | 20 | 0 | {"uncompiled residual": 20} | | 50 | 20 | 0 | 0 | 20 | 0 | {"uncompiled residual": 20} | | 60 | 20 | 0 | 0 | 20 | 0 | {"uncompiled residual": 20} | This is the correct result. A canonicalizer is admitted only when it proves that the exact formula belongs to its tractable algebra. Otherwise the residual stays UNKNOWN. --- ## 6. The new theorem target: Adaptive Feature Basis Synthesis For each formula F, seek a deterministic map Basis(F) = (phi_1, ..., phi_m) with m polynomial in |F|, such that: 1. Basis(F) is computable in polynomial time; 2. each phi_i has a polynomial-size/evaluable description; 3. the exact constraints can be transformed into the feature algebra in polynomial time; 4. fiber nonemptiness is decidable in polynomial time in this algebra; 5. conjunction, projection, and recursive compilation never require a superpolynomial number of features. For XOR, Basis(F) is essentially a row-reduced linear basis. For matching, it is graph/assignment incidence. For Horn, closure coordinates suffice. For 2-SAT, SCC reachability is the canonical representation. For pigeonhole, v0.19 synthesizes row/column cardinality coordinates. For arbitrary 3-SAT, no universal Basis algorithm is known or proved here. If such a Basis algorithm existed with the five properties above for every CNF, then SAT would be in P and therefore P=NP. --- ## 7. Why this is a better target than "low degree" Let standard monomial features be x_S = product_(i in S) x_i. Degree-d lifting offers sum_(j=0)^d C(n,j) features. But the useful coordinate can be high degree while belonging to a tiny structured family. Examples include: - parity features; - cardinality/threshold features; - matching exchange structure; - custom high-degree SoS basis functions. The quantity RRLS should optimize is therefore not degree alone but: feature count + feature synthesis cost + closure cost + exact decision cost. Call this **Adaptive Feature Width**. --- ## 8. The remaining wall We have now repeatedly seen the same pattern: known structure -> polynomial canonicalizer -> collapse generic 3-SAT -> no known canonicalizer -> residual Known proof-system lower bounds also show that no single one of the standard fixed languages (Resolution, low-degree Polynomial Calculus, many Cutting-Planes variants, OBDD/DNNF compilation, etc.) can serve as the universal answer. The unresolved possibility is an **instance-adaptive portfolio of canonically generated feature algebras**. That is narrower than "search every transformation" and broader than any one proof system. The proof gate remains closed until the portfolio itself is shown complete and polynomial for every input.