NP-completeness of the Hamming salesman problem
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
scientific article; zbMATH DE number 3887437