Relations Among Complexity Measures
Document Type
Article
Department
Mathematics (HMC)
Publication Date
1979
Abstract
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).
Rights Information
© 1979 Association for Computing Machinery
Terms of Use & License Information
DOI
10.1145/322123.322138
Recommended Citation
Pippenger, N, Fischer, M.J. "Relations among Complexity Measures", J. ACM, 26 (1979), 361-381. doi: 10.1145/322123.322138
