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