Linear speed-up does not hold on Turing machines with tree storages
From MaRDI portal
Publication:688445
DOI10.1016/0020-0190(93)90078-NzbMath0788.68060MaRDI QIDQ688445
Publication date: 20 December 1993
Published in: Information Processing Letters (Search for Journal in Brave)
computational complexity; Turing machines; Kolmogorov complexity; lower bounds; speed-up; online simulation; tree storage
68Q25: Analysis of algorithms and problem complexity
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing access pointers into trees and arrays
- On time versus space. II
- A fast implementation of a multidimensional storage into a tree storage
- Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
- Optimal Dynamic Embedding of Trees into Arrays
- Optimal On-Line Simulations of Tree Machines by Random Access Machines
- Relations Among Complexity Measures
- On the Computational Complexity of Algorithms
- Boolean Memories
- On the Minimum Computation Time of Functions