Randy 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.
I'm pretty skeptical of your claim that complexity theory is ignored by almost the entire professional CS community. Certainly, many programmers can get by without understanding it, but the same thing is true for anything -- most programmers can get by without knowing C++.
NP completeness is a very basic property. I'd be hard pressed to name any big names in computer science that would deem NP completeness and basic complexity theory irrelevant.