Traveling salesman problem

The <b>traveling salesman problem</i> 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.