```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 saythat 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 anyreason to leap from one conjecture to the other.   (I'm not saying your suggestion is wrong; I'm just saying it doesn'tseem justified by logical reasoning.)-Arthur
```