Complexity and Recursion

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.