A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences

作     者：Xie, Jingnan Lin, Ching-Sheng Hunt, Harry B. Stearns, Richard E. 

作者机构：Computer Science Department Millersville University of PA 40 Dilworth Road MillersvillePA17551 United States Master Program of Digital Innovation Tunghai University 1727 Sec. 4 Taiwan Boulevard Xitun District Taichung40704 Taiwan Computer Science Department University at Albany SUNY 1400 Washington Avenue AlbanyNY12222 United States 

出 版 物：《SSRN》 

年 卷 期：2025年

核心收录：

主　　题：Fredholm integral equations 

摘      要：Computable analysis extends classical computability theory to continuous domains, investigating the computability and complexity of problems in mathematical analysis. In this paper, we develop a framework for analyzing the complexity of mathematical problems across various fields by constructing highly efficient many-one reductions. For example, we show that the equivalence-to-identically-zero-function problem is reducible to determining whether the Jacobian determinant of a set of functions is identically zero, whether a Fredholm integral equation of the first kind has no eigenvalue, whether a Fredholm integral equation of the second kind has a trivial solution, whether the gradient of a function is identically zero, whether all finite orbits are closed in a given potential, and whether the Poisson bracket of two functions vanishes. Building on prior undecidability and productiveness (a stronger form of non-recursive enumerability) results for the equivalence-to-identically-zero-function problem, we establish that these problems are productive for specific classes of elementary functions. Furthermore, we explore potential approaches for applying classical complexity classes, such as NP, PSPACE, and EXPTIME, to computable analysis by leveraging the efficiency of our reductions. Our results provide a unified proof technique for analyzing complexity across different scientific domains, offering a practical extension of computational complexity theory to continuous mathematical structures. © 2025, The Authors. All rights reserved.