On Pointers versus Addresses (Extended Abstract)

The problem of determining the cost of random-access memory (RAM) is addressed by studying the simulation of random addressing by a machine which lacks it, called a pointer machine. The model allows the use of a data type of choice. A RAM program of time t and space s can be simulated in O(t log s) time using a tree. However, this is not an obvious lower bound since a high-level data type can allow the data to be encoded in a more economical way. The major contribution is the formalization of incompressibility for general data types. The definition extends a similar property of strings that underlies the theory of Kolmogorov complexity. The main theorem states that for all incompressible data types an Omega (t log s) lower bound holds. Incompressibility is proved for the real numbers with a set of primitives which includes all functions which are continuously differentiable except on a countable closed set. >

Authors

• Amir M. Ben-Amram
• Zvi Galil

Keywords

• Read-write memory
• Costs
• Random access memory
• Upper bound
• Algorithm design and analysis
• Programming profession
• Power generation economics
• Arithmetic
• Computational modeling
• Time measurement
• Lower Bound
• Computational Model
• Decision Tree
• Set Of Functions
• Proof Of Theorem
• Incompressible
• Directed Graph
• Boolean Operators
• Open Set
• Random Access
• Model Definition
• Binary Tree
• Boundary Of Set
• Left Shift
• General Integration
• Floor Function
• Implicit Function Theorem
• Online Problem
• Closed Set