About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
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 onedimensional 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-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.