Some perspectives on computational complexity

In past decades, the theory of computational complexity has flourished in terms of both the revelation of its internal structures and the unfolding of its numerous applications. In this paper we discuss several persistent and interwoven themes underlying many of these accomplishments. Chief among them are the interplay between communication and computation, the power of problem reduction, and the increasingly prominent role played by classical mathematics. We will also speculate on a few promising directions for future development of computational complexity.