
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 9:16 PM


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 > interreducible 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 NPComplete, 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

