Bruce Schneier has solved the Travelling Salesman problem in O(1) time, but hasn't published it because he doesn't like salesmen.
Things you might not know about Bruce Schneier
Bruce Schneier has solved the Travelling Salesman problem in O(1) time, but hasn't published it because he doesn't like salesmen.