Por Eduardo Skapinakis (NOVAMath, Universidade Nova de Lisboa).

While complexity classes are usually defined as the problems that can be solved by some computational model, under some resource bound, there is a variety of ways to characterize them without mentioning either of them. This is the topic of Implicit Complexity.

I will talk about the study of Complexity from the perspective of recursive functions, discussing the tools to capture non-deterministic, probabilistic and quantum classes and the role of composition in characterizing and restricting access to oracles.

Transmissão via Zoom.