2025/10/02 by Jian-Gang Tang, Jiangang Tang, Tang, Jian-Gang · 6 voices
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Homotopy and Cohomology in Algebraic Topology #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2510.17829
This paper establishes the separation of complexity classes P and NP through a novel homological algebraic approach grounded in category theory. We construct the computational category Comp, embedding computational problems and reductions into a unified categorical framework. By developing computational homology theory, we associate to each problem L a chain complex C\bullet(L) whose homology groups Hn(L) capture topological invariants of computational processes. Our main result demonstrates that problems in P exhibit trivial computational homology (Hn(L) = 0 for all n > 0), while NP-complete problems such as SAT possess non-trivial homology (H1(SAT) ≠ 0). This homological distinction provides the first rigorous proof of P ≠ NP using topological methods. Our work inaugurates computational topology as a new paradigm for complexity analysis, offering finer distinctions than traditional combinatorial approaches and establishing connections between structural complexity theory and homological invariants.