
Re: On NP Completeness and Intractability
Posted:
Oct 26, 2005 6:20 PM


In article <djmhrr$trn$1@news.msu.edu>, <stephen@nomail.com> wrote: >In comp.theory Nimmi Srivastav <nimmi_srivastav@yahoo.com> wrote: >> How can any solvable problem (albeit with an inefficient algorithm) be >> reduced to an unsolvable problem? It sounds somewhat counterintuitive >> on the surface.
[some explanation deleted]
>If we could solve the halting problem in polynomial time, then we could >determine if there existed a tour of cost K or less in polynomial time.
While technically accurate, this response may confuse Nimmi Srivastav more, because the condition "If we could solve the halting problem in polynomial time" sounds nonsensical since we know that this is impossible.
It might be helpful to emphasize that "reduction" here has a specific technical meaning. The word was not chosen arbitrarily and it does match the intuitive, informal meaning of the word "reduction" quite well; however, the match isn't perfect. In particular, in informal usage, saying that "A reduces to B" typically carries the connotation that some progress has been made in solving A, and that B is potentially more tractable or conceptually simpler or something. The technical meaning, however, does not have this denotation. It simply means that instances of problem A have been transformed into the format of instances of problem B. As long as one can exhibit the transformation, one can claim the existence of a reduction, even if one has no idea how one might solve problem B (or even, as in this case, one knows that problem B isn't solvable).  Tim Chow tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. Galileo, Dialogues Concerning Two New Sciences

