A continuous characterization of PSPACE using polynomial ordinary differential equations
DOI10.1016/J.JCO.2023.101755OpenAlexW4360999625MaRDI QIDQ6155896FDOQ6155896
Authors: Olivier Bournez, Daniel Graça, Amaury Pouly 
Publication date: 7 June 2023
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2023.101755
computational complexityordinary differential equationsPSPACEanalog computationgeneral purpose analog computercontinuous models of computation
Theory of computing (68Qxx) Computability and recursion theory (03Dxx) General theory for ordinary differential equations (34Axx)
Cites Work
- Computability with polynomial differential equations
- Computational complexity of solving polynomial differential equations over unbounded domains
- Computability, noncomputability and undecidability of maximal intervals of IVPs
- Effective computability of solutions of differential inclusions: the ten thousand monkeys approach
- Title not available (Why is that?)
- Title not available (Why is that?)
- A tutorial on computable analysis
- Lipschitz continuous ordinary differential equations are polynomial-space complete
- Analog computers and recursive functions over the reals.
- Polynomial differential equations compute all real computable functions on computable compact intervals
- Some recent developments on Shannon's General Purpose Analog Computer
- Mathematical Theory of the Differential Analyzer
- Universal computation and other capabilities of hybrid and continuous dynamical systems
- Title not available (Why is that?)
- Theory and Applications of Models of Computation
- Iteration, inequalities, and differentiability in analog computers
- On the functions generated by the general purpose analog computer
- Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
- Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
- 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
- Approximability in the GPAC
- Analog networks on function data streams
Cited In (1)
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)
