2017/10/10 by Konečný, Michal, Neumann, Eike
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Mathematical and Theoretical Analysis
paper · pdf · doi:10.48550/arxiv.1710.03702
openalex publication_date 2017/10/10 · openalex created_date 2019/10/10 · openalex updated_date 2026/07/28
A famous result due to Ko and Friedman (1982) asserts that the problems of\nintegration and maximisation of a univariate real function are computationally\nhard in a well-defined sense. Yet, both functionals are routinely computed at\ngreat speed in practice. We aim to resolve this apparent paradox by studying\nclasses of functions which can be feasibly integrated and maximised, together\nwith representations for these classes of functions which encode the\ninformation which is necessary to uniformly compute integral and maximum in\npolynomial time. The theoretical framework for this is the second-order\ncomplexity theory for operators in analysis which was introduced by Kawamura\nand Cook (2012). The representations we study are based on rigorous\napproximation by polynomials, piecewise polynomials, and rational functions. We\ncompare these representations with respect to polytime reducibility as well as\nwith respect to their ability to quickly evaluate symbolic expressions in a\ngiven language. We show that the representation based on rigorous approximation\nby piecewise polynomials is polytime equivalent to the representation based on\nrigorous approximation by rational functions. With this representation, all\nterms in a certain language, which is expressive enough to contain the maximum\nand integral of most functions of practical interest, can be evaluated in\npolynomial time. By contrast, both the representation based on polynomial\napproximation and the standard representation based on function evaluation,\nwhich implicitly underlies the Ko-Friedman result, require exponential time to\nevaluate certain terms in this language. We confirm our theoretical results by\nan implementation in Haskell, which provides some evidence that second-order\npolynomial time computability is similarly closely tied with practical\nfeasibility as its first-order counterpart.\n