The world around us, including nature, society, science and mathematics, presents us with a large number and variety of computational problems. For each we seek solutions that minimize various resources while maintaining other desirable properties. The Theory of Computation is charged with figuring out the feasibility and costs of this multitude of problems. The past few decades of work have revealed remarkable structure: this complex world of problems, resources and properties clusters into a few natural groups which furthermore have conceptual meaning. I will survey some important aspects of this body of work, including: the tools of reduction and completeness, the reasons for clustering (which go to the very definition of computation by Turing), and the major challenges for a better understanding of this universe.
