Por Luís Pereira (Universidade de Lisboa).
In the 1980's and 1990's Attila Maté and Claude Sureson gave a characterization of the Computational Complexity problem NP vs coNP that involves extensions of models of arithmetic. In this first of two informal seminars, in which I will ask questions to more knowledgeable members of the audience, I will present the reasoning behind Máté's side of the implication and how it formed the context in which Ajtai's proof that Parity is not first order definable over finite models, was conceived. This last result, in its parallel translation to the language of Boolean circuits, that Parity is not in AC^0, was the spark that ignited the enthusiasm of the 1980's for the Boolean circuit approach to Computational Complexity.
Transmissão via Zoom (pw: 919 4789 5133).
