论文标题
使用离散的普通微分方程的多项式时间可计算函数的表征可计算的函数
A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations
论文作者
论文摘要
在最近的一篇文章中，使用离散的普通微分方程（ODE）（也称为有限差异）表征了从整数到可计算的整数的函数类别。这样做，我们指出了线性（离散）ODES和经典ODE工具的基本作用，例如变量的变化以捕获可计算性和复杂性度量，或作为编程工具。在本文中，我们将函数表征的方法从整数中扩展到可计算分析的多项式时间中可计算的真实物质。特别是，我们根据包含一些基本功能的最小函数提供了此类功能的表征，并且通过组成，线性长度频率和自然有效极限模式封闭。
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, we 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.
