Por Luís Pereira (Universidade de Lisboa).
In the 1980's and 1990's Attila Máté and Claude Sureson gave a characterization of the Computational Complexity problem NP vs coNP that involves extensions of models of arithmetic. In this second informal seminar I will talk about Sureson's direction of implication. I will emphasize how the structure of its proof resembles the structure of the proof of Wilkie's Theorem that states that any non-standard model of arithmetic M has an end-extension N with solutions to diophantine equations previously unsolvable in M. I will review the basic facts about models of arithmetic, so no prior knowledge will be required to follow the proofs.
Transmissão via Zoom (pw: 919 4789 5133).