Colloque des sciences mathématiques du Québec

15 octobre 2010 de 16 h 00 à 18 h 00 (heure de Montréal/Miami) Sur place

Grand Challenges in Complexity Theory

Colloque par Alexander Razborov

Conférence s'adressant à un large auditoire / Suitable for a general audience Modern complexity theory is a vast, loosely defined area. Its methods and methodology can be successfully applied whenever one has a set of tasks, a class of admissible solutions, and numerical characteristics to measure the "quality" of a solution. This talk will focus on two specific scenarios: classical computational complexity and proof complexity. The story we will tell, however, is highly representative of the methods that have been tried in the field at large, with its mixed bag of successes, setbacks, and promising directions. I will try to reveal some of the tight, beautiful and unexpected connections existing between different branches of complexity theory. I will discuss the "grand challenges" of the field, including "P vs NP" and questions about the power of classical proof systems. This talk will assume no prior knowledge in theoretical computer science.


CRM, UdeM, Pavillon André-Aisenstadt, 2920, chemin de la tour, salle 1360