Grand Challenges in Complexity Theory
The story I 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.