A continuous characterization of PSPACE using polynomial ordinary differential equations

DOI10.1016/J.JCO.2023.101755MaRDI QIDQ6155896zbMATH OpenOpenAlexFDO

Authors Olivier Bournez, Daniel Graça, Amaury Pouly

Publication date 7 June 2023

Published in Journal of Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.jco.2023.101755

zbMATH Keywords

analog computationcomputational complexitycontinuous models of computationgeneral purpose analog computerordinary differential equationsPSPACE

Mathematics Subject Classification ID

Computability and recursion theory (03Dxx) General theory for ordinary differential equations (34Axx) Theory of computing (68Qxx)

Cites work

• A tutorial on computable analysis
• Analog computers and recursive functions over the reals.
• Analog networks on function data streams
• Approximability in the GPAC
• Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
• Computability with polynomial differential equations
• Computability, noncomputability and undecidability of maximal intervals of IVPs
• Computational complexity of solving polynomial differential equations over unbounded domains
• Effective computability of solutions of differential inclusions: the ten thousand monkeys approach
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 766966 (Why is no real title available?)
• Iteration, inequalities, and differentiability in analog computers
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• Mathematical Theory of the Differential Analyzer
• On the functions generated by the general purpose analog computer
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• Some recent developments on Shannon's General Purpose Analog Computer
• Theory and Applications of Models of Computation
• Universal computation and other capabilities of hybrid and continuous dynamical systems

Cited in

(6)

• Programming with ordinary differential equations: some first steps towards a programming language
• Quantifiying the robustness of dynamical systems. Relating time and space to length and precision
• The complexity of computing in continuous time: space complexity is precision
• Computation with real numbers and continuous-time dynamical systems
• Solving discontinuous initial value problems with unique solutions is equivalent to computing over the transfinite
• Quantifying the robustness of dynamical systems. Relating time and space to length and precision

This page was built for publication: A continuous characterization of PSPACE using polynomial ordinary differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155896)