A continuous characterization of PSPACE using polynomial ordinary differential equations

DOI10.1016/j.jco.2023.101755OpenAlexW4360999625MaRDI QIDQ6155896

Daniel Silva Graça, Olivier Bournez, Amaury Pouly, Unnamed Author

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

zbMATH Keywords

computational complexityanalog computationgeneral purpose analog computerordinary differential equationsPSPACEcontinuous models of computation

Mathematics Subject Classification ID

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

Related Items (1)

Programming with ordinary differential equations: some first steps towards a programming language

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of solving polynomial differential equations over unbounded domains
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• Analog computers and recursive functions over the reals.
• On the functions generated by the general purpose analog computer
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Computability with polynomial differential equations
• Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
• Computational Complexity of Smooth Differential Equations
• Some recent developments on Shannon's General Purpose Analog Computer
• Computability, noncomputability and undecidability of maximal intervals of IVPs
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length (Journal version)
• Analog networks on function data streams
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• Mathematical Theory of the Differential Analyzer
• Theory and Applications of Models of Computation
• Iteration, inequalities, and differentiability in analog computers

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