23
$\begingroup$

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.

I can, however, certainly write a program that can compute the running time of a program of like:

for(i=0; i<N; i++)
    { x = 1; }

and return a time complexity of $N$, without ever running it.

For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.

My question is this:

What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?

*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ (1) “The O-notation” does not mean “time complexity.” (2) It is unclear what you mean by “O(infinity).” Please avoid inventing a new notation if possible. (3) Deciding whether a given program halts or not and giving an explicit upper bound on the time complexity of the program is different. $\endgroup$
    – Tsuyoshi Ito
    Sep 12, 2012 at 14:53
  • 1
    $\begingroup$ I am not familiar with inferring time complexity of programs in restricted classes, but one class of programs which may be worth checking for is called “bounded loop programs,” for which it is easy to bound the time complexity. I remember that bounded loop programs are discussed in Chapter 3 of Gems of Theoretical Computer Science by Uwe Schöning and Randall J. Pruim in the context of deciding equivalence of two programs, but I am not sure how much relevant the chapter is to your question. $\endgroup$
    – Tsuyoshi Ito
    Sep 12, 2012 at 15:32
  • 4
    $\begingroup$ I'm a little confused. In what way is this out of scope ? One reasonable answer to the OP's question would be language fragments (or even classes of fragments) for which running time can be determined algorithmically. $\endgroup$
    – Suresh Venkat
    Sep 12, 2012 at 19:14
  • 4
    $\begingroup$ Related question: Are runtime bounds in P decidable? $\endgroup$
    – Artem Kaznatcheev ♦
    Sep 12, 2012 at 22:43
  • 7
    $\begingroup$ I'm terribly late to this comment thread. We seem to pounce the moment a post smells newbie-ish. I'm not pointing fingers. I feel this instinct myself. Maybe we should be gentler. The OP admitted to not being familiar with the area or terms. What's the point of a question-answer site if we only tolerate people who know exactly what they want, and ask it in our language. $\endgroup$
    – Vijay D
    Dec 8, 2012 at 10:08

2 Answers 2

Reset to default
23
$\begingroup$

In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time.

However, much work has been carried out on the effective computation of program complexity. I have particular fondness for Implicit Complexity Theory which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!

One particularly nice example is described in this paper by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in P.

Improve this answer
$\endgroup$
5
  • $\begingroup$ As a side note, also see Epigram, which is a language which can guarantee termination. $\endgroup$
    – Realz Slaw
    Sep 14, 2012 at 20:25
  • $\begingroup$ This is a nice start, but is there more to say? (For example, it seems to me that a given elementary recursive function's runtime must be straightforward to compute, yet such functions can solve any problem in the exponential hierarchy....) $\endgroup$
    – usul
    Dec 8, 2012 at 11:29
  • $\begingroup$ Insofar as it is possible to determine that the input program is written in a restricted language, you can assume the time complexity is bounded by whatever upper bound that language imposes. However, many primitive recursive functions have general recursive equivalents which are more efficient $\endgroup$
    – Chris Pressey
    Dec 8, 2012 at 21:21
  • 1
    $\begingroup$ (accidentally saved that comment early, then exceeded the 5-minute limit. The second sentence should read as follows:) However, programs in these restricted languages may have equivalents in less restricted languages which are more efficient (specifically, many primitive recursive functions have general recursive equivalents which are more efficient) which, in practice, encourages the use of the unrestricted, harder-to-analyze languages. $\endgroup$
    – Chris Pressey
    Dec 8, 2012 at 21:31
  • 1
    $\begingroup$ That's very interesting Chris! Do you have a reference? In fact it seems counter-inutitive: I would have suspected primitive recursive functions can simulate general recursive functions for a given number of steps, which would then limit the speedup to some constant factor. $\endgroup$
    – cody
    Dec 10, 2012 at 23:45
11
$\begingroup$

The question you pose and the specific counting trick you describe is a classic one in program analysis. There is the theoretical problem of complexity analysis, and it's practical manifestation in terms of automatically estimating the performance of a piece of code. Such an automated analysis has several applications from detecting performance bugs to estimating the cost for some computation in the cloud.

Cody pointed out that the problem is undecidable in general. This problem is harder than proving termination, because obtaining a complexity bound entails that the program also terminates. There are two approaches to such a problem. One is from program analysis. The idea of adding a counter and estimating its value exists since the 70s. This encoding reduces the problem of determining running time to that of computing an invariant.

A second approach is to design a programming language that only admits programs of a certain bounded complexity. This is the area of implicit computational complexity.

Some references for both areas follow.

  1. The SPEED Project, is one specific line of program analysis work that focuses on how to find bounds on counters once introduced into the program. The counters may measure time or space consumption.
  2. Multivariate amortized resource analysis, Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012
  3. On Decidable Growth-Rate Properties of Imperative Programs, Amir Ben Amram, Developments in Implicit Computational complExity 2010. This is a beautiful line of work on bounding complexity of imperative programs by syntactic restrictions.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.