
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 5:13 PM


On Thu, 27 Oct 2005, Randy wrote: > Joe Hendrix 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.
(Tangent: According to my lexicon, if a method doesn't terminate, it's not an "algorithm." Algorithms terminate in finite time, which is why they're so useful. :) Replace "algorithm" with "method" or "procedure" in your sentence, and I agree completely.)
> 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.
Exactly!
> 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)?
Yes, you are. /Algorithms/ have asymptotic complexity. /Problems/ do not. Now, it's often[1] possible to talk about the /best possible/ algorithm to solve a given problem, and then talk about that algorithm's theta complexity, which is what you're wanting to do. But in the kind of computer science we're talking about, it's hardly ever obvious whether you've found the /best possible/ algorithm  and if you haven't, then it's no use talking about its complexity.
Example: Suppose the problem is "sort a list of integers." What is the complexity of this problem? Alice thinks, "Aha! Sorting the list requires comparing each pair of elements, so the complexity of the problem is O(n^2)." Alice is WRONG. Bob thinks, "Aha! Shellsort is an algorithm that sorts a list in something like O(n^1.5) time, so the problem is about O(n^1.5)." Bob is right about the complexity of Shell sort, but WRONG about the complexity of the underlying problem. Shell sort is simply not the best possible algorithm for the problem. The RIGHT answer is O(n lg n), and it takes a surprising amount of math to prove that. Just imagine how much math it might take to prove the complexity of a problem that's actually hard!
> 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
This is the flaw in your line of argument  problems don't /have/ runtime. /Algorithms/ have runtime. (A second problem is that I can make the worstcase runtime as bad as I want, just by picking a really stupid algorithm to solve the problem.)
By the way, many people have mentioned the existence of problems in EXP but not in NP, but I don't think anyone's given an example yet. Here's a trivial example: Given an integer N, print out all the integers between 1 and 2**N. That problem isn't in NP, because solutions can't be verified in polytime  it takes O(2**N) time just to read the solution in!
HTH, Arthur
[1]  I'm fairly sure there exist classes of problems with no "best" solution, but merely an infinite family of solutions each of which is better than the last. I don't have any examples, but I'd be interested to see one.

