Journal article 677 views
Representations and evaluation strategies for feasibly approximable functions
Michal Konečný,
Eike Neumann
Computability, Volume: 10, Issue: 1, Pages: 63 - 89
Swansea University Author: Eike Neumann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.3233/com-180234
Abstract
A famous result due to Ko and Friedman (Theoretical Computer Science 20 (1982) 323–352) asserts that the problems of integration and maximisation of a univariate real function are computationally hard in a well-defined sense. Yet, both functionals are routinely computed at great speed in practice.We...
| Published in: | Computability |
|---|---|
| ISSN: | 2211-3568 2211-3576 |
| Published: |
IOS Press
2021
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa60147 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
A famous result due to Ko and Friedman (Theoretical Computer Science 20 (1982) 323–352) asserts that the problems of integration and maximisation of a univariate real function are computationally hard in a well-defined sense. Yet, both functionals are routinely computed at great speed in practice.We aim to resolve this apparent paradox by studying classes of functions which can be feasibly integrated and maximised, together with representations for these classes of functions which encode the information which is necessary to uniformly compute integral and maximum in polynomial time. The theoretical framework for this is the second-order complexity theory for operators in analysis which was introduced by Kawamura and Cook (ACM Transactions on Computation Theory 4(2) (2012) 5).The representations we study are based on approximation by polynomials, piecewise polynomials, and rational functions. We compare these representations with respect to polytime reducibility.We show that the representation based on approximation by piecewise polynomials is polytime equivalent to the representation based on approximation by rational functions.With this representation, all terms in a certain language, which is expressive enough to contain the maximum and integral of most functions of practical interest, can be evaluated in polynomial time. By contrast, both the representation based on polynomial approximation and the standard representation based on function evaluation, which implicitly underlies the Ko-Friedman result, require exponential time to evaluate certain terms in this language.We confirm our theoretical results by an implementation in Haskell, which provides some evidence that second-order polynomial time computability is similarly closely tied with practical feasibility as its first-order counterpart. |
|---|---|
| Item Description: |
Author accepted manuscript available from: https://research.aston.ac.uk/en/publications/representations-and-evaluation-strategies-for-feasibly-approximab |
| Keywords: |
Computable analysis, computational complexity, real functions, polynomial approximation |
| College: |
Faculty of Science and Engineering |
| Issue: |
1 |
| Start Page: |
63 |
| End Page: |
89 |