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