The Garland Measure and Computational Complexity of Stack Programs

AbstractA key problem in implicit computational complexity is to analyse the impact on program run times of nesting restricted control structures, such as for-do statements in imperative languages. This problem has two aspects. One is whether there are methods of extracting information from the syntax of such programs that give insight as to why some nesting of control structures may cause a blow up in complexity, e.g. from polynomial to (iterated) exponential time, while others do not. Bearing in mind that there are limitations to any such method, the other is whether a given method is “optimal” in the sense that it provides a full understanding of the mechanisms that cause and control the complexity of computations.This paper presents a graph theoretical analysis of control in stack programs, called “garland measure”. It is shown that (1) stack programs of garland measure n compute exactly those functions computed by a Turing machine whose running time (as a function of input size) lies in Grzegorczyk class En+2. In particular, stack programs of garland measure 0 compute precisely the polynomial-time computable functions.Furthermore, it is shown that the garland measure is “optimal” in the sense that no other measure on stack programs satisfying (1) can admit more algorithms at any level when restricting to “core programs” that comprise those stack manipulations which cause and control computational complexity