No Cover Image

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.

Check full text

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...

Full description

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!
first_indexed 2022-06-07T14:04:24Z
last_indexed 2023-01-11T14:41:55Z
id cronfa60147
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-07-07T10:46:17.6320412</datestamp><bib-version>v2</bib-version><id>60147</id><entry>2022-06-07</entry><title>Representations and evaluation strategies for feasibly approximable functions</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-07</date><deptcode>SCS</deptcode><abstract>A famous result due to Ko and Friedman (Theoretical Computer Science 20 (1982) 323&#x2013;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.</abstract><type>Journal Article</type><journal>Computability</journal><volume>10</volume><journalNumber>1</journalNumber><paginationStart>63</paginationStart><paginationEnd>89</paginationEnd><publisher>IOS Press</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>2211-3568</issnPrint><issnElectronic>2211-3576</issnElectronic><keywords>Computable analysis, computational complexity, real functions, polynomial approximation</keywords><publishedDay>20</publishedDay><publishedMonth>1</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-01-20</publishedDate><doi>10.3233/com-180234</doi><url/><notes>Author accepted manuscript available from: https://research.aston.ac.uk/en/publications/representations-and-evaluation-strategies-for-feasibly-approximab</notes><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2022-07-07T10:46:17.6320412</lastEdited><Created>2022-06-07T15:00:44.9613613</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Michal</firstname><surname>Kone&#x10D;n&#xFD;</surname><order>1</order></author><author><firstname>Eike</firstname><surname>Neumann</surname><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2022-07-07T10:46:17.6320412 v2 60147 2022-06-07 Representations and evaluation strategies for feasibly approximable functions 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-06-07 SCS 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. Journal Article Computability 10 1 63 89 IOS Press 2211-3568 2211-3576 Computable analysis, computational complexity, real functions, polynomial approximation 20 1 2021 2021-01-20 10.3233/com-180234 Author accepted manuscript available from: https://research.aston.ac.uk/en/publications/representations-and-evaluation-strategies-for-feasibly-approximab COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2022-07-07T10:46:17.6320412 2022-06-07T15:00:44.9613613 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Michal Konečný 1 Eike Neumann 2
title Representations and evaluation strategies for feasibly approximable functions
spellingShingle Representations and evaluation strategies for feasibly approximable functions
Eike Neumann
title_short Representations and evaluation strategies for feasibly approximable functions
title_full Representations and evaluation strategies for feasibly approximable functions
title_fullStr Representations and evaluation strategies for feasibly approximable functions
title_full_unstemmed Representations and evaluation strategies for feasibly approximable functions
title_sort Representations and evaluation strategies for feasibly approximable functions
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Michal Konečný
Eike Neumann
format Journal article
container_title Computability
container_volume 10
container_issue 1
container_start_page 63
publishDate 2021
institution Swansea University
issn 2211-3568
2211-3576
doi_str_mv 10.3233/com-180234
publisher IOS Press
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description 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.
published_date 2021-01-20T04:18:01Z
_version_ 1763754200248877056
score 11.013686

Similar Items