Very tangential, I was a physics major, and learned about Traveling Salesperson when in college at UCSD - I looked it up in the library and there was like, an entire hallway of books/research on this problem and it blew my mind. It really put into perspective how much work had gone into that single problem. I think the shelf was larger than the solar physics papers on file in a nearby area.