<p>As the title says, how are lower bounds for computational complexity proved?  I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound. </p>

<p>General-level explanations and proofs are both welcome. I assume that proofs can be very different for different classes of problems, but I'm looking for just few examples to have a good grab on the basics.</p>

CC BY-SA 3.0
2013-07-15T02:30:23.033Z
Taken at face value, this is an **excellent** research-level question! For almost any interesting problem, the correct answer is **Nobody has a clue.**
Jeffε
CC BY-SA 3.0
2013-07-15T03:45:21.913Z
Not pretending to be speaking for Mr. Ryan Williams, but didn't he have a nice lower bounds proof a couple of years ago?
William Hird
CC BY-SA 3.0
2013-07-15T06:42:28.850Z
It doesn't seem that you have the required basic background knowledge in this topic. Please note that the target community of cstheory is professional researchers in theoretical computer science and as such we expect people asking questions here to know at least the basics of the area of their question. If you are not familiar with the basics of this area then please consider posting on [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-07-17T19:50:10.890Z
O(n) to read an input in a serial fashion. O(nlogn) to sort in the comparison model since this is the height of the decision tree. Regan has a nice survey paper: http://www.cse.buffalo.edu/~regan/papers/pdf/Super.pdf
Chad Brewbaker
CC BY-SA 3.0
2013-07-19T16:29:25.477Z
Once you have a few base questions with known lower bounds, you can use reductions with a given complexity to prove that another problem has a certain bound.
Joey Eremondi
CC BY-SA 3.0
2013-07-19T21:49:07.370Z
@jmite: What do you mean by "a few base questions with known lower bounds? Some kind of structures? (geometry).
William Hird
CC BY-SA 3.0
2013-07-19T22:01:47.017Z
No, I'm talking about things like sorting, which we know to be $\Omega(n \log n)$. Or how some problems are known to be EXPTIME-complete. If you can show that your algorithm reduces to sorting, then you know that it can't be any faster than $O(n \log n)$.
Joey Eremondi
CC BY-SA 3.0
2013-07-19T22:08:48.530Z
I recommend migration to CS.SE
Joey Eremondi
CC BY-SA 3.0
2013-07-22T14:19:10.127Z
I'm not sure if CS.SE is the right place either, as JeffE points out, this is, at face value, a hard question. It would be more appropriate here if it were, say, asking for a *survey of known lower bounds (or techniques)*.
Joshua Grochow
<time-complexity>
How are lower bounds for computational complexity proved?
dude
# How are lower bounds for computational complexity proved?

(Asked by: username_0 on 2013-07-14)

As the title says, how are lower bounds for computational complexity proved? I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound.

General-level explanations and proofs are both welcome. I assume that proofs can be very different for different classes of problems, but I'm looking for just few examples to have a good grab on the basics.

**Tags:** time-complexity

> **Comments:**
> **username_1**: Taken at face value, this is an **excellent** research-level question! For almost any interesting problem, the correct answer is **Nobody has a clue.**  
> **username_2**: Not pretending to be speaking for Mr. Ryan Williams, but didn't he have a nice lower bounds proof a couple of years ago?  
> **username_3**: It doesn't seem that you have the required basic background knowledge in this topic. Please note that the target community of cstheory is professional researchers in theoretical computer science and as such we expect people asking questions here to know at least the basics of the area of their question. If you are not familiar with the basics of this area then please consider posting on [cs.se] which has a broader scope.  
> **username_4**: O(n) to read an input in a serial fashion. O(nlogn) to sort in the comparison model since this is the height of the decision tree. Regan has a nice survey paper: http://www.cse.buffalo.edu/~regan/papers/pdf/Super.pdf  
> **username_5**: Once you have a few base questions with known lower bounds, you can use reductions with a given complexity to prove that another problem has a certain bound.  
> **username_2**: @jmite: What do you mean by "a few base questions with known lower bounds? Some kind of structures? (geometry).  
> **username_5**: No, I'm talking about things like sorting, which we know to be $\Omega(n \log n)$. Or how some problems are known to be EXPTIME-complete. If you can show that your algorithm reduces to sorting, then you know that it can't be any faster than $O(n \log n)$.  
> **username_5**: I recommend migration to CS.SE  
> **username_6**: I'm not sure if CS.SE is the right place either, as JeffE points out, this is, at face value, a hard question. It would be more appropriate here if it were, say, asking for a *survey of known lower bounds (or techniques)*.  

---

## 0 answers

