the mathematical discovery, formalized in the 1970s by Stephen Cook and Richard Karp, that many natural optimization problems belong to a class (NP-hard) for which no efficient solution algorithm is known or believed to exist. The traveling salesman problem (find the shortest route visiting all citi