A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences.
Saved in:
| Title: | A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences. |
|---|---|
| Authors: | Xie, Jingnan1 (AUTHOR) jingnan.xie@millersville.edu, Lin, Ching-Sheng2 (AUTHOR) cslin612@thu.edu.tw, Hunt III, Harry B.3 (AUTHOR) huntharryiii@gmail.com, Stearns, Richard E.3 (AUTHOR) thestearns2@gmail.com |
| Source: | Theory of Computing Systems. Jun2026, Vol. 70 Issue 2, p1-26. 26p. |
| Subjects: | Computational complexity, Fredholm equations, Jacobian matrices, Injective functions, Recursion theory |
| Abstract: | 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. Future work includes exploring how classical complexity classes, such as NP, PSPACE, and EXPTIME, can be applied 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
