Characterizing time computational complexity classes with polynomial differential equations

Article type: Research Article

Authors: Gozzi, Riccardo^{a; b} | Graça, Daniel^{c; b; *}

Affiliations: [a] Instituto Superior Técnico, Universidade de Lisboa, Portugal | [b] Instituto de Telecomunicações, Portugal | [c] Universidade do Algarve, Portugal

Correspondence: [*] Corresponding author. dgraca@ualg.pt.

Abstract: In this paper we show that several classes of languages from computational complexity theory, such as EXPTIME, can be characterized in a continuous manner by using only polynomial differential equations. This characterization applies not only to languages, but also to classes of functions, such as the classes defining the Grzegorczyk hierarchy, which implies an analog characterization of the class of elementary computable functions and the class of primitive recursive functions.

Keywords: Analog computation, computation with polynomial ordinary differential equations, EXPTIME, Grzegorczyk hierarchy

DOI: 10.3233/COM-210384

Journal: Computability, vol. 12, no. 1, pp. 23-57, 2023