Characterisations of polynomial-time and -space complexity classes over the reals
Manon Blanc
Université Paris Saclay
https://perso.crans.org/mblanc/
Date(s) : 20/05/2025 iCal
11h00 - 12h00
Many recent works have studied how analogue computational 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. This 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 characterise PTIME and PSPACE for functions over the reals. We will use discrete ODEs first, and then we will show that we can use continuous ODEs. Also, we will see how we can relate polynomial space with the reachability in dynamical systems.
Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories
