Depth Entropy H_d and the P vs NP Boundary: A Structural Separation via Resolution Lower Bounds

Read full text Summarise with VIRAT
Authors: Juan Gabriel Molina
Cited by: 0

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