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).

$\endgroup$

marked as duplicate by Kaveh Jan 5 '13 at 1:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 '13 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 '13 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 '13 at 22:06
  • $\begingroup$ @Kaveh thanks! I should have asked over here in the first place :) $\endgroup$ – singpolyma Jan 4 '13 at 22:16

Browse other questions tagged or ask your own question.