29 janvier 2024
Riccardo Gozzi (LACL)The purpose of this talk is to characterize complexity classes from standard computational complexity theory using systems of ordinary differential equations. We start by recalling concepts related to the general research field of analog computing, from a physical, theoretical, and abstraction level. We then proceed to provide historical context to the main model of the talk, the GPAC from C. Shannon, which describes the behavior of the analog machine called differential analyser. We then explain the evolution that the model had in literature throughout the years and present the details about the analog characterization for the classes P and FP, which connects the GPAC model with the discrete model of Turing machines. We explain how this equivalence should be intended and what are its main consequences. Finally, we briefly discuss some of the more recent developments on the subject, mentioning how to extend the characterization for the class FEXPTIME, for each level of the Grzegorczyk hierarchy, and for polynomial space complexity classes such as FPSPACE and PSPACE.