0
$\begingroup$

Possible Duplicate:
Are runtime bounds in P decidable? (answer: no)

Originally asked on SO: https://stackoverflow.com/questions/13371025

I have seen many questions asking if this computation is possible, but they all ask about writing a program to compute the complexity of arbitrary algorithms (which is obviously undecideable). I am willing to make the following restrictions on the input:

The algorithm terminates The algorithm is purely functional

The question is, can a program be written to compute the time complexity of such an algorithm through static analysis? If the input algorithm does not terminate, the program behaviour is undefined (it may crash, return a lie, or fail to terminate).

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This is already answered here. I am going to close this as a duplicate since that seems to answer your question. $\endgroup$
    – Kaveh
    Jan 4, 2013 at 21:58
  • $\begingroup$ Your question is a little bit vague since you don't explain what is a "reasonable" bound, however a similar argument would show that the problem is undecidable for any definition I can think of. The restrictions won't matter as long as the class of programs you are considering is capable of syntactically checking if a given string is a terminating computation of a given Turing machine on blank tape (which is a very simple task that any reasonable class of program would be expected to perform unless it is a really very restricted class), $\endgroup$
    – Kaveh
    Jan 4, 2013 at 22:04
  • 2
    $\begingroup$ the undecidability comes from the universal quantifier in the $O$, i.e. the bound needs to hold for all inputs and that cannot be observed with any finite amount of computation (by an argument similar to Rice's theorem the only way of checking such properties is to simulate the machine and we need to simulate the machine on infinitely many inputs). $\endgroup$
    – Kaveh
    Jan 4, 2013 at 22:06
  • $\begingroup$ @Kaveh thanks! I should have asked over here in the first place :) $\endgroup$
    – singpolyma
    Jan 4, 2013 at 22:16

0

Reset to default

Browse other questions tagged or ask your own question.