firstname.lastname@example.org wrote: > In article <email@example.com>, Randy <firstname.lastname@example.org> 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.
I'm going to take your word for that. I guess I'm more doubtful now of the merits of computational complexity (CC) outside of academia. I appreciate the value in characterizing tasks that are in/feasible, as folks in OR have done for eons. But is the subtlety captured by the narrow definition of NP really practically useful or conceptually constructive, beyond the simpler concept of exponential asymptotic complexity and its concomitant infeasibility? If so, I don't see it.
If I've gained anything from this thread, it's a greater feel for the specificity of and a lesser feel for the utility of P vs. NP, and Hard vs. Complete. I'm left with a much stronger sense that CC has less relevance than I thought. If I came to appreciate the inadequacy of exponentiality as compared to NP, that could change. But it seems I don't, and the preceding conversation has left we with less patience or confidence that clarity will ever be forthcoming.