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

On Thu, 27 Oct 2005, Randy wrote:

> Arthur J. O'Dwyer wrote:

>> On Thu, 27 Oct 2005, Randy wrote:

> ...

>>> Or am I still confusing apples (problems) with oranges (solutions)?

>>

>> Yes, you are. /Algorithms/ have asymptotic complexity. /Problems/ do

>> not.

[...]

> So if I may summarize (boy, do I know how to court danger), the value of

> CC seems to lie in:

>

> 1) identifying a problem's theoretical omega (lower bound) in the

> solution space (like sorting's NlgN), and

I guess. Of course, you can do that without the labels "P" and "NP".

> 2) characterizing classes of problems as being computationally

> equivalent (polynomially equivalent?), which is useful because:

>

> 3) when problems A and B are in the same CC class, both are

> inter-reducible polynomially, therefore problem A can be solved using

> problem B's algorithm, at no worse than a polynomially greater runtime

> cost. (We know that B's algorithm is "feasibly" powerful enough to

> solve either problem).

Close. If A and B are both in P, we can't say much of anything about

relationships between A and B. Ditto if A and B are both in NP. /But.../

If A is in NP and B is in NP-Complete, then we can definitively say

that A can be reduced to B, therefore A can be solved using (one of)

B's algorithm(s) at no worse than a polynomially greater runtime.

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

>

> As Tim Chow has suggested, perhaps chess or go?

Tim didn't suggest either of those as problems with no "best" algorithm;

he suggested those as problems (probably) not in NP. I don't see any

reason to leap from one conjecture to the other.

(I'm not saying your suggestion is wrong; I'm just saying it doesn't

seem justified by logical reasoning.)

-Arthur