Linear speed-up does not hold on Turing machines with tree storages (Q688445): Difference between revisions

One of the basic results in computational complexity is the linear speed- up theorem by \textit{J. Hartmanis} and \textit{R. E. Stearns} [Trans. AMS 117, 285-306 (1965; Zbl 0131.154)]: On Turing machines accessing tapes as storage constant factors in the computation time are not significant, since any computation can be increased in speed by any constant factor. In this paper Turing machines accessing storage devices with a tree-like structure are studied. It is shown that on tree storage machines constant factors are significant. For any \(k\), power of two, there is a modification of the Storage-Retrieval Problem which can be solved in time \(kn\) on a machine with two binary tree storages. On the other hand, any binary tree storage machine (even if it is equipped with more storages) requires time \(kn-O(n/ \log n)\) to solve this problem.