# RRLS v0.15 — The Knowledge-Compilation Wall ## Status **P = NP is not proved.** v0.15 found a stronger formulation of the missing link: > A short description is insufficient. RRLS needs an exact representation that is > simultaneously compact and closed under the reasoning operations required by the > computation. CNF itself is already a polynomial-size representation of SAT instances. Merely compressing it into another compact syntax does not make satisfiability polynomial. The relevant dimensions are therefore: representation size SAT/consistency cost conjunction/composition cost existential forgetting/projection cost cost of changing representation cost of finding the representation path All must remain polynomial. --- ## 1. Boundary-relation experiment RRLS profiled exact Boolean relations using: - affine/GF(2) recognition - Algebraic Normal Form sparsity - greedy invertible GF(2) coordinate shears - sampled OBDD variable orders - exact Cartesian factorization - Walsh/Fourier support - balanced tensor/matrix flattening rank Canonical results include: | family | k | cases | median_density | median_anf | median_rot_anf | median_bdd | median_walsh | median_real_rank | median_gf2_rank | affine_rate | factor_rate | anf_fraction | rot_anf_fraction | |:-------------|----:|--------:|-----------------:|-------------:|-----------------:|-------------:|---------------:|-------------------:|------------------:|--------------:|--------------:|---------------:|-------------------:| | CNF-boundary | 6 | 3 | 0.046875 | 4 | 3 | 7 | 64 | 1 | 1 | 0.333333 | 1 | 0.0625 | 0.046875 | | CNF-boundary | 8 | 3 | 0.0195312 | 40 | 6 | 14 | 256 | 2 | 2 | 0.333333 | 0.333333 | 0.15625 | 0.0234375 | | CNF-boundary | 10 | 3 | 0.000976562 | 32 | 1 | 10 | 1024 | 1 | 1 | 1 | 1 | 0.03125 | 0.000976562 | | HWB | 6 | 1 | 0.5 | 31 | 11 | 21 | 52 | 6 | 6 | 0 | 0 | 0.484375 | 0.171875 | | HWB | 8 | 1 | 0.5 | 125 | 64 | 47 | 216 | 8 | 8 | 0 | 0 | 0.488281 | 0.25 | | HWB | 10 | 1 | 0.5 | 503 | 389 | 94 | 956 | 10 | 10 | 0 | 0 | 0.491211 | 0.379883 | | HWB | 12 | 1 | 0.5 | 2009 | 1549 | 162 | 3879 | 12 | 12 | 0 | 0 | 0.490479 | 0.378174 | | majority | 6 | 1 | 0.65625 | 35 | 35 | 12 | 64 | 4 | 4 | 0 | 0 | 0.546875 | 0.546875 | | majority | 8 | 1 | 0.636719 | 71 | 57 | 20 | 256 | 5 | 5 | 0 | 0 | 0.277344 | 0.222656 | | majority | 10 | 1 | 0.623047 | 627 | 627 | 30 | 1024 | 6 | 6 | 0 | 0 | 0.612305 | 0.612305 | | majority | 12 | 1 | 0.612793 | 1419 | 1419 | 42 | 4096 | 7 | 7 | 0 | 0 | 0.346436 | 0.346436 | | multiplexer | 6 | 1 | 0.5 | 9 | 4 | 7 | 16 | 3 | 3 | 0 | 0 | 0.140625 | 0.0625 | | multiplexer | 11 | 1 | 0.5 | 27 | 13 | 15 | 64 | 4 | 4 | 0 | 0 | 0.0131836 | 0.00634766 | | parity | 6 | 1 | 0.5 | 6 | 1 | 11 | 1 | 2 | 2 | 1 | 0 | 0.09375 | 0.015625 | | parity | 8 | 1 | 0.5 | 8 | 1 | 15 | 1 | 2 | 2 | 1 | 0 | 0.03125 | 0.00390625 | | parity | 10 | 1 | 0.5 | 10 | 2 | 19 | 1 | 2 | 2 | 1 | 0 | 0.00976562 | 0.00195312 | | parity | 12 | 1 | 0.5 | 12 | 2 | 23 | 1 | 2 | 2 | 1 | 0 | 0.00292969 | 0.000488281 | | random50 | 6 | 1 | 0.4375 | 30 | 18 | 21 | 52 | 7 | 6 | 0 | 0 | 0.46875 | 0.28125 | | random50 | 8 | 1 | 0.488281 | 123 | 92 | 68 | 256 | 16 | 14 | 0 | 0 | 0.480469 | 0.359375 | | random50 | 10 | 1 | 0.491211 | 522 | 432 | 225 | 1024 | 32 | 29 | 0 | 0 | 0.509766 | 0.421875 | | random50 | 12 | 1 | 0.514893 | 2007 | 1915 | 719 | 4096 | 64 | 61 | 0 | 0 | 0.48999 | 0.467529 | Parity is the clean positive example. An invertible GF(2) rotation turns parity into a single coordinate; its Fourier support is one and it is recognized as affine. Random 50%-density relations trend toward: - roughly half of all ANF coefficients nonzero; - full Fourier support; - balanced flattening rank approaching the maximum; - rapidly growing sampled OBDD size; - no affine or product decomposition. This validates the coordinate-search idea while also showing that no single current vocabulary is close to universal. --- ## 2. Hidden Weighted Bit: compact source, expensive OBDD Measured extension: | k | states | sampled_obdd_nodes | anf_terms | rotated_anf_terms | rotation_accepts | walsh_nonzero | min_sampled_real_flat_rank | min_sampled_gf2_flat_rank | seconds | sampled_order | flat_partition | |----:|---------:|---------------------:|------------:|--------------------:|-------------------:|----------------:|-----------------------------:|----------------------------:|----------:|:-------------------------------------------------------|:-------------------------| | 14 | 16384 | 333 | 8085 | 7711 | 6 | 16092 | 14 | 14 | 1.06274 | (13, 1, 0, 2, 11, 9, 7, 6, 8, 10, 3, 12, 4, 5) | (0, 1, 2, 3, 4, 5, 6) | | 16 | 65536 | 608 | 32799 | 32625 | 2 | 64224 | 16 | 16 | 2.30814 | (2, 0, 14, 4, 11, 5, 15, 1, 7, 6, 3, 9, 8, 10, 12, 13) | (0, 1, 2, 3, 4, 5, 6, 7) | At k=16: - truth states: 65,536 - sampled OBDD: 608 nodes - ANF: 32,799 terms - after tested GF(2) shears: 32,625 terms - Walsh support: 64,224 / 65,536 - balanced sampled ranks: full 16/16 The finite experiment is not a lower-bound proof. The literature gives the stronger result: Hidden Weighted Bit has OBDD size Ω(2^(n/5)) for any variable order, despite having polynomial-size circuit representations. Therefore OBDD cannot be RRLS's universal target language. --- ## 3. DNNF is not the universal language either Knowledge-compilation lower-bound work gives polynomial-size CNF families whose every DNNF representation is exponentially large. So moving from OBDD to the much more expressive decomposable NNF family still does not give a universal polynomial-size tractable representation. This is an unconditional wall for that representation family, not merely an RRLS benchmark failure. --- ## 4. Bottom-up collapse itself has a known wall RRLS's historical loop was: solve small relation -> compile token -> combine tokens -> repeat. This is bottom-up knowledge compilation. Known lower bounds show formulas that have tiny final structured-DNNF representations but for which every bottom-up compilation sequence using conjunction/structure changes must generate exponentially large intermediate results. Therefore even the existence of a compact *final* representation is insufficient. The intermediate compatibility relations are where complexity can reappear. That directly confirms the v0.14 "boundary relation" insight. --- ## 5. Operational Relational Width v0.15 replaces scalar compression width with a Pareto object. For exact boundary relation B and representation language L define ORW_L(B) = ( description_size, SAT_cost, conjunction_cost, forgetting_cost, transform_cost ). A relation is computationally cheap only if every coordinate needed by the algorithm is polynomially bounded. A "dimensional lift" is useful only when it lowers the operational vector rather than moving exponential cost from one coordinate to another. Examples: - truth table: easy queries, exponential representation; - CNF: compact, SAT may be hard; - OBDD: tractable queries, may require exponential size; - affine system: compact + tractable when the relation is genuinely affine; - matching representation: compact + tractable for matching structure. This is the rigorous version of RRLS's earlier "stored tension" idea: hardness can move between representation size and operation cost without disappearing. --- ## 6. Dynamic language paths A universal RRLS solver does not have to use one language. It may search a semantics-preserving path CNF -> affine -> matching -> decision diagram -> another lifted relation -> terminal with different regions using different algebras. But a real P=NP proof would need one **uniform polynomial-time pathfinder** and prove that for every SAT input: 1. the number of representation changes is polynomial; 2. every transformation is polynomial; 3. every intermediate representation has polynomial size; 4. all hidden vocabulary/advice is polynomial-size and uniformly constructible; 5. the terminal representation answers SAT in polynomial time. If these hold, SAT is in P and hence P=NP. No such universal path theorem is known or proved here. --- ## 7. What the next engine should search v0.16 should stop scoring representations primarily by compressed byte count. It should score **operation-aware transforms**: score = representation bits + measured/proved Apply cost + measured/proved Forget cost + decision cost + path-discovery cost. High-value candidate languages/operators: - affine and modular linear systems - matching/matroid exchange structure - flows/cuts - BDD/SDD/DNNF-style decompositions - symmetry/orbit quotients - tensor/factor graph decompositions - low-width circuit decompositions - semidefinite/SOS certificates - communication-complexity-guided separators The hard gate remains: no P=NP claim without a uniform polynomial worst-case proof.