Relations Among Complexity Measures

Various computational models (such as machines and combinational logic networks) induce various and, in general, different computational complexity measures. Relations among these measures are established by studying the ways in which one model can simulate another. It is shown that a machine with k-dimensional storage tapes (respectively, with tree-structured storage media) can be simulated on-line by a machine with one-dimensional storage tapes in time O(n^2-1/k) (respectively, in time O(n²/log n)). An oblivious machine is defined to be one whose head positions, as functions of time, are independent of the input, and it is shown that any machine with one-dimensional tapes can be simulated on-line by an oblivious machine with two one-dimensional tapes in time O(n log n). All of these results are the best possible, at least insofar as on-line simulation is concerned. By similar methods it is shown that n steps of the computation of an arbitrary machine with one-dimensional tapes can be performed by a combinational logic network of cost O(n log n) and delay O(n)