Computational complexity aims to understand the fundamental limitations and capabilities of efficient computation. For example, which computational problems inherently require a huge running time to solve, no matter how clever an algorithm one designs? This most basic question of computational complexity is now understood to be both extremely difficult and of great importance, as demonstrated by all the attention given to the famous P vs. NP question. At the same time, however, this is but one of many the fascinating issues addressed by complexity theory (and covered in this course). First, running time will not be the only computational resource we consider, but also space/memory, nondeterminism, randomness, parallelism, communication, algebraic operations, and quantum mechanics. We will also study a variety of types of computational problems, such as decision, search, counting, optimization, and proof verification. We will introduce an array of complexity classes to capture these resources and problem types. We will use the powerful notions of reduction and completeness to establish relationships between seemingly unrelated problems, classes, and resources. Indeed, it is in discovering such connections that complexity theory has had its greatest successes, and we will see one of the most surprising ones: the equivalence between probabilistic verification of mathematical proofs (PCPs) and the complexity of finding approximate solutions to optimization problems. We will also examine various approaches to separating P and NP, and more generally to proving lower bounds on complexity. Finally, we will study what happens when one relaxes the requirement for an algorithm to be "correct", for example from worst-case complexity to average-case complexity or from exact solutions to approximate solutions.