Depth Entropy H_d and the P vs NP Boundary: A Structural Separation via Resolution Lower Bounds
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
This paper introduces depth entropy (H_d), a structural measure of computational complexity defined as the Shannon entropy of the forward/backward step distribution of an algorithm's execution trace. We demonstrate empirically that P-class algorithms exhibit H_d ≈ 0.20 bits while NP-class algorithms exhibit H_d ≈ 0.92 bits (gap = 0.71 bits, Cohen's d = 1.446, p ≈ 0). We connect this formally to resolution proof complexity via the DPLL-resolution equivalence theorem, establishing that resolution-based algorithms must perform 2^Ω(n/log n) forced H_d-increasing steps on hard unsatisfiable 3-SAT instances. The framework produces a falsifiable structural fingerprint for any claimed polynomial-time algorithm for NP-complete problems. Priority declared by Juan Gabriel Molina, March 27, 2026.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Computability
Logic
AI Algorithms
Advanced Graph Theory Research
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 27 March 2026
- Language
- EN