Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Randy Posts: 19 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 7:32 PM

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.
> Now, it's often[1] possible to talk about the /best possible/ algorithm
> to solve a given problem, and then talk about that algorithm's theta
> complexity, which is what you're wanting to do. But in the kind of
> computer science we're talking about, it's hardly ever obvious whether
> you've found the /best possible/ algorithm --- and if you haven't, then
> it's no use talking about its complexity.
>
> Example: Suppose the problem is "sort a list of integers." What is the
> complexity of this problem?
> Alice thinks, "Aha! Sorting the list requires comparing each pair of
> elements, so the complexity of the problem is O(n^2)." Alice is WRONG.
> Bob thinks, "Aha! Shell-sort is an algorithm that sorts a list in
> something like O(n^1.5) time, so the problem is about O(n^1.5)."
> Bob is right about the complexity of Shell sort, but WRONG about the
> complexity of the underlying problem. Shell sort is simply not the
> best possible algorithm for the problem.
> The RIGHT answer is O(n lg n), and it takes a surprising amount of
> math to prove that. Just imagine how much math it might take to prove
> the complexity of a problem that's actually hard!

Right. That example had occurred to me. It's odd that I never before
appreciated the sorting *problem's* NlgN lower bound as an expression of
computational complexity, nor that it was a different kettle of fish
than all sorting *algorithms'* best case NlgN asymptotic complexity.

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

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

...
>
> By the way, many people have mentioned the existence of problems in EXP
> but not in NP, but I don't think anyone's given an example yet. Here's a
> trivial example: Given an integer N, print out all the integers between
> 1 and 2**N. That problem isn't in NP, because solutions can't be verified
> in polytime --- it takes O(2**N) time just to read the solution in!
>
> HTH,
> -Arthur
>
> [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?

Randy

--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

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