Is it really possible to prove lower bounds?

Problem Detail: 

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use for the proof, but given that, do we really prove a lower bound then in general? What I means is that can we prove something like "problem $X$ cannot be solved faster than $t(X)$ time" rather than "problem $X$ can be solved in $t(X)$ time or faster"?

I have tried to find information specifically on lower bounds and proofs of them, but I can't really find any of interest, any recommendations on books/papers/websites on the subject?

Asked By : hsalin

Answered By : Tom van der Zanden

We can absolutely prove such things.

Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the algorithm on some input, we could observe that it never examined a particular element of the input. Changing that element to the minimum, we can get the algorithm to fail.

A less trivial lower bound is the $\Omega(n \log n)$ lower bound for sorting in the comparison-based model. The proof for that goes along the following lines: given an input of $n$ numbers, there are $n!$ possible outputs (the input could be any permutation of the sorted list, so the output can also be any permutation of the input). If we are limited to only doing comparisons, then our algorithm (on average) needs to perform at least $\log_2(n!)=\Omega(n \log n)$ comparisons in order to be able to give $n!$ different outputs.

Lower bounds can be even stronger. There are several problems (notably the $EXPTIME$-hard problems) for which there is an exponential lower bound. Problems in this class include computing optimal strategies for games such as (generalized) chess, checkers and go. The proof of this is via the Time Hierarchy Theorem, which states (subject to some restrictions on $f$):

Given a function $f$, there exists a computational problem that can be solved in time $O(f(n))$ but can not be solved in time $o(\frac{f(n)}{\log n})$.

So basically, if you can think of a function $f$ there exists a problem that requires that much time to solve.

Finally, another avenue of not necessarily proving a time lower bound but something even stronger is showing the undecidability of a problem (e.g. halting, post correspondence).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38357