View in EDS

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

Saved in:
Bibliographic Details
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 192401451
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Xie%2C+Jingnan%22">Xie, Jingnan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> jingnan.xie@millersville.edu</i><br /><searchLink fieldCode="AR" term="%22Lin%2C+Ching-Sheng%22">Lin, Ching-Sheng</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> cslin612@thu.edu.tw</i><br /><searchLink fieldCode="AR" term="%22Hunt+III%2C+Harry+B%2E%22">Hunt III, Harry B.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> huntharryiii@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Stearns%2C+Richard+E%2E%22">Stearns, Richard E.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> thestearns2@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Jun2026, Vol. 70 Issue 2, p1-26. 26p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Fredholm+equations%22">Fredholm equations</searchLink><br /><searchLink fieldCode="DE" term="%22Jacobian+matrices%22">Jacobian matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Injective+functions%22">Injective functions</searchLink><br /><searchLink fieldCode="DE" term="%22Recursion+theory%22">Recursion theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192401451
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-026-10269-8
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 26
        StartPage: 1
    Subjects:
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Fredholm equations
        Type: general
      – SubjectFull: Jacobian matrices
        Type: general
      – SubjectFull: Injective functions
        Type: general
      – SubjectFull: Recursion theory
        Type: general
    Titles:
      – TitleFull: A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Xie, Jingnan
      – PersonEntity:
          Name:
            NameFull: Lin, Ching-Sheng
      – PersonEntity:
          Name:
            NameFull: Hunt III, Harry B.
      – PersonEntity:
          Name:
            NameFull: Stearns, Richard E.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 70
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1