Characterizing time computational complexity classes with polynomial differential equations

DOI10.3233/COM-210384OpenAlexW4294266235WikidataQ115222735 ScholiaQ115222735MaRDI QIDQ5880938FDOQ5880938

Authors: Daniel Graça 

Publication date: 9 March 2023

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-210384

Recommendations

• 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
• An analog characterization of the Grzegorczyk hierarchy
• Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations
• A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations

zbMATH Keywords

analog computationEXPTIMEGrzegorczyk hierarchycomputation with polynomial ordinary differential equations

Mathematics Subject Classification ID

Computability and recursion theory (03Dxx)

Cites Work

• Computability with polynomial differential equations
• Computational complexity of solving polynomial differential equations over unbounded domains
• Title not available (Why is that?)
• A tutorial on computable analysis
• Computational Complexity
• Title not available (Why is that?)
• Analog computers and recursive functions over the reals.
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Computing with polynomial ordinary differential equations
• Some recent developments on Shannon's General Purpose Analog Computer
• Mathematical Theory of the Differential Analyzer
• Classical recursion theory. Vol. II
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• Computational complexity of real functions
• Title not available (Why is that?)
• Theory and Applications of Models of Computation
• An analog characterization of the Grzegorczyk hierarchy
• Iteration, inequalities, and differentiability in analog computers
• Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions
• Title not available (Why is that?)
• On the functions generated by the general purpose analog computer
• Automata, Languages and Programming
• 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

Cited In (6)

• A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations
• Programming with ordinary differential equations: some first steps towards a programming language
• Computational complexity of solving polynomial differential equations over unbounded domains
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• Title not available (Why is that?)
• On the complexity of the differential-algebraic description of analytic complexity classes

This page was built for publication: Characterizing time computational complexity classes with polynomial differential equations

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