The CEMS.UL - Center for Mathematical Studies is promoting the seminar "Reflexivity of Omega-Consistency in a General Setting", with the participation of Isabel Oitavem (Universidade NOVA de Lisboa).
Abstract: Monotone computability was originally introduced through the study of negation-free circuits. In 1991, Grigni and Sipser initiated a line of research investigating the effects of "restricting negation" in other models of computation, leading to a more uniform approach to monotone complexity.
In this talk, we examine machine-independent approaches to positive (monotone) complexity classes. More precisely, we present recursion-theoretic characterisations of positive (monotone) counterparts of two fundamental complexity classes, P and NP. Our focus is on discussing recursion schemes in the monotone setting.
This talk is based on joint work with Das and Skapinakis.