A Complexity Theory for Constructible Functions and Sheaves
summary
Claims a singly exponential bound and an explicit algorithm for the derived direct image of a constructible sheaf under a polynomial map: given a semi‑algebraic partition subordinate to the input sheaf, the pushforward admits a semi‑algebraic partition subordinate to the output with pieces and stalk Betti numbers bounded singly exponentially and computable in the BSS model. Tools: semi‑algebraic geometry, Hardt triviality, contractible coverings, spectral sequences and derived direct image machinery for constructible sheaves. Proposes complexity classes (sheaf/P vs sheaf/NP analogues) and conjectures separations.
AI-written summary · about