# RRLS v0.14 — The Missing-Link Search ## Status **P = NP is not proved.** v0.14 materially narrows the RRLS hypothesis. The current evidence says the missing link is not another small local Boolean relation and not naive repeated monomial lifting. The most precise current target is **higher-order boundary compatibility**. --- ## 1. Local Boolean relation space exhausted at arity 3 RRLS exhaustively enumerated all 2^(2^3) = 256 ternary Boolean relations. For each relation it tested the standard tractable closure signatures: - 0-valid - 1-valid - coordinatewise AND closure (Horn) - coordinatewise OR closure (dual-Horn) - majority closure (bijunctive / 2-SAT algebra) - ternary XOR/minority closure (affine algebra) Measured: - all ternary relations: **256** - relations with a Schaefer tractable signature: **241** - outside those signatures: **15** The canonical positive 1-in-3 and NAE-3 relations fail every tested tractable signature. This strongly narrows the search: a universal P=NP language cannot be obtained simply by discovering one more fixed local ternary Boolean operator inside the same CSP representation. --- ## 2. Exact projection gap: all 2D shadows solve, 3D does not RRLS exhaustively searched 3×3×3 matching relations and found a minimum projection-gap instance after checking 3,865 subsets. Minimum size: **4 triples**. Triples: [ [ 0, 0, 0 ], [ 0, 1, 1 ], [ 1, 0, 1 ], [ 2, 2, 2 ] ] Every XY, XZ and YZ projection admits a perfect ordinary bipartite matching. Yet the original 3-dimensional relation has **no** perfect 3D matching. Therefore: solve(P_xy(T)) = YES solve(P_xz(T)) = YES solve(P_yz(T)) = YES does not imply solve(T) = YES. This is an exact finite demonstration of information stored only in the joint fiber of the higher-dimensional relation and erased by every pairwise projection. --- ## 3. A 2×2×2 integrality / lattice gadget The relation T = {000, 011, 101, 110} has complete pairwise projections and no integral perfect 3D matching. Its exact-cover incidence system A x = 1 has the fractional solution x = (1/2, 1/2, 1/2, 1/2). A 3×3 minor of A has determinant magnitude **2**. Thus the incidence geometry is not totally unimodular: the continuous polytope contains a fractional state that is not an integer matching. The same system is inconsistent over GF(2), so parity is a valid polynomial-time algebraic shadow that detects this particular obstruction. This gives RRLS a concrete interpretation of a "tear": projection creates a fractional or phantom state; the missing integral compatibility is stored in a lattice/coset coordinate invisible to the lower representation. --- ## 4. Algebraic shadows kill most random 3DM projection gaps — but not all RRLS generated 3DM no-instances that already survived all three pairwise perfect-matching tests, then applied finite-field shadows and LP feasibility. | n | no_instances | median_triples | GF2_reject_rate | any_prime_reject_rate | LP_reject_rate | survive_all_rate | median_exact_search_nodes | |----:|---------------:|-----------------:|------------------:|------------------------:|-----------------:|-------------------:|----------------------------:| | 3 | 250 | 7 | 0.476 | 0.48 | 0.936 | 0.024 | 3 | | 4 | 250 | 11 | 0.24 | 0.244 | 0.932 | 0.048 | 5 | | 5 | 250 | 16 | 0.168 | 0.176 | 0.904 | 0.076 | 7 | | 6 | 250 | 22 | 0.032 | 0.044 | 0.944 | 0.056 | 10 | The key result is the residual: - for n=6, about **5.6%** of tested no-instances survived every tested GF(p) consistency check *and* the ordinary LP relaxation. These survivors are much stronger adversarial cores than generic random SAT formulas. --- ## 5. Naive dimensional lifting failed RRLS then lifted the GF(2) exact-cover system to monomial coordinates: D1: x_i D2: x_i, x_i x_j D3: x_i, x_i x_j, x_i x_j x_k Every original coverage equation was multiplied by lower-degree monomials and re-linearized using x_i^2=x_i. Measured: | n | no_instances | median_triples | D1_reject | D2_reject | D3_reject | median_D3_monomials | survive_D3 | |----:|---------------:|-----------------:|------------:|------------:|------------:|----------------------:|-------------:| | 3 | 150 | 7 | 0.46 | 0.46 | 0.46 | 63 | 0.54 | | 4 | 150 | 11 | 0.206667 | 0.206667 | 0.206667 | 231 | 0.793333 | | 5 | 120 | 16 | 0.175 | 0.175 | 0.175 | 696 | 0.825 | | 6 | 80 | 21 | 0.0375 | 0.0375 | 0.0375 | 1561 | 0.9625 | Degree 2 and degree 3 rejected **no additional instances** over degree 1 in this test. So merely adding more coordinates is not enough. A useful lift must add a genuinely new invariant or global relation, not redundant copies of the same algebra. --- ## 6. The new missing-link candidate: Relational Width The unsafe collapse rule is: solved subproblem -> one bit / scalar answer. The safe rule is: solved subproblem -> exact relation on its boundary coordinates. Let a problem be decomposed into a region R and its boundary S. Define B_R(S) = { boundary assignments extendable to a valid solution inside R }. When R is eliminated, RRLS must preserve B_R, not merely SAT(R). This is exactly the information that the 3DM projection counterexample loses. ### Relational Width Define, for an RRLS operator language L, rw_L(R,S) = minimum description length in L of B_R(S). The computational width of an elimination is then governed by the maximum boundary relation description cost, not merely by the number of variables in the separator. This generalizes ordinary width measures: - an arbitrary table on k boundary bits may cost Θ(2^k); - a parity relation over k bits is still O(k); - an ALLDIFFERENT relation can have large arity but a compact matching representation; - a linear system may have a large boundary but a polynomial matrix description. This is the strongest current RRLS theorem target. --- ## 7. What would actually prove P=NP through this route It would be sufficient to construct one fixed, uniform relational language L and prove that for every SAT instance there is a polynomial-time elimination/compilation sequence such that: 1. every boundary relation produced is represented exactly; 2. every relation representation has size polynomial in the original input; 3. recognizing, composing, projecting and simplifying relations in L is polynomial; 4. the number of compilation steps is polynomial; 5. no exponential table/advice/precomputation is hidden in L. Then SAT would be in P, hence P=NP. v0.14 has **not** proved this closure theorem. The current residual 3DM cores are concrete counterexamples to all weaker forms of the claim that rely only on pairwise projections, simple finite-field shadows, LP feasibility, or naive degree-3 GF(2) monomial lifts. --- ## 8. Next research loop The next operator market should search representations of B_R rather than search only assignments. Candidate global languages: - totally-unimodular / balanced matrix structure; - matroid and matching-style exchange relations; - parity / modular linear systems; - cut and flow relations; - convex/LP separation certificates; - semidefinite / sum-of-squares shadows; - symmetry/orbit quotient relations; - tensor factorization and low-rank boundary signatures; - polymorphism/domain-lift discovery. The hard gate stays unchanged: no P=NP claim until exact universal closure + polynomial worst-case proof.