Date: Oct 27, 2005 5:13 PM
Author: Arthur J. O'Dwyer
Subject: Re: On NP Completeness and Intractability

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


> 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
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! Shell-sort 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 worst-case 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!


[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.