# RRLS v0.25 — Synchronized Collision Algebra ## Status **P = NP is not proved.** v0.25 translates the "hairs collide, synchronize, and become collective modes" idea into a sequence of exact Boolean counting algebras. The central result is not a proof of polynomial-time SAT, but a measured hierarchy of increasingly aggressive exact synchronization rules. Across the five implementations, the benchmark suite completed 1064/1064 method/formula differential checks exactly against brute force on small instances. --- ## 1. Clause falsifiers as collision coordinates Every CNF clause has one unique partial assignment that falsifies it. For clause c, call this partial coordinate A_c and define I_A(x)=1 iff full assignment x extends A. Then exactly 1_SAT(F)(x) = product_c (1 - I_(A_c)(x)). The collision product is I_A I_B = 0 if A and B conflict I_(A union B) otherwise. So subsets of clauses that attempt incompatible joint falsification annihilate. Different clause subsets that reach the same merged partial assignment synchronize by adding their integer coefficients. Exact model count: #SAT(F) = sum_A alpha_A 2^(n-|A|). This replaces naive 2^m clause-subset expansion by at most 3^n partial-coordinate states, but 3^n is still exponential. --- ## 2. Synchronization level 1 — identical collision coordinate Implementation: `collision_expand` Two derivations merge only when they reach the same partial assignment. Random 3-SAT around ratio 4.26 showed enormous synchronization and cancellation, but the live collision language still reached roughly one million states around n=18-20. Clause ordering changed runtime but, on the tested n=14/16 formulas, did not change the peak because the final collision-support itself was the largest state set. Conclusion: collision identity is real compression, but insufficient. --- ## 3. Synchronization level 2 — forget coordinates after their final interaction If variable v appears in no future clause, summation over it commutes with every future factor. For one collision term: sum_(x_v) I_A = 2 I_(A\v) if v is unassigned in A 1 I_(A\v) if v is assigned in A. Therefore dead coordinates can be pulled back onto the string immediately. Implementation: `collision_projected_count` This changes the controlling parameter from total n to the maximum live frontier w. The partial-assignment representation has at most 3^w states. This is exact. --- ## 4. Synchronization level 3 — keep only nonzero collective trajectories The partial-cube basis still stores derivation structure. The exact response on a Boolean frontier of width w has only 2^w complete assignments. Two dense/sparse implementations were built: `frontier_table_count` `sparse_frontier_count` The sparse version stores only nonzero frontier amplitudes. Phase-transition random 3-SAT results: | n | completed | median_width | median_peak_live | max_peak_live | median_seconds | |----:|------------:|---------------:|-------------------:|----------------:|-----------------:| | 20 | 3 | 16 | 419 | 532 | 0.0074763 | | 30 | 3 | 24 | 6739 | 13242 | 0.0542316 | | 40 | 3 | 32 | 61691 | 87104 | 0.381942 | | 50 | 2 | 36 | 646442 | 845254 | 6.29276 | | 60 | 0 | 27 | 786751 | 865427 | 2.36361 | The completed medians n=20..50 were empirically fit by peak ≈ 4.28 × 1.2685^n with R²=0.97744 on raw peak counts. The finite exponential fit is better than the tested polynomial fit on this tiny range. It is **not an asymptotic lower bound**, but it means this quotient has not produced evidence of polynomial worst-case scaling. --- ## 5. Structural control: synchronization can be essentially constant-width For bounded-window 3-SAT in its natural geometric clause order, the sparse projected frontier stayed at five live Boolean coordinates. At n=5000: clauses = 9780 peak frontier bits = 5 peak live states = 28 wall time ≈ 0.2081 s and the result was exact SAT. This is exactly the expected bounded-pathwidth behavior. A generic frontier heuristic could destroy this locality, which demonstrates that the timing/order must respect the actual interaction geometry. --- ## 6. Synchronization level 4 — different coordinates, identical future dance The strongest new rule is: if residual_future(a) == residual_future(b), merge a and b. After substituting the current frontier assignment into every unprocessed clause, two histories with the exact same canonical residual CNF have identical future behavior. At peak snapshots: | n | frontier_bits | live_states | future_equivalence_classes | compression_ratio | largest_equivalence_class | |----:|----------------:|--------------:|-----------------------------:|--------------------:|----------------------------:| | 20 | 16 | 1044 | 20 | 52.2 | 970 | | 30 | 17 | 1438 | 546 | 2.6337 | 887 | | 40 | 25 | 26404 | 10302 | 2.563 | 15746 | The n=20 sample compressed 1,044 current frontier assignments to only 20 distinct future formulas — 52.2×. At n=30/40 the measured quotient was smaller (~2.6×), but still exact. This led to the breadth-first residual automaton: `residual_sync_count` where state = canonical remaining CNF and multiplicity = number of histories reaching that future. Phase-transition results: | n | completed | median_peak | max_peak | median_seconds | |----:|------------:|--------------:|-----------:|-----------------:| | 20 | 3 | 130 | 403 | 0.01553 | | 30 | 3 | 2039 | 3381 | 0.25062 | | 40 | 3 | 9044 | 12119 | 2.56006 | This is closely related to OBDD/residual-memoization methods. Its width can still be exponential in general. --- ## 7. Apples-to-apples synchronization ladder Same formulas, same state cap: | n | method | status | count | peak_modes | seconds | |----:|:---------------------|:---------|--------:|-------------:|-----------:| | 20 | collision-coordinate | UNKNOWN | nan | 192644 | 0.604082 | | 20 | projected-collision | UNSAT | 0 | 107028 | 1.23147 | | 20 | sparse-frontier | UNSAT | 0 | 264 | 0.00788243 | | 20 | future-residual | UNSAT | 0 | 147 | 0.0108941 | | 30 | collision-coordinate | UNKNOWN | nan | 182550 | 0.461331 | | 30 | projected-collision | UNKNOWN | nan | 187564 | 0.566572 | | 30 | sparse-frontier | SAT | 64 | 4767 | 0.0436206 | | 30 | future-residual | SAT | 64 | 1536 | 0.203485 | | 40 | collision-coordinate | UNKNOWN | nan | 179493 | 0.366575 | | 40 | projected-collision | UNKNOWN | nan | 162130 | 0.357608 | | 40 | sparse-frontier | UNSAT | 0 | 130336 | 0.723796 | | 40 | future-residual | UNSAT | 0 | 26616 | 5.92395 | Headline n=40 instance: collision-coordinate : cap / UNKNOWN near 180k modes projected-collision : cap / UNKNOWN near 162k modes sparse-frontier : exact UNSAT, 130,336 peak modes future-residual : exact UNSAT, 26,616 peak modes At n=30: sparse-frontier : exact #SAT = 64 with 4,767 peak modes future-residual : exact #SAT = 64 with 1,536 peak modes Every completed exact representation agrees. --- ## 8. Known-algebra controls still beat generic synchronization The generic collision language is not the right final basis for every structured family. Examples from v0.25/v0.19/v0.13: - XOR is better canonicalized directly into GF(2) rank. - pigeonhole is better canonicalized into ALLDIFFERENT / matching/cardinality. - bounded-width formulas are better handled by structural frontier elimination. The projected collision engine itself completed XOR-CNF through n=48 in one tested sequence and pigeonhole through PHP 5->4, but then hit its state cap. Their dedicated algebraic canonicalizers scale far better. Therefore the correct RRLS architecture remains a portfolio: collision synchronization + structural projection + future-equivalence quotient + family-specific canonical algebra. --- ## 9. Complexity interpretation Let w be the maximum number of live Boolean coordinates for a fixed clause schedule. The exact representations have rough worst-case state ceilings: collision partial assignments : O(3^w) dense/sparse frontier response : O(2^w) future residual synchronization : O(W_R) where W_R is the maximum number of distinct canonical residual futures for the chosen variable order. None is proved polynomial for arbitrary CNF. For general SAT, w can grow linearly and residual width can be exponential. Thus v0.25 does not close the P vs NP proof gate. --- ## 10. What the hair model contributed The physical metaphor generated four mathematically distinct synchronization operations: 1. **collision**: incompatible partial coordinates annihilate; identical merged coordinates combine. 2. **return to string**: coordinates with no future interaction are summed out immediately. 3. **collective occupancy**: empty trajectories are not represented. 4. **synchronized future motion**: different histories merge when their exact future response is identical. That fourth rule is the strongest one. It changes the research question from "How many assignments are alive?" to "How many genuinely different futures are alive?" This is a much better complexity observable. --- ## 11. Remaining theorem target A true wall break would require a polynomial-time canonicalizer Q such that, for every CNF F, F -> Q(F) produces only polynomially many exact future modes, or compresses those future modes into a tractable algebra of polynomial size. Required: 1. Q is uniform and polynomial-time. 2. Every synchronization is semantics preserving. 3. Intermediate representations remain polynomial-size. 4. Exact SAT/nonemptiness is polynomial in the representation. 5. No exponential advice, preprocessing, assignment enumeration, or hidden search. If such a Q exists for all CNFs, SAT is in P and therefore P=NP. No such universal theorem is proved in v0.25. --- ## 12. Next attack The next useful object is the **residual-future language itself**. Instead of merely hashing canonical residual CNFs, mine the residual-mode population for a second-level algebra: - affine relations among residual modes; - symmetry/orbit quotients; - separator-equivalent interfaces; - low-rank transition operators; - synchronized strongly connected mode clusters; - spectral / transfer-function representations of the residual transition graph. The target is a compact algebra over *futures*, not over raw variables.