Relations Among Complexity Measures

Various computational models (such as machines and combinational logic networks) induce various and, m general, different computational complexity measures Relations among these measures are established by studying the ways m which one model can “simulate” another It ts shown that a machine with k-dimensional storage tapes (respectively, with tree-structured storage media) can be simulated on-hne by a machine with onedimensional storage tapes m time O(n 2-ilk) (respectively, m time O(n2/log n)) An obhv machine Is defined to be one whose head posmons, as functions of time, are independent of the input, and It Is shown that any machine with one-dmenslonal tapes can be simulated on-hne 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-hne simulation is concerned. By slmdar methods It is shown that n steps of the computation of an arbitrary machine with onedimensional tapes can be performed by a combinational logic network of cost O(n log n) and delay O(n). © 1979, ACM. All rights reserved.