In comp.theory Randy <email@example.com> wrote: > Joe Hendrix wrote: > ... >> >> 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.
> I won't dispute that finding a problem to be NPC has value. But simply > quantifying its theta asymptotic complexity would seem to be equally > valuable, seemingly more so, and without the added burden of proving > that the problem's in NP.
> Or am I still confusing apples (problems) with oranges (solutions)?
You are still confusing problems and solutions. How do you quantify the theta asymptotic complexity of a problem? Remember, a problem is not an algorithm, and just because you have an algorithm that solves a particular problem it does not mean that a better algorithm does not exist.
> In other words, isn't proving NPC overkill if all you want to do is > characterize a problem? Wouldn't it be equally effective to identify a > problem's worst case runtime and then choose among known techniques that > efficiently solve problems with equal worst case (or theta) complexity?
How do you identify a problem's worst case runtime?