| _version_ | 1866902216911093760 |
|---|---|
| author | Ednyashev, Sanal |
| author_facet | Ednyashev, Sanal |
| contents | <p>This publication presents the formal proof and theoretical development of the L_σ(n) theorem — a structural-information barrier in Boolean satisfiability (SAT) solving. It establishes that for any k-local structural algorithm operating on a CNF formula φ represented structurally as σ(φ), the classification accuracy is bounded above by ½ + ε as the information loss L_σ(φ) increases.</p> <p> </p> <p>The theorem is grounded in the formal expression: </p> <p>**L_σ(n) = K(φ) – H(s(σ(φ)))**, </p> <p>where:</p> <p>- *K(φ)* denotes the Kolmogorov complexity of the formula,</p> <p>- *σ(φ)* is a structural representation (e.g., variable-clause graph),</p> <p>- *s(σ(φ))* is the serialized structural projection,</p> <p>- *H(·)* is Shannon entropy.</p> <p> </p> <p>The results show that even advanced machine learning models (e.g., GNNs) systematically degrade in performance on instances with high L_σ(n), confirming the existence of structural barriers. A full constructive proof is included, alongside the critical counterexample φ₄ where two structurally equivalent formulas diverge semantically (SAT vs UNSAT), exposing the limit of structure-only reasoning.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_15660687 |
| institution | Zenodo |
| language | eng |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | The L_σ(n) Theorem: Formal Structural Limits in SAT Solving and Information Loss Analysis Ednyashev, Sanal SAT solving ETH GNN L_σ(n) theorem information theory Kolmogorov complexity structural abstraction classifier limits natural proofs <p>This publication presents the formal proof and theoretical development of the L_σ(n) theorem — a structural-information barrier in Boolean satisfiability (SAT) solving. It establishes that for any k-local structural algorithm operating on a CNF formula φ represented structurally as σ(φ), the classification accuracy is bounded above by ½ + ε as the information loss L_σ(φ) increases.</p> <p> </p> <p>The theorem is grounded in the formal expression: </p> <p>**L_σ(n) = K(φ) – H(s(σ(φ)))**, </p> <p>where:</p> <p>- *K(φ)* denotes the Kolmogorov complexity of the formula,</p> <p>- *σ(φ)* is a structural representation (e.g., variable-clause graph),</p> <p>- *s(σ(φ))* is the serialized structural projection,</p> <p>- *H(·)* is Shannon entropy.</p> <p> </p> <p>The results show that even advanced machine learning models (e.g., GNNs) systematically degrade in performance on instances with high L_σ(n), confirming the existence of structural barriers. A full constructive proof is included, alongside the critical counterexample φ₄ where two structurally equivalent formulas diverge semantically (SAT vs UNSAT), exposing the limit of structure-only reasoning.</p> |
| title | The L_σ(n) Theorem: Formal Structural Limits in SAT Solving and Information Loss Analysis |
| topic | SAT solving ETH GNN L_σ(n) theorem information theory Kolmogorov complexity structural abstraction classifier limits natural proofs |
| url | https://doi.org/10.5281/zenodo.15660687 |