English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The outcomes of this paper are twofold. Implicit complexity.  We provide an implicit characterization of polynomial time computation interms of ordinary differential equations: we characterize the class PTIME oflanguages computable in polynomial time in terms of differential equations withpolynomial right-hand side. This result gives a purely continuous elegant andsimple characterization of PTIME. We believe it is the first time complexityclasses are characterized using only ordinary differential equations. Ourcharacterization extends to functions computable in polynomial time over thereals in the sense of computable analysis. Our results may provide a newperspective on classical complexity, by giving a way to define complexityclasses, like PTIME, in a very simple way, without any reference to a notion of(discrete) machine. This may also provide ways to state classical questionsabout computational complexity via ordinary differential equations.  Continuous-Time Models of Computation.  Our results can also be interpreted in terms of analog computers or analogmodels of computation: As a side effect, we get that the 1941 General PurposeAnalog Computer (GPAC) of Claude Shannon is provably equivalent to Turingmachines both in terms of computability and complexity, a fact that has neverbeen established before. This result provides arguments in favour of ageneralised form of the Church-Turing Hypothesis, which states that anyphysically realistic (macroscopic) computer is equivalent to Turing machinesboth in terms of computability and complexity.

Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length (Journal version)