# RRLS v0.20 — Structural × Algebraic Tractability Map ## Status **P = NP is not proved.** v0.20 narrows the unexplained region into a two-axis map: constraint algebra × interaction structure. A SAT/CSP instance can be easy because its relations belong to a tractable algebra, or because the constraint interaction graph admits a low-width decomposition. These mechanisms are genuinely orthogonal. --- ## 1. Exact structural solver v0.20 adds exact Boolean bucket elimination. It: 1. constructs a primal interaction graph; 2. computes a deterministic min-fill elimination order; 3. materializes exact boundary factors; 4. existentially eliminates one variable at a time; 5. returns UNKNOWN rather than truncating if factor scope exceeds the configured cap. Differential verification: 84/84 small bounded-width CNFs agreed with brute force. Scaling: | family | n | clauses | status | minfill_width | max_factor_scope | seconds | |:--------------------|----:|----------:|:---------|----------------:|-------------------:|-----------:| | bounded-window-3SAT | 50 | 137 | SAT | 4 | 5 | 0.00805637 | | bounded-window-3SAT | 100 | 275 | SAT | 4 | 5 | 0.0142237 | | bounded-window-3SAT | 200 | 567 | SAT | 4 | 5 | 0.04999 | | bounded-window-3SAT | 400 | 1149 | SAT | 4 | 5 | 0.19418 | | bounded-window-3SAT | 800 | 2305 | UNSAT | 4 | 5 | 0.804155 | At 800 variables / 2,305 clauses the induced width remained 4, maximum factor scope 5, and the pure-Python exact run took about 0.8 seconds. --- ## 2. Structure × algebra experiment | family | variables | cases | median_width | min_width | max_width | algebraic_routes | structural_routes | unknown | median_seconds | |:---------------------|------------:|--------:|---------------:|------------:|------------:|-------------------:|--------------------:|----------:|-----------------:| | bounded-window 3-SAT | 400 | 1 | 4 | 4 | 4 | 0 | 1 | 0 | 0.19969 | | pigeonhole | 56 | 1 | 35 | 35 | 35 | 1 | 0 | 0 | 0.00155846 | | pigeonhole | 132 | 1 | 87 | 87 | 87 | 1 | 0 | 0 | 0.0149037 | | pigeonhole | 240 | 1 | 151 | 151 | 151 | 1 | 0 | 0 | 0.0269886 | | random 3-SAT | 30 | 3 | 21 | 20 | 21 | 0 | 0 | 3 | 0.00385141 | | random 3-SAT | 40 | 3 | 28 | 27 | 29 | 0 | 0 | 3 | 0.0113739 | | random 3-SAT | 50 | 3 | 34 | 34 | 35 | 0 | 0 | 3 | 0.0184725 | | random 3-SAT | 60 | 3 | 40 | 40 | 41 | 0 | 0 | 3 | 0.0328337 | | random 3-SAT | 80 | 3 | 55 | 54 | 55 | 0 | 0 | 3 | 0.089477 | | random 3-XOR | 40 | 1 | 9 | 9 | 9 | 1 | 0 | 0 | 0.000503753 | | random 3-XOR | 60 | 1 | 12 | 12 | 12 | 1 | 0 | 0 | 0.000639507 | | random 3-XOR | 80 | 1 | 16 | 16 | 16 | 1 | 0 | 0 | 0.0010127 | Observed quadrants: ### Narrow structure, no special algebra Bounded-window 3-SAT: - width 4 - exact structural route ### Wide structure, tractable algebra Pigeonhole: - width 35 -> 151 in the measured sequence - exact matching/cardinality route 3-XOR: - increasing width - exact GF(2) rank route ### Wide structure, no recognized tractable algebra Random phase-transition 3-SAT: - median min-fill width ~20 at n=30 - ~28 at n=40 - ~35 at n=50 - ~41 at n=60 - ~55 at n=80 - every tested instance stayed UNKNOWN. This is the current RRLS residual quadrant. --- ## 3. Symmetry quotienting Signed incidence color refinement was added as a cheap canonical quotient diagnostic. | family | variables | cases | median_width | median_variable_quotient_ratio | median_largest_variable_class | median_clause_quotient_ratio | median_spectral_gap | median_sigma2 | |:---------------------|------------:|--------:|---------------:|---------------------------------:|--------------------------------:|-------------------------------:|----------------------:|----------------:| | 3-XOR | 37 | 1 | 10 | 0.972973 | 2 | 0.993056 | 0.0892775 | 0.910723 | | 3-XOR | 56 | 1 | 15 | 1 | 1 | 1 | 0.0555869 | 0.944413 | | 3-XOR | 79 | 1 | 18 | 0.974684 | 2 | 0.993056 | 0.0478452 | 0.952155 | | bounded-window 3-SAT | 199 | 1 | 4 | 1 | 1 | 1 | 0.000189252 | 0.999811 | | pigeonhole | 56 | 1 | 35 | 0.0178571 | 56 | 0.00537634 | 0.154846 | 0.845154 | | pigeonhole | 132 | 1 | 87 | 0.00757576 | 132 | 0.00143062 | 0.147197 | 0.852803 | | random 3-SAT | 30 | 3 | 20 | 1 | 1 | 1 | 0.239891 | 0.760109 | | random 3-SAT | 40 | 3 | 28 | 1 | 1 | 1 | 0.257332 | 0.742668 | | random 3-SAT | 50 | 3 | 35 | 1 | 1 | 1 | 0.238259 | 0.761741 | | random 3-SAT | 60 | 3 | 41 | 1 | 1 | 1 | 0.232023 | 0.767977 | | random 3-SAT | 80 | 3 | 55 | 1 | 1 | 1 | 0.234992 | 0.765008 | Pigeonhole is enormously symmetric: - PHP 12->11: 132 variables collapse to one variable color class under the diagnostic. Random 3-SAT is the opposite: - every tested variable and clause becomes individually distinguished; - variable quotient ratio = 1.0; - clause quotient ratio = 1.0. So the generic residual is not hiding the same obvious orbit/cardinality quotient that made pigeonhole collapse. But symmetry is not necessary for tractability: 3-XOR is also mostly individualized under this refinement and still collapses under GF(2). --- ## 4. Expansion is a barrier amplifier, not the missing invariant Resolution width lower bounds and Polynomial Calculus degree lower bounds are known to arise from expansion properties of clause-variable incidence structures. Our random 3-SAT samples show a stable nontrivial normalized-incidence spectral gap around 0.23 together with growing min-fill width and no WL quotient. This combination is consistent with the known proof-complexity picture: expanding cores resist local/narrow proof languages. But expansion alone is not computational hardness. A Tseitin-style inconsistent parity system on random connected 3-regular graphs gives: | family | graph_vertices | variables_edges | clauses | minfill_width | variable_quotient_ratio | largest_variable_class | spectral_gap | sigma2 | route | language | status | solve_seconds | |:----------------------|-----------------:|------------------:|----------:|----------------:|--------------------------:|-------------------------:|---------------:|---------:|:----------|:-----------|:---------|----------------:| | Tseitin 3-regular XOR | 20 | 30 | 80 | 8 | 1 | 1 | 0.0454979 | 0.954502 | algebraic | GF(2)/rank | UNSAT | 0.000216559 | | Tseitin 3-regular XOR | 30 | 45 | 120 | 8 | 1 | 1 | 0.0270867 | 0.972913 | algebraic | GF(2)/rank | UNSAT | 0.000369543 | | Tseitin 3-regular XOR | 40 | 60 | 160 | 10 | 1 | 1 | 0.0192421 | 0.980758 | algebraic | GF(2)/rank | UNSAT | 0.000398602 | | Tseitin 3-regular XOR | 60 | 90 | 240 | 15 | 1 | 1 | 0.0178739 | 0.982126 | algebraic | GF(2)/rank | UNSAT | 0.000735656 | Underlying graph spectral diagnostics: | vertices | edges | normalized_nontrivial_spectral_radius | graph_spectral_gap | |-----------:|--------:|----------------------------------------:|---------------------:| | 20 | 30 | 0.93035 | 0.0696505 | | 30 | 45 | 0.881257 | 0.118743 | | 40 | 60 | 0.898798 | 0.101202 | | 60 | 90 | 0.942466 | 0.0575336 | | 80 | 120 | 0.931564 | 0.0684358 | | 120 | 180 | 0.919313 | 0.0806871 | The instances are global, symmetry-poor, and increasingly wide in their CNF representation, yet RRLS dispatches them through GF(2) rank in sub-millisecond time. Therefore: expansion != hardness. The more precise residual signature is: expansion / wide interaction + no cheap structural separator + no recognized global algebraic quotient. --- ## 5. Connection to CSP theory Finite-domain CSP theory already formalizes the algebraic axis. The Bulatov-Zhuk dichotomy says a fixed finite constraint template is either polynomial-time solvable or NP-complete, with the tractable side characterized by nontrivial polymorphisms / Siggers-type identities. The 3-SAT language has only projection polymorphisms, so a new *fixed local Boolean polymorphism* cannot be the RRLS breakthrough. Structural CSP theory formalizes the other axis. Bounded treewidth/fractional hypertree width yields tractability, and submodular width gives a broad structural boundary for parameterized tractability under ETH. So both of RRLS's obvious static escape directions are already deeply classified. --- ## 6. Candidate missing object: Canonical Hybrid Quotient The remaining possibility is instance-adaptive. Seek a polynomial-time transformation Q(F) -> (regions R_i, interfaces S_i, local algebras A_i) such that every transformed region satisfies at least one: 1. A_i has a polynomial-time tractable algebra / polymorphism; 2. R_i has polynomially bounded structural width; and all interface relations stay polynomial-size and exact. Required proof obligations: - Q is uniform and polynomial-time; - output and vocabulary size are polynomial; - every local recognizer/solver is polynomial; - interfaces compose and project in polynomial time; - the number of recursive quotient/decomposition steps is polynomial. If such Q exists for every CNF, SAT is in P and therefore P=NP. No such universal quotient theorem is proved here. --- ## 7. Why this is sharper than "adaptive basis" v0.19 showed that one hard fixed monomial basis can be replaced by a tiny instance-specific cardinality basis. v0.20 adds the missing structural fact: sometimes no special basis is needed because small separators suffice. So the adaptive target should optimize both: algebraic feature width and structural separator width. A useful working quantity is HybridWidth(F) = minimum over exact polynomially discoverable decompositions of the maximum operational boundary cost after local algebraic quotienting. This is a research definition, not a known complexity characterization. --- ## 8. Strongest remaining adversary The most informative next training corpus is no longer arbitrary SAT. It is specifically formulas satisfying all of: - fixed NP-hard local language; - high structural width / expansion; - low obvious symmetry; - no Horn/Krom/affine/matching/cardinality recognition; - no cheap bounded-degree algebraic refutation; - no small currently known backdoor. Those are the irreducible expander cores. The next RRLS engine should mine them for **global instance-specific quotients**: matroid structure, cuts/flows, higher polymorphisms after domain lift, spectral modules, tensor interfaces, or other exact canonical relations. The proof gate remains closed until one such mechanism is proved complete and polynomial for all inputs.