The Traveling Salesman Problem and P vs. NP: Some 1960s Theoretical Work at NIST On the Complexity of Mathematical Algorithms.

An informal description for a general audience of some basic mathematical theory developed at NBS, and a bit of reminiscing about important mathematical NBS colleagues, Alan Hoffman, Alan Goldman, and Christoph Witzgall.

The TSP is to find an optimum way for a stylus or a salesman to move through any prescribed set of points. It turns out to still be algorithmically difficult. The most famous of unsolved mathematical questions is still whether or not the TSP will forever remain intrinsically difficult.

While researching the TSP at NBS, some other seemingly difficult algorithmic problems were nicely solved.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.