The traveling salesman problem is one of the best-known examples of an algorithmically hard problem, but what does that mean formally? It turns out that a solution to this problem would immediately give a solution to any other NP problem, and in this sense we say it is "NP-complete." In this talk, we will give a more formal definition of what it means for a problem to be NP-complete, develop the machinery needed to prove NP-completeness, and then use this machinery to prove that the traveling salesman problem (and a few others) is indeed NP-complete.