Computational Complexity Since 1980

摘要

Recently, I told a long-time friend who isn't a mathematician what I was working on. His shocked reply was that that was the exact same topic I was working on my first month of graduate school, which was very close to the truth. The classical challenges that have been with us for over two decades remain. We know so much more about the questions, but so little about the answers. (Of course, I have shortchanged the genuinely new areas of complexity, such as quantum complexity, in my pursuit of links with the past.) The more we study these problems, the closer the links between them seem to grow. On the one hand, it is hard to be optimistic about our area soon solving any one of these problems, since doing so would cut through the Gordian knot and lead to progress in so many directions. It seems that randomness does not make algorithms more powerful, but that we need to prove lower bounds on circuits to establish this. On the other hand, it seems that if cryptographic assumptions hold, proving circuit lower bounds is difficult. On the other hand, it is hard to be pessimistic about an area that has produced so many fascinating and powerful ideas. It is hard to be pessimistic when every year, substantial progress on another classical complexity progress is made. There are no safe bets, but if I had to bet, I would bet on the longshots. The real progress will be made in unexpected ways, and will only be perfectly reasonable in hindsight.