[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Usually in AlgorithmAnalysis we are looking for upper bounds on cost, as in "Algorithm X solves problem Y in no more than O(n22/7) time in the worst case." Upper bounds are useful when we want to advertise that our algorithm is good. But what if we want to argue that no other algorithm can be better, or perhaps that some problem is so hard that we can't possibly hope to find a good solution to it?

For this we need a lower bound. Lower bounds come in two flavors:

1. Information-theoretic lower bounds

2. Lower bounds by reduction

Suppose we already have a lower bound S(n) on some problem A, and that there is a reduction from A to some other problem B. Formally, a reduction is a function f such that A(x) = B(f(x)). Let Tf(n) be an upper bound on the time to compute f(x) when |x| = n, and let TB(n) be an upper bound on the time to compute B(x) when |x| = n. Then computing A(x) as B(f(x)) with |x| = n takes time at most Tf(n) + TB(Tf(n)). (The odd second term comes from the fact that Tf(n) is an upper bound on the length of the output of f(x); note that we are also assuming here that TB is nondecreasing.)

An important special case of this is when Tf = O(nc) and TB = O(nd) for some c and d. Then Tf(n) + Tf(TB(n)) = O(nc) + O(ncd) = O(ncd). In words:

How do we get lower bounds out of this? Since S(n) ≤ Tf(n) + Tf(TB(n)), we have TB(n) ≥ Tf-1(S(n) - Tf(n)). For example:

3. Can we prove interesting lower bounds?

Lower bounds on problems are the really interesting results, since those are the ones that say that the problem is too hard instead of saying that we are too dumb to come up with a better algorithm. But we aren't very good at proving them; in fact, the comparison-based sorting lower bound is about the only non-trivial lower bound we've got for a traditional algorithmic problem. The difficulty is that it is very hard to write a lower bound proof that covers all possible algorithms, including the ones no one has thought of yet---algorithms are slippery and clever, and there are a lot of them.

So instead we fall back to classifying problems by how hard they appear to be relative to other problems. This classification task is the core of ComputationalComplexityTheory. For many such classes of problems we cannot prove that all the problems in some class are hard, but we can prove that each is hard if and only if all the others are (for an appropriate definition of "hard"). This is not quite as good as a real lower bound, but appears to be the best we can do so far.


2014-06-17 11:58