The third in the fall series of Simons Institute Open Lectures. Suppose we are given an optimization problem where the quality of a proposed solution can be evaluated efficiently. The study of when this happens leads to the classical theory of NP-completeness that was intitiated in the 1970s and mostly completed before 1990. The most famous NP-complete problem is the Traveling Salesman Problem.