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 -- Knuth-Bendix 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
|
|
