Mathematical Logic Webinar

Continuous characterizations of computational complexity classes with ordinary differential equations


Por Daniel Graça (University of Algarve).

In this talk we will show that traditional computational complexity classes such as P, EXPTIME, or PSPACE can be characterized using polynomial ordinary differential equations, and that the same can be done for other classes such as the Grzegorczyk hierarchy and the class of primitive recursive functions. This talk describes work done in collaboration with O. Bournez, R. Gozzi, and A. Pouly.

Transmissão via Zoom.

CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional