February 5, 2008
Alexander Razborov, Steklov Mathematical Institute and IAS
Grand Challenges in Complexity Theory
ABSTRACT: 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.