On the Time and Space Complexity of Computation Using Write-Once Memory

On the Time and Space Complexity of Computation Using Write-Once Memory

Abstract— On the Time and Space Complexity of Computation Using Write-Once Memory. We introduce a model of computation based on the use of write-once memory. Write-once memory has the property that bits may be set but not reset. Our model consists of a RAM with a small amount of regular memory (such as logarithmic or n=for ~ < 1, where n is the size of the problem) and a polynomial amount of write-once < Final Year Projects 2016 > memory. Bounds are given on the time required to simulate on write-once memory algorithms which originally run on a RAM with a polynomial amount of regular memory. We attempt to characterize algorithms that can be simulated on our write-once memory model with very little slow-down. A persistent computation is one in which, at all times, the memory state of the computation at any previous point in time can be reconstructed. We show that any data structure or computation implemented on this write-once memory model can be made persistent without sacrificing much in the way of running time or space.