
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 12:38 AM


In comp.theory tchow@lsa.umich.edu wrote: > 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.
Perhaps, but the whole reason we are interested in polynomial reducibility is because of the fact that if A is polynomially reducible to B, and if there exists a polynomial time solution to B, then A also has a polynomial time solution.
I rarely see unsolvable problems discussed in the context of NPcompleteness, maybe because it does not make much sense to talk about the time complexity of unsolvable problems.
> 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).
But you do not want to forget why the reductions are useful in the first place. You can construct all sorts of reductions that just map one instance to another. I could look at linear reductions for example, which transform one instance to another in linear time. But what does this reduction mean? If I find a linear reduction from A to B, what have I learned about A and B?
Stephen

