Analog characterization of complexity classes

The purpose of the present dissertation is to characterize complexity classes from standard computational complexity theory by means of systems of ordinary differential equations. We start this work by recalling the concepts of generable functions as functions represented by solutions of polynomial ordinary differential equations. Then we present the details about a previous existing analog characterization for the classes P and FP. Building on this result we show how to extend the characterization for the class FEXPTIME, and then for the classes of elementary functions and primitive recursive functions. To be able to obtain these extensions we have to overcome the fact that the previous construction designed for FP relied on composition properties of polynomials which does not stand for other general boundaries. We also demonstrate that with some modifications to the main definitions of our simulation it is possible to provide a description of complexity classes of decidable sets, such as EXPTIME. Moreover, modifying the way the continuous simulation of Turing machines is performed we are able to provide a complete characterization of the polynomial space complexity classes FPSPACE and PSPACE. Finally, we discuss the complexity of the problem of computing the complex square root over simply connected domains of the complex plane, describing an algorithm that proves the upper complexity bound to belong to the class P^ParityP. This description improves the existing computational complexity result for this problem, which was achieved with an algorithm of complexity P^MP.

Recommended citation: Gozzi, Riccardo, and Daniel Graça. Analog characterization of complexity classes. Diss. PhD thesis, Instituto Superior Técnico, Lisbon, Portugal and University of Algarve, Faro, Portugal, 2022. https://scholar.tecnico.ulisboa.pt/api/records/eQCtqawIw3sb-UklVdtD8gkBmFIHud3r3Ptg/file/4ce8a8dc534ad948f22c6a95028001f9e1220e4faac0935424dd49817c14a8a3.pdf