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.

Improve this question
$\endgroup$
9
  • 7
    $\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, 2013 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, 2013 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, 2013 at 6:42
  • 1
    $\begingroup$ I recommend migration to CS.SE $\endgroup$
    – Joey Eremondi
    Jul 19, 2013 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, 2013 at 14:19

0

Reset to default

Browse other questions tagged or ask your own question.