Orador Convidado: Isabel Oitavem (NOVA Math and DM, FCT NOVA)
Resumo: For many of our everyday activities we heavily rely on the unknown, but somehow expected, gap between the complexity classes P and NP. In this talk we mention several complexity classes, but particular attention is given to these two key classes — P and NP.
Complexity classes are primarily defined based on models of computation, but several studies developed conceptually different approaches to complexity classes. Since Kleene, it is known that the of recursive functions corresponds to the computable functions.
In this talk we explore recursion-like approaches to complexity classes, explaining the main challenges faced in the process of characterizing P and NP [1]. We do also a brief mention to the major challenge of developing similar approaches to classes that seem to have a semantic nature, like the probabilistic BPP [2].
[1] I. Oitavem (2022), The polynomial hierarchy of functions and its levels. Theoretical Computer Science 900 (2022), pp.25-34. DOI:10.1016/j.tcs.2021.11.016
[2] M. Antonelli, U. Dal Lago, D. Davioli, I. Oitavem, P. Pistoni (2024) Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories. CSL2024, Leibniz International Proceedings in Informatics (LIPIcs). DOI: 10.4230/LIPIcs.CSL.2024.10.
Keywords: Computational Complexity, polynomial hierarchy, machine independent, recursion schemes.
Resumo
