Proofs, Complexity, and Optimization

  • Date April 11, 2018
  • Hour 4 pm
  • Room GSSI Main Lecture Hall
  • Speaker Pierluigi Crescenzi (Universit√† di Firenze)


It is well known that proofs have always been one of the most important notions in mathematics, if not the most important one. It is maybe less known that proofs, as an abstract notion, also played and still play a central role in computer science. Indeed, the famous (still open) P?NP problem can be stated in terms of proof searching and verifying. Not only, proof verification turned out to be an essential tool in the field of approximation algorithms, in order to solve some long-standing open problems. In this talk we will review the deep connection between proofs, complexity, and optimization, and we will show how this connection has allowed us to better understand the limits of computers.