Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

 Messages: [ Previous | Next ]
 stephen@nomail.com Posts: 1,744 Registered: 12/13/04
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 counter-intuitive
>>> 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
NP-completeness, 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

Date Subject Author
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 Dr. David Kirkby
10/25/05 ianparker2@gmail.com
10/25/05 Pubkeybreaker
10/25/05 osmium
10/25/05 Pubkeybreaker
10/25/05 Willem
10/25/05 Bryan Olson
10/25/05 Willem
10/25/05 Ed Prochak
10/25/05 Dr. David Kirkby
10/25/05 Gene
10/25/05 MartDowd
10/25/05 RobertSzefler
10/25/05 Dr. David Kirkby
10/25/05 Pubkeybreaker
10/25/05 Wim Benthem
10/26/05 RobertSzefler
10/25/05 KP Bhat
10/25/05 stephen@nomail.com
10/25/05 tchow@lsa.umich.edu
10/25/05 googmeister@gmail.com
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/27/05 stephen@nomail.com
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 C6L1V@shaw.ca
10/25/05 stephen@nomail.com
10/25/05 Wim Benthem
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/26/05 Randy
10/27/05 Arthur J. O'Dwyer
10/27/05 Randy
10/27/05 Willem
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 tchow@lsa.umich.edu
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Arthur J. O'Dwyer
10/27/05 googmeister@gmail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 Arthur J. O'Dwyer
10/28/05 Joe Hendrix
10/28/05 Ben Rudiak-Gould
10/28/05 Bryan Olson
10/28/05 Pekka Orponen
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/25/05 tchow@lsa.umich.edu
10/25/05 Michael J. Hennebry
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/25/05 Willem
10/25/05 Arthur J. O'Dwyer
10/25/05 googmeister@gmail.com
10/31/05 Oliver Wong
10/31/05 Robert Israel
11/1/05 Willem
11/1/05 googmeister@gmail.com
11/1/05 Willem
11/1/05 Torkel Franzen
11/1/05 googmeister@gmail.com
11/1/05 Oliver Wong
11/1/05 Willem
11/1/05 Robert Israel
10/26/05 Randy
10/26/05 stephen@nomail.com
10/26/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/25/05 Pat Farrell
10/25/05 Bryan Olson