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.