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

