| Résume | Many recent works have studied how analogue models work, compared to classical digital ones. By “analogue” models of computation, we mean computing over continuous quantities, while “digital” models work on discrete structures. It led to a broader use of Ordinary Differential Equation (ODE) in computability theory. From this point of view, the field of implicit complexity has also been widely studied and developed.
We show here, using arguments from computable analysis, that we can algebraically and implicitly characterise PTIME and PSPACE for functions over the reals using discrete ODEs and continuous ODEs. |
