Characterizing time computational complexity classes with polynomial	differential equations

Gozzi, Riccardo; Graça, Daniel

Publication

Characterizing time computational complexity classes with polynomial differential equations

2022Journal article

dc.contributor.author	Gozzi, Riccardo
dc.contributor.author	Graça, Daniel
dc.date.accessioned	2022-10-21T13:57:03Z
dc.date.available	2022-10-21T13:57:03Z
dc.date.issued	2022
dc.description.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.	pt_PT
dc.description.version	info:eu-repo/semantics/acceptedVersion	pt_PT
dc.identifier.doi	10.3233/COM-210384	pt_PT
dc.identifier.issn	2211-3568
dc.identifier.uri	http://hdl.handle.net/10400.1/18413
dc.language.iso	eng	pt_PT
dc.peerreviewed	yes	pt_PT
dc.publisher	IOS Press	pt_PT
dc.relation.publisherversion	https://doi.org/10.3233/COM-210384	pt_PT
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	pt_PT
dc.title	Characterizing time computational complexity classes with polynomial differential equations	pt_PT
dc.type	journal article
dspace.entity.type	Publication
oaire.citation.title	Computability	pt_PT
person.familyName	Graça
person.givenName	Daniel
person.identifier.ciencia-id	2D11-56DE-3F11
person.identifier.orcid	0000-0002-0330-833X
person.identifier.rid	D-2335-2011
person.identifier.scopus-author-id	8882791800
rcaap.rights	openAccess	pt_PT
rcaap.type	article	pt_PT
relation.isAuthorOfPublication	ba0c1461-5d2d-4f06-b648-df4a1a505bdf
relation.isAuthorOfPublication.latestForDiscovery	ba0c1461-5d2d-4f06-b648-df4a1a505bdf