Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Randy Posts: 19 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 26, 2005 7:24 PM

tchow@lsa.umich.edu wrote:
> In article <djm7hh\$qhb\$1@joe.rice.edu>, Randy <joe@burgershack.com> wrote:
>

>>It's no surprise to me. IMHO, its because of its abstract terminology
>>(and the consequential confusion among non-theorists) that complexity
>>theory is almost entirely ignored by the professional CS community.
>>IMHO, this is because: 1) it's poorly explained by those who understand
>>it, and 2) it's deemed irrelevant by just about everyone, including many
>>who understand it better than I.

>
>
> Poor explanations and other human failings aside, a large part of the
> reason that complexity theory is ignored by "practitioners" is that
> practitioners are usually interested in positive results (i.e., algorithms)
> and not in negative results (i.e., nonexistence of algorithms). I don't
> see that this is necessarily "a shame"; it's just a matter of what you're
> interested in.
>
> However, I don't think that it's quite true to say that all of complexity
> theory is irrelevant to those who are interested only in algorithms. I
> don't think that any practitioner can afford to be completely ignorant of
> the concept of NP-completeness. Knowing whether a problem is NP-complete
> provides extremely valuable guidance in choosing an algorithmic approach
> to it.

I'm going to take your word for that. I guess I'm more doubtful now of
the merits of computational complexity (CC) outside of academia. I
appreciate the value in characterizing tasks that are in/feasible, as
folks in OR have done for eons. But is the subtlety captured by the
narrow definition of NP really practically useful or conceptually
constructive, beyond the simpler concept of exponential asymptotic
complexity and its concomitant infeasibility? If so, I don't see it.

If I've gained anything from this thread, it's a greater feel for the
specificity of and a lesser feel for the utility of P vs. NP, and Hard
vs. Complete. I'm left with a much stronger sense that CC has less
relevance than I thought. If I came to appreciate the inadequacy of
exponentiality as compared to NP, that could change. But it seems I
don't, and the preceding conversation has left we with less patience or
confidence that clarity will ever be forthcoming.

Randy

--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

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