View in EDS

A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.

Saved in:
Bibliographic Details
Title: A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.
Authors: Blanc, Manon1,2 (AUTHOR) manon.blanc@lix.polytechnique.fr, Bournez, Olivier1 (AUTHOR) olivier.bournez@lix.polytechnique.fr
Source: International Journal of Foundations of Computer Science. Nov2025, Vol. 36 Issue 7, p989-1016. 28p.
Subjects: Computable functions, Computable analysis, Ordinary differential equations, Linear differential equations, Polynomial time algorithms, Mathematical functions, Computational complexity
Abstract: In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the authors pointed out the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company 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
Description
Abstract:In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the authors pointed out the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema. [ABSTRACT FROM AUTHOR]
ISSN:01290541
DOI:10.1142/S0129054124470014