A Time-Space Trade-Off

A problem with a demonstrable time-space trade-off is exhibited. The problem is to compile a straight-line program for a certain uninterpreted expression; time is reckoned as the number of instructions in the program,. space as the number of registers referred to. There are programs using linear space and linear time, but any program using less than linear space uses more than linear time