5

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.

Jeffε
  • 23,129
  • 10
  • 96
  • 163
dude
  • 79
  • 1
  • 7
    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ε Jul 15 '13 at 02:30
  • 1
    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 Jul 15 '13 at 03:45
  • 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 Jul 15 '13 at 06:42
  • 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 Jul 17 '13 at 19:50
  • 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 Jul 19 '13 at 16:29
  • @jmite: What do you mean by "a few base questions with known lower bounds? Some kind of structures? (geometry). – William Hird Jul 19 '13 at 21:49
  • 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 Jul 19 '13 at 22:01
  • 1
    I recommend migration to CS.SE – Joey Eremondi Jul 19 '13 at 22:08
  • 1
    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 Jul 22 '13 at 14:19

0 Answers0