The traveling-salesman problem is an example of a {combinatorial optimization problem}, in which one wishes to sift through a vast number of patterns, combinations, arrangements or schedules to find one that is most efficient or least costly. Closely related are {combinatorial decision problems}, in which the task is to decide whether there exists an arrangement that satisfies a stated set of constraints. Such problems arise throughout the sciences and in every area of industry: examples range from placing components on a computer chip to scheduling classes at a school to sequencing a genome. Some of these problems admit {polynomial-time algorithms}, in which the number of computation steps grows as some fixed power of the size of the instance, but most seem to require an exponentially growing number of steps.
Many combinatorial decision problems are like jig-saw puzzles: they are hard to solve, but once a solution is revealed it is easy to verify. The collection of all such easy-to-verify problems is called NP. One of the most famous open problems in mathematics is whether every problem in NP is solvable in polynomial time. This appears unlikely, since many problems in NP have evaded solution for many decades.
A problem in NP is called {NP-complete} if a polynomial-time algorithm for its solution would yield polynomial-time solutions for all the problems in NP. Using a concept of reducibility between problems, computer scientists have exhibited many thousands of NP-complete problems.
Most combinatorial optimization problems are as hard as the NP-complete problems, but one can often be satisfied with solutions that are of approximately minimum cost, but not of strictly minimum cost. In practice heuristic algorithms, often motivated by analogies with physics or biology, often succeed in producing good approximate solutions, but computer scientists have shown that, in many cases, producing a decent approximate solution is as hard as producing the best possible solution.
The lecture will conclude with a discussion of how NP-completeness and related concepts of computational complexity have had echoes in fields ranging from cryptography, where secure communication depends on the intractability of factoring large integers, to economic theory, where the cost of rational decision-making is increasingly taken into account.