5
$\begingroup$

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.

$\endgroup$

closed as off-topic by Aaron Roth, Robin Kothari, Mohammad Al-Turkistany, Kaveh Jul 15 '13 at 6:41

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ Taken at face value, this is an excellent research-level question! For almost any interesting problem, the correct answer is Nobody has a clue. $\endgroup$ – Jeffε Jul 15 '13 at 2:30
  • 1
    $\begingroup$ Not pretending to be speaking for Mr. Ryan Williams, but didn't he have a nice lower bounds proof a couple of years ago? $\endgroup$ – William Hird Jul 15 '13 at 3:45
  • $\begingroup$ 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 Computer Science which has a broader scope. $\endgroup$ – Kaveh Jul 15 '13 at 6:42
  • 1
    $\begingroup$ I recommend migration to CS.SE $\endgroup$ – jmite Jul 19 '13 at 22:08
  • 1
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow Jul 22 '13 at 14:19

Browse other questions tagged or ask your own question.