A Homological Proof of 𝐏≠𝐍𝐏: Computational Topology via Categorical Framework
Jian-Gang Tang
本文通过基于范畴论的新颖同调代数方法，建立了复杂度类P与NP的分离。我们构建了计算范畴Comp，将计算问题和归约嵌入到统一的范畴框架中。通过发展计算同调理论，我们将每个问题L与一个链复形C_∙(L)相关联，其同调群H_n(L)捕捉了计算过程的拓扑不变量。我们的主要结果表明，P类问题表现出平凡的计算同调（对所有n>0有H_n(L)=0），而NP完全问题如SAT具有非平凡同调（H_1(SAT)≠0）。这种同调区别提供了使用拓扑方法对P≠NP的第一个严格证明。该证明在Lean 4中进行了形式化验证，确保了绝对的数学严谨性。我们的工作开创了计算拓扑学作为复杂性分析的新范式，提供了比传统组合方法更精细的区分，并建立了结构复杂性理论与同调不变量之间的联系。
This paper establishes the separation of complexity classes 𝐏 and 𝐍𝐏 through a novel homological algebraic approach grounded in category theory. We construct the computational category 𝐂𝐨𝐦𝐩, 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_∙(L) whose homology groups H_n(L) capture topological invariants of computational processes. Our main result demonstrates ...
