• 03/04/2024 das 14h30 às 15h30 (CLAV 128 e online) 

Isabel Oitavem,  NOVA Math and DM, FCT NOVA, This email address is being protected from spambots. You need JavaScript enabled to view it.

Abstract: 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 class 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 class 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 Interna- tional Proceedings in Informatics (LIPIcs). DOI: 10.4230/LIPIcs.CSL.2024.10.

Keywords: Computational Complexity, polynomial hierarchy, machine independent, recursion schemes.

Attachments:
Download this file (Seminar_IsabelOitavem.pdf)Seminar_IsabelOitavem.pdf[ ]911 kB

Centro de Investigação em Matemática e Aplicações (CIMA)

Phone:  +351 266 745 353

Email Address:  dircima@uevora.pt

Address:   Colégio Luís Verney

                Rua Romão Ramalho, 59,
                7000-671 Évora,

                Portugal

Thesis

Logos