Randy wrote: > 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...)
Perhaps it is also because they are smart enough to realize its importance. Complexity theory is a big field, and one could get a lot of fame as a researcher by finding a solid line of reasoning that it is irrelevant. I personally think that there is too much of a focus on worst-case running time at the undergraduate level, but admitadly other types of analysis are usually even harder to do correctly.
> Maybe that was because it's just too much trouble > to ask others to prove their algorithms to be NPC (or NP-Hard)
This suggests you still don't understand what NP complete and NP hard mean. Algorithms are not NP complete, problems are. Algorithms may have a polynomial time running time, an exponential time, or something even worse. A good algorithm doesn't even have to always terminate to be useful -- Knuth-Bendix completion is a good example of an important algorithm that does not.
> 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.
Well, I am not in theory and find NP completeness useful. I don't know what you mean by informal algorithmists though. A computer science algorithm is by definition a formal entity. How do you expect a machine to execute an informal algorithm? In my experience in automated reasoning, NP completeness is a good result to achieve, since it suggests that techniques like SAT solving or linear arithmetic decision procedures may be able to efficiently solve problems in practice. Higher complexity classes usually require more exhaustive search.
This discussion might make since if you were talking about some exotic class perhaps involving machines with oracles, but NP completeness is a very basic concept.