Randy
Posts:
19
Registered:
12/13/04


Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 4:37 PM


Joe Hendrix wrote: > Randy wrote: ... > > 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  KnuthBendix completion is a good example of an important > algorithm that does not.
Is the issue here one of solution space vs problem space, algorithm vs problem description, thereby necessitating and justifying the need for dissimilar KINDS of complexity? If so, that explains a lot. In essence, CC exists because it's meaningless to equate complexity measures in the problem and solution space. Which is what I've been doing, unsuccessfully.
... > > 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)?
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? CC's departure from traditional complexity analysis doesn't seem like it adds that much value, especially in "the real world" where theta's constants and exponents really do matter.
> > 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.
OK, presuming that the goal of CC is NOT to assess problems rather than solutions, the value of showing membership in NP as opposed to just identifying worst case complexity is something that still don't appreciate. If so, I'll willingly admit that the failure is mine.
Randy
 Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

