On the Space and Time Complexity of Functions Computable by Simple Programs
Tat-Hung Chan, Óscar H. Ibarra · SIAM Journal on Computing · 1983
We study the space and time complexity of functions computable by simple loop-free programs operating on integers. In particular, we show that any function $f(x_1 , \cdots ,x_k )$ computable by a program using only comparison-based conditional forward branching instructions and the arithmetic operations $ + , - $, and truncating division by integer constants (such programs compute exactly the functions definable in Presburger arithmetic) can be computed by an off-line Turing machine in space $s(n)$ and time $n^2 /s(n)$ for any reasonable space bound $s(n)$ between $\log n$ and n. Moreover, the space-time trade-off is optimal.