Đã lưu trong:
| Tác giả chính: | |
|---|---|
| Định dạng: | Recurso digital |
| Ngôn ngữ: | Tiếng Anh |
| Được phát hành: |
Zenodo
2025
|
| Những chủ đề: | |
| Truy cập trực tuyến: | https://doi.org/10.5281/zenodo.15660687 |
| Các nhãn: |
Thêm thẻ
Không có thẻ, Là người đầu tiên thẻ bản ghi này!
|
Mục lục:
- <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>