Algorithmic Topological Assembly and the Structural Boundary of Polynomial-Time Computation
Abstract
This paper extends a topological approach to computational complexity by incorporating the structure of polynomial-time algorithms into the analysis of compatibility complexes. Building on earlier results showing that shallow and logarithmic-depth computation enforces low-dimensional topological simplicity, and that NP-complete problems exhibit high assembly complexity, it introduces algorithmic filtrations induced by execution traces. A new invariant, AET∗₄,alg, is defined to measure topological assembly compatible with computation. Using relative homology, spectral sequences, and discrete Morse theory, the paper proves that no polynomial-time algorithm can generate or sustain nontrivial fourth homology along such filtrations. Systematic attempts to construct counterexamples fail for structural reasons. The result isolates bounded algorithmic assembly as a necessary condition for polynomial-time computation.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Topological and Geometric Data Analysis
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 4 February 2026
- Language
- EN
- Document type
- Preprint