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.

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! 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!

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.