# RRLS v0.28 — Adversarial Generator Compiler ## Status **P = NP is not proved.** v0.28 deliberately changes the research objective from "make RRLS look good" to "construct formulas that break RRLS, preserve the breakage, classify why it breaks, and refuse to confuse finite success with a complexity theorem." The build contains four main systems: 1. **Generator Market** — exact candidate languages compete, but UNKNOWN is preserved. 2. **Adversary Forge** — mutates formulas to maximize current compiler failure. 3. **Complexity Ledger** — records where explicit representation/work moves. 4. **Counterexample Miner** — clusters and delta-minimizes recurring failures. It also integrates an exact anchored Boolean-polynomial generator and a proof attacker whose branch counter is treated as a proof disqualifier. --- # 1. Hard P-vs-NP proof gate The gate requires all of the following simultaneously: one fixed uniform deterministic exact algorithm for arbitrary SAT; rigorous worst-case polynomial time and intermediate-size proof; concrete proof artifact; independent verification. Finite benchmarks, empirical fits, compression ratios, state caps, millions of solved instances, or a low branch count do not satisfy any missing condition. Current gate: P = NP PROVED: FALSE --- # 2. Exactness gates Fresh v0.28 checks completed: - Generator market with independent Boolean oracle: **36/36** after anchored-polynomial integration. - Anchored polynomial compiler vs independent truth enumeration: **140/140**. - Scheduled-vs-audit-all market correctness: **56/56**. - Semantic-future bitset oracle vs independently enumerated truth functions: **120/120**. - Hybrid proof attacker vs brute force: **56/56**. No critical exact-solver disagreement occurred in those checks. --- # 3. Generator Market Current exact languages include: algebraic router: 0/1-valid 2-SAT / SCC Horn GF(2) assignment / matching-cardinality bounded structural elimination anchored multilinear polynomial sparse synchronized frontier subsumption-normalized residual-future automaton small brute oracle for audit only. The production scheduler escalates through cheap exact languages before invoking expensive representations. Representative scheduled runs: | family | scale | seed | variables | clauses | status | scheduled_winner | proxy_best | total_executed_seconds | wasted_seconds | wall_seconds | executed | skipped | cross_language_cost_comparable | |:-----------|--------:|-------:|------------:|----------:|:---------|:-----------------------|:-----------------------|-------------------------:|-----------------:|---------------:|:-------------------------------------------------------------------------------------------------|:-------------------------------------------------------------------|:---------------------------------| | lowwidth | 100 | 1 | 100 | 185 | SAT | hybrid-width8 | hybrid-width8 | 0.0165515 | 0.00142938 | 0.0177872 | algebraic-router,hybrid-width8,brute-oracle | anchored-poly,sparse-frontier,semantic-residual-lite | False | | lowwidth | 500 | 1 | 500 | 967 | SAT | hybrid-width8 | hybrid-width8 | 0.272092 | 0.00889959 | 0.278248 | algebraic-router,hybrid-width8,brute-oracle | anchored-poly,sparse-frontier,semantic-residual-lite | False | | xor3 | 64 | 1 | 64 | 204 | SAT | algebraic-router | algebraic-router | 0.00201203 | 0 | 0.003281 | algebraic-router,brute-oracle | hybrid-width8,anchored-poly,sparse-frontier,semantic-residual-lite | False | | pigeonhole | 6 | 1 | 30 | 141 | UNSAT | algebraic-router | algebraic-router | 0.00131999 | 0 | 0.00202202 | algebraic-router,brute-oracle | hybrid-width8,anchored-poly,sparse-frontier,semantic-residual-lite | False | | random3 | 30 | 1 | 30 | 128 | SAT | semantic-residual-lite | semantic-residual-lite | 0.35346 | 0.0463878 | 0.355332 | algebraic-router,hybrid-width8,anchored-poly,sparse-frontier,semantic-residual-lite,brute-oracle | nan | False | | random3 | 40 | 282000 | 40 | 170 | nan | nan | nan | 1.77085 | 1.77085 | 1.77315 | algebraic-router,hybrid-width8,anchored-poly,sparse-frontier,semantic-residual-lite,brute-oracle | nan | False | An important v0.28 correction: > `feature_proxy`, frontier-state count, polynomial-term count, and residual-state count > are **not the same unit**. The first draft incorrectly used those route-local counts to crown a universal "smallest generator." That comparison has been disabled. `cross_language_cost_comparable` is now false unless a common canonical serialization is supplied. --- # 4. The adversary found a real operational wall At a fixed resource budget: structural width cap = 8 dynamic state/term cap = 2,000 random phase-transition 3-SAT produced: | n | cases | all_primary_unknown | unknown_fraction | median_seconds | |----:|--------:|----------------------:|-------------------:|-----------------:| | 24 | 6 | 0 | 0 | 0.0716062 | | 30 | 6 | 0 | 0 | 0.313166 | | 36 | 6 | 5 | 0.833333 | 0.69835 | | 40 | 6 | 6 | 1 | 0.870827 | In this finite scan: n=24: 0/6 defeated all primary generators n=30: 0/6 n=36: 5/6 n=40: 6/6 This is **not an asymptotic lower bound**. It is a reproducible regression frontier for the current compiler configuration. One fixed n=40 case (`seed=282000`) gives: algebraic router UNKNOWN hybrid width-8 UNKNOWN anchored polynomial UNKNOWN sparse frontier UNKNOWN semantic residual UNKNOWN at the 2,000-unit cap. --- # 5. Budget audit: UNKNOWN means resource exhaustion The same hard n=40 formula was rerun with larger dynamic caps: | cap | engine | status | count | peak | capped | seconds | |------:|:------------------|:---------|--------:|-------:|:---------|----------:| | 2000 | sparse-frontier | UNKNOWN | nan | 1992 | True | 0.0343742 | | 2000 | semantic-residual | UNKNOWN | nan | 1623 | True | 0.850069 | | 5000 | sparse-frontier | UNKNOWN | nan | 4538 | True | 0.039311 | | 5000 | semantic-residual | UNKNOWN | nan | 4227 | True | 1.54549 | | 10000 | sparse-frontier | UNKNOWN | nan | 7649 | True | 0.0447051 | | 10000 | semantic-residual | UNKNOWN | nan | 5647 | True | 2.18517 | | 25000 | sparse-frontier | UNKNOWN | nan | 20210 | True | 0.0916903 | | 25000 | semantic-residual | UNSAT | 0 | 16852 | False | 6.93287 | | 50000 | sparse-frontier | UNKNOWN | nan | 48424 | True | 0.156178 | | 50000 | semantic-residual | UNSAT | 0 | 16852 | False | 6.88245 | The residual language eventually proves: UNSAT with peak residual population: 16,852 once the cap reaches 25,000. The sparse-frontier language still reaches its configured cap at 50,000. Therefore the original UNKNOWN was not a wrong SAT/UNSAT answer. It was a representation budget failure. --- # 6. Counterexample Miner Starting with the 170-clause hard formula, chunk delta-debugging preserved the complete tight-budget market failure while shrinking it to: 30 clauses after: 36 market evaluations. All primary languages, including anchored polynomial, remain UNKNOWN at width-8 / 2,000-unit limits. But this minimized case is **not a general hardness certificate**. Increasing the structural width cap to 9 solves it SAT almost immediately in the separate resolution audit. So the artifact is correctly labeled: counterexample to current configured compiler, NOT counterexample to polynomial-time SAT. --- # 7. Evolutionary adversary A small n=30 evolutionary run evaluated 33 unique formulas. Its best measured fixed-budget hardness vector was: (0, 2, 1, 21, 12, 11, 7943) The search increased residual-state pressure relative to the initial population, but the semantic residual language still solved the best n=30 candidate. The point is not the exact score. The infrastructure now automatically retains formulas that worsen the compiler instead of selecting only success cases. --- # 8. Complexity cascade: the strongest discovery The adversarial formulas looked large in the current representations. Exact audit: | case | n | full_assignment_space | peak_live_frontier_states | syntactic_future_classes | exact_semantic_future_classes | poly_recognized_syntaxes | poly_unknown_syntaxes | live_to_syntax_ratio | syntax_to_semantic_ratio | live_to_semantic_ratio | |:------------------|----:|------------------------:|----------------------------:|---------------------------:|--------------------------------:|---------------------------:|------------------------:|-----------------------:|---------------------------:|-------------------------:| | hard40_seed282000 | 40 | 1099511627776 | 84394 | 38191 | 1 | 38191 | 0 | 2.20979 | 38191 | 84394 | | hard36_seed286600 | 36 | 68719476736 | 9799 | 3258 | 5 | 1423 | 1835 | 3.00767 | 651.6 | 1959.8 | ## Hard n=40 case full assignment universe = 2^40 peak live frontier states = 84,394 residual CNF syntaxes = 38,191 exact semantic futures = 1 Every one of the 38,191 residual CNFs computes the exact same Boolean function: FALSE. So the entire peak residual population is semantically one UNSAT future. ## Hard n=36 case 9,799 live states 3,258 syntactic futures 5 exact semantic futures. The exact semantic audit is exponential and therefore is **not an algorithmic breakthrough**. Its role is diagnostic: it proves that the current engine can wildly overestimate future complexity by counting descriptions rather than functions. --- # 9. Polynomial routing of the adversarial futures | case | n | syntactic_residuals | recognized | recognized_fraction | SAT | UNSAT | UNKNOWN | breakdown | seconds | |:------------------|----:|----------------------:|-------------:|----------------------:|------:|--------:|----------:|:----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------:| | hard40_seed282000 | 40 | 38191 | 38191 | 1 | 0 | 38191 | 0 | {('UNSAT', 'structural', 'low-width exact bucket elimination'): 29867, ('UNSAT', 'algebraic', '2-SAT/SCC'): 1, ('UNSAT', 'algebraic', 'GF(2)/rank'): 8323} | 17.654 | | hard36_seed286600 | 36 | 3258 | 1423 | 0.436771 | 7 | 1416 | 1835 | {('UNSAT', 'algebraic', 'GF(2)/rank'): 490, ('UNSAT', 'structural', 'low-width exact bucket elimination'): 925, ('UNKNOWN', 'unknown', 'uncompiled wide residual'): 1835, ('UNSAT', 'algebraic', '2-SAT/SCC'): 1, ('SAT', 'structural', 'low-width exact bucket elimination'): 7} | 7.7416 | For the hard n=40 snapshot, every one of the 38,191 residual syntaxes is individually certified UNSAT by existing polynomial routes: 29,867 bounded-width exact eliminations 8,323 GF(2) contradictions 1 2-SAT contradiction. Yet the upstream engine generated tens of thousands of residual descriptions before discovering that fact. For the hard n=36 snapshot, 1,835 syntactic residuals remain UNKNOWN to the current width-8/algebra router. But the exact semantic oracle says there are only five semantic classes total. --- # 10. The "easy representative" result | case | semantic_class | models_in_future | syntactic_members | easy_representative_exists | easy_status | easy_route | easy_language | unknown_syntaxes | |:------------------|-----------------:|-------------------:|--------------------:|:-----------------------------|:--------------|:-------------|:-----------------------------------|-------------------:| | hard36_seed286600 | 0 | 0 | 3251 | True | UNSAT | algebraic | GF(2)/rank | 1835 | | hard36_seed286600 | 1 | 1 | 2 | True | SAT | structural | low-width exact bucket elimination | 0 | | hard36_seed286600 | 2 | 2 | 2 | True | SAT | structural | low-width exact bucket elimination | 0 | | hard36_seed286600 | 3 | 3 | 1 | True | SAT | structural | low-width exact bucket elimination | 0 | | hard36_seed286600 | 4 | 3 | 2 | True | SAT | structural | low-width exact bucket elimination | 0 | | hard40_seed282000 | 0 | 0 | 38191 | True | UNSAT | structural | low-width exact bucket elimination | 0 | Every one of the five exact semantic classes in the n=36 snapshot contains at least one representative that the polynomial portfolio can solve. Most strikingly: 3,251 syntactic residuals belong to the same UNSAT semantic function; 1,835 of those syntaxes are UNKNOWN to the current router; another syntax for that exact same function is recognized as GF(2)-UNSAT. This strongly localizes the missing operation on these finite controls: > discover a tractable canonical representative of a semantic equivalence class without > first solving full Boolean equivalence by exponential truth-table enumeration. A universal polynomial implementation of that idea would itself be a major complexity result. v0.28 does not have one. --- # 11. Anchored polynomial generator The fixation-point idea is represented exactly by y = x XOR a and the SAT indicator is compiled as a multilinear polynomial over GF(257). A zero final polynomial means UNSAT; a nonzero polynomial means SAT. Fresh independent differential: 140/140 exact. The hard n=40 formula hits the 2,000-term budget after only a handful of clauses, so anchoring does not remove the worst-case term explosion. This generator therefore adds another exact coordinate system, not a universal escape. --- # 12. Proof attacker The proof attacker separates: "solver found the answer" from "candidate polynomial proof path found the answer." Polynomial-only family results: | family | scale | variables | clauses | poly_only_status | poly_collapses | wide_unknown_cores | max_minfill_width_seen | branch_nodes | seconds | |:-----------|--------:|------------:|----------:|:-------------------|-----------------:|---------------------:|-------------------------:|---------------:|-----------:| | xor3 | 64 | 64 | 204 | SAT | 1 | 0 | 0 | 0 | 0.00780311 | | pigeonhole | 6 | 30 | 141 | UNSAT | 1 | 0 | 0 | 0 | 0.00317664 | | lowwidth | 200 | 200 | 381 | SAT | 3 | 0 | 4 | 0 | 0.0343111 | | random3 | 24 | 24 | 102 | UNKNOWN | 0 | 1 | 17 | 0 | 0.00466584 | | random3 | 30 | 30 | 128 | UNKNOWN | 0 | 1 | 20 | 0 | 0.00759551 | | random3 | 36 | 36 | 153 | UNKNOWN | 0 | 1 | 24 | 0 | 0.010119 | | random3 | 40 | 40 | 170 | UNKNOWN | 0 | 1 | 27 | 0 | 0.0132315 | | 3color | 8 | 24 | 65 | SAT | 1 | 0 | 6 | 0 | 0.00570789 | | 3color | 10 | 30 | 97 | UNKNOWN | 0 | 1 | 11 | 0 | 0.00309841 | | tseitin | 20 | 30 | 80 | SAT | 1 | 0 | 0 | 0 | 0.00232681 | Known structured families collapse without branching. Generic phase-transition random 3-SAT remains UNKNOWN under the polynomial-only path. When branching is enabled, the same engine solves many finite controls, but every branch is recorded as evidence that the current P-time proof path failed. Finite branching diagnostics: | n | cases | median_nodes | median_branch_nodes | max_branch_nodes | median_seconds | aborted | |----:|--------:|---------------:|----------------------:|-------------------:|-----------------:|----------:| | 20 | 3 | 10 | 5 | 6 | 0.0208432 | 0 | | 24 | 3 | 10 | 6 | 9 | 0.024687 | 0 | | 28 | 3 | 12 | 7 | 9 | 0.0451689 | 0 | | 32 | 3 | 6 | 4 | 13 | 0.0290113 | 0 | | 36 | 3 | 33 | 16 | 17 | 0.135167 | 0 | | 40 | 3 | 18 | 9 | 14 | 0.0944002 | 0 | These samples are small and do not establish exponential asymptotics. They simply keep the proof boundary explicit. --- # 13. Complexity Ledger The ledger records: explicit input CNF size; route-local representation units; caps; frontier width; synchronization counts; runtime; selected scheduled route. It does **not** assert: information conservation; thermodynamic equivalence; Kolmogorov-optimality; cross-language MDL comparability. That correction is important. A GF(2) equation, BDD node, frontier state, residual CNF, and polynomial monomial have different serialization costs. A future version must serialize all candidate generators into one exact common format before "smallest language" becomes a defensible cross-language statement. --- # 14. Counterexample clustering The obstruction miner groups failures using exact operational features: algebraic route status bounded-width status / width sparse-frontier cap residual cap anchored-polynomial cap mode-count buckets. In the 24-formula scan it found multiple recurring obstruction classes rather than one single failure shape. That is useful even if P != NP: the engine is becoming a map of **which representation fails where**. --- # 15. What survived the hostile audit The following claims survive v0.28: 1. Different exact generator languages dominate different structured families. 2. Eventual SAT/UNSAT answers remained consistent across tested exact candidates. 3. UNKNOWN correctly tracks incomplete/capped computation. 4. Clause/order/basis choice can move enormous amounts of representation cost. 5. Syntactic future count can exceed true semantic future count by orders of magnitude. 6. On selected hard snapshots, semantic classes can contain both hard-looking and easy-looking syntactic descriptions. 7. The current missing operation is increasingly well described as **semantic canonicalization / generator discovery**, not merely another SAT branching heuristic. What does **not** survive as a claim: 1. benchmark success implies P=NP; 2. raw feature counts from different languages are directly comparable; 3. a minimized current-compiler counterexample is a complexity lower bound; 4. a tiny semantic future set implies we can find it in polynomial time; 5. finite branch counts establish polynomial scaling. --- # 16. Current theorem target A real P=NP result along this route would require a fixed uniform transformation Q(F) such that for every CNF F: 1. Q is computable in polynomial time; 2. every intermediate object has polynomial description length; 3. Q maps semantically equivalent future states to a polynomial-size canonical generator language; 4. SAT/nonemptiness of that generator is decidable in polynomial time; 5. no exponential truth-table oracle, branching, advice, anchor search, or hidden preprocessing is used. If those conditions are proved for arbitrary CNF, then SAT is in P. v0.28 does not prove them. --- # 17. Next attack The strongest next target is **Canonical Semantic Generator Synthesis**. Do not ask: "Can I solve this residual?" Ask: "Can I convert all descriptions of the same residual function into the same compact normal form, using only polynomial work?" Immediate test languages: GF(2) RREF canonical form; 2-SAT implication closure; bounded-width interface functions; renamable Horn closure; matching/cardinality certificates. Then attack the uncompiled residuals with the adversary and ask whether all semantic classes admit one of those canonical forms before the frontier population blows up. The proof gate stays closed until that process has a uniform worst-case polynomial theorem.