Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

 Messages: [ Previous | Next ]
 Arthur J. O'Dwyer Posts: 91 Registered: 12/13/04
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

Date Subject Author
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 Dr. David Kirkby
10/25/05 ianparker2@gmail.com
10/25/05 Pubkeybreaker
10/25/05 osmium
10/25/05 Pubkeybreaker
10/25/05 Willem
10/25/05 Bryan Olson
10/25/05 Willem
10/25/05 Ed Prochak
10/25/05 Dr. David Kirkby
10/25/05 Gene
10/25/05 MartDowd
10/25/05 RobertSzefler
10/25/05 Dr. David Kirkby
10/25/05 Pubkeybreaker
10/25/05 Wim Benthem
10/26/05 RobertSzefler
10/25/05 KP Bhat
10/25/05 stephen@nomail.com
10/25/05 tchow@lsa.umich.edu
10/25/05 googmeister@gmail.com
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/27/05 stephen@nomail.com
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 C6L1V@shaw.ca
10/25/05 stephen@nomail.com
10/25/05 Wim Benthem
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/26/05 Randy
10/27/05 Arthur J. O'Dwyer
10/27/05 Randy
10/27/05 Willem
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 tchow@lsa.umich.edu
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Arthur J. O'Dwyer
10/27/05 googmeister@gmail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 Arthur J. O'Dwyer
10/28/05 Joe Hendrix
10/28/05 Ben Rudiak-Gould
10/28/05 Bryan Olson
10/28/05 Pekka Orponen
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/25/05 tchow@lsa.umich.edu
10/25/05 Michael J. Hennebry
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/25/05 Willem
10/25/05 Arthur J. O'Dwyer
10/25/05 googmeister@gmail.com
10/31/05 Oliver Wong
10/31/05 Robert Israel
11/1/05 Willem
11/1/05 googmeister@gmail.com
11/1/05 Willem
11/1/05 Torkel Franzen
11/1/05 googmeister@gmail.com
11/1/05 Oliver Wong
11/1/05 Willem
11/1/05 Robert Israel
10/26/05 Randy
10/26/05 stephen@nomail.com
10/26/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/25/05 Pat Farrell
10/25/05 Bryan Olson