|
|
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
|
|
