Joe Hendrix wrote: > 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.
Perhaps that's because it doesn't serve them to make the argument. Why pick fights that aren't worth the trouble? (I'm certainly sympathetic to this argument at the moment...)
As it happens, I've seen several AI professors over the years try to integrate CC into practical domains, in an attempt to give depth and perspective to their technique or philosophy. Invariably, though, the effort ended quickly. Maybe that was because it's just too much trouble to ask others to prove their algorithms to be NPC (or NP-Hard) in order to justify employing their novel approach. Or maybe the NP formality really didn't add value.
I'd be interested to know some examples of CS non theorists (e.g. informal algorithmists) who have found formal NP (as opposed to simple algorithmic complexity) valuable other than to imply exponentiality or infeasibility. With each mention of NP or NPC in the various research papers I've read, I have never seen subsequent statements grounding the implications of the problem as being specifically and formally NP-Hard or NPC, beyond merely being exponential or infeasible or unpredictable.
I think this implies: 1) even most non-theory CS academics don't find formal CC to be necessary in grounding their work, and 2) in using the term NPC or NP-Hard, instead of using "infeasible" or "exponential", and then *not* explaining why the former has greater implications than the latter, it seems likely to me that a lot of academics don't appreciate the necessity of CC either.
Or maybe it's just time for me to get out of Dodge...