The traveling salesman problem, or TSP for short, is this: given a finite number of ``cities'' along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. (Here, we consider just the symmetric TSP, where traveling from city X to city Y costs the same as traveling from Y to X; the ``way of visiting all the cities'' is simply the order in which the cities are visited.) To put it differently, in terms of ``graph theory'' the data consist of integer weights assigned to the edges of a finite complete graph; the objective is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context, hamiltonian cycles are commonly called tours.
This is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are hard to solve.