Relations Among Complexity Measures

Abstract

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 one- dimensional storage tapes m time O(n 2-ilk) (respectively, m time O(n2/log n)) An obhv:ous 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-d~menslonal 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 one- dimensional tapes can be performed by a combinational logic network of cost O(n log n) and delay O(n)