# RRLS v0.16 — Extension Synthesis Is the Wall

## Status

**P = NP is not proved.**

This release identifies a much sharper equivalence between RRLS and classical proof
complexity.

## 1. RRLS vocabulary already has a classical analogue

RRLS repeatedly does

    relation -> assign token q -> reuse q in later relations.

Extended Frege allows a fresh extension variable

    q <-> Phi

and later proof lines may use q instead of expanding Phi.

Extended Resolution is resolution with unrestricted extension variables, and standard
proof-complexity references state that Extended Resolution and Extended Frege
polynomially simulate one another.

Therefore the idea "name every discovered relation and recursively build a language"
is powerful, but **not by itself the missing link**. Proof complexity has already pushed
this abstraction very far.

## 2. The experiment: naming really can remove exponential syntactic expansion

The included `extension_dag_vs_formula` benchmark recursively duplicates a previous
formula twice but stores it once with an extension variable.

At depth 40:

- syntactically expanded formula proxy:
  6,597,069,766,651
- extension-DAG proxy:
  201

So extension naming can create an exponential representation advantage while the
definition DAG stays linear.

That is exactly what our RRLS vocabulary was designed to do.

But this still says nothing about whether the *right* definitions can be discovered
efficiently.

## 3. The actual wall: extension synthesis / proof automatization

Even tiny-looking operator classes have exponentially many possible definitions.

For n variables:

    all parity supports: 2^n
    all literal conjunction patterns: 3^n

Brute-force "rotate until something becomes cheap" can therefore hide the exponential
search inside the compiler.

For affine constraints this problem disappears because Gaussian elimination provides a
polynomial canonicalization.

For matching, graph structure supplies a polynomial recognition/solution algorithm.

For general SAT, no universal polynomial canonicalizer/extension synthesizer is known.

This gives a precise RRLS design rule:

> Never search an exponentially large coordinate family. Replace search with a
> polynomial-time canonicalization theorem for that relation family.

## 4. Proof-complexity interpretation

For an UNSAT CNF, RRLS's compilation trace can be viewed as a refutation proof.

To obtain P=NP through this route we need more than short proofs.

We need one uniform procedure for which all of the following are polynomial in n:

    proof length
    proof verification
    learned vocabulary / extension definitions
    time to discover the extensions and proof

The last line is the missing ingredient.

A polynomially bounded proof language whose proofs are not efficiently discoverable
does not give a polynomial-time SAT algorithm.

## 5. Why this is a serious barrier

Known results show that finding near-shortest Resolution refutations is NP-hard; in
particular Resolution is not efficiently automatizable unless P=NP.

For stronger Frege-style systems, automatizability is tied to major complexity and
cryptographic questions. Extended Frege itself permits the kind of recursively named
Boolean-circuit vocabulary RRLS was independently converging toward.

A 2026 lower bound also shows that a strong algebraic polynomial-calculus system with
extension variables for arbitrary-depth algebraic circuits can still require
exponential bit-size refutations for a binary-value principle over Q. So "allow arbitrary
algebraic extension definitions" is not automatically universal either.

## 6. New missing-link hypothesis: canonical extension synthesis

For every irreducible core F, seek a family-specific map

    Canon(F) -> (language L, extensions E, residual R)

such that:

1. Canon runs in polynomial time;
2. |E| + |R| is polynomial;
3. the map is exact / semantics preserving;
4. L has polynomial-time reasoning;
5. recursive application reaches a solved state in polynomially many steps.

This is much stronger than compression and much sharper than blind operator search.

RRLS already has successful examples:

    XOR CNF -> row-reduced GF(2) system
    pigeonhole CNF -> ALLDIFFERENT / matching
    2-SAT -> SCC condensation
    Horn -> least-model closure

Each is a *canonicalizer*, not an exhaustive search over all possible rotations.

The unresolved research question is whether general SAT admits a finite/polynomially
indexable portfolio of such canonicalizers with universal closure.

## 7. Hard proof gate

v0.16 should reject any claimed wall break if the candidate requires:

- exponential operator enumeration;
- exponential advice/vocabulary;
- nonuniform precomputation hidden outside the runtime;
- an unproved assumption that short proofs are easy to find;
- branching with no polynomial bound.

The strongest current target is therefore:

    polynomial canonical extension synthesis

not merely:

    recursive relation compression.