|
Re: On NP Completeness and Intractability
Posted:
Oct 26, 2005 6:34 PM
|
|
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. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however 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
|
|