Talk by Riccardo Gozzi: «Analog characterization of standard complexity classes by means of ODEs»
For a new seminar of the proofs and algorithms pole of LIX, we are happy to welcome Riccardo Gozzi.
Abstract: In this presentation it will be shown how to make use of ordinary differential equations (ODEs) to describe standard complexity classes. Previously it was shown that the classes P and FP can be characterized with ODEs. Here we show that ODEs can also be used to characterize a wide range of computable functions, from exponentials up to including all elementary functions. It will be also discussed the case of space complexity classes, introducing the definition of a particular dynamical system able to describe functions in FPSPACE. Finally, to complement what have been done with functions, the treatment of classes of languages such as EXPTIME and PSPACE will be included in the analysis.