Is there or is there not a polynomial-time algorithm for obviously finite bounded integer programming? I mean, this is my sermon: Is there or is there not?
—Jack Edmonds, 1991.1
The pursuit of the salesman through ever larger numbers of cities has led to breakthroughs in mathematics, computing, and engineering, as well as advances in numerous practical applications. This is the pride and joy of TSP researchers. But the step-by-step approach has not answered the mother-of-all complexity questions: can we efficiently solve every instance of the TSP?
The fate of the salesman from this complexity point of view is tied to that of many other problems, including general integer programming, via the theory of Stephen Cook and Richard Karp. ...