Wednesday, September 22, 2004

Polynomial puzzlement

I have received a truly fascinating request for my high quality advice.

Magus of Magaluf asks: "I have something of a problem. I am having trouble sleeping as I keep wondering if P=NP? In other words, is it possible for a deterministic Turing machine to solve in polynomial time problems which are solved by a nondeterministic Turing machine in polynomial time, or, on the contrary, is the traveling salesman problem truly "hard" in the sense that no polynomial-time algorithm exists to solve it?"

Are you sure you are having trouble sleeping? It sounds as though this would send anyone to sleep. However, you might be one of those odd people who enjoys working out complicatedness and therefore has no friends. I would suggest that if N=1 then P=NP, however, there are so many numbers in the world that the probability of N=1 is infinitly low. Therefore I suggest you go and find other hobbies and forget the travelling salesman. There are plenty more fish in the sea. Hope that helps, Magus.