Traveling salesman problem

The traveling salesman problem is a prominent illustration of a class of problems in complexity theory. See Sharp-P.

An [approximative solution] for 1512 cities in Germany was found 2001 by the Princeton University.