Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

On the Time and Space Complexity of Computation Using Write-Once Memory - OR - Is Pen Really Much Worse Than Pencil?

Sandy Irani, Moni Naor and Ronitt Rubinfeld

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-434
June 1988

http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-434.pdf

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 (such as logarithmic or n^alpha for alpha < 1, where n is the size of the problem) of regular memory, and a polynomial amount of write-once 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. The space requirements of algorithms running on the write-once model are studied. We show that general simulations of algorithms originally running on a RAM with regular memory by algorithms running on our write-once memory model require space proportional to the number of steps simulated. In order to study the space complexity further, we define an analogue of the pebbling game, called the pebble-sticker game. A sticker is different from a pebble in that it cannot be removed once placed on a node of the computation graph. As placing pebbles correspond to writes to regular memory, placing stickers correspond to writes to the write-once memory. Bounds are shown on pebble-sticker tradeoffs required to evaluate trees and planar graphs. Finally, we define the complexity class WO-PSPACE as the class of problems which can be solved with a polynomial amount of write-once memory, and show that it is equal to P.


BibTeX citation:

@techreport{Irani:CSD-88-434,
    Author = {Irani, Sandy and Naor, Moni and Rubinfeld, Ronitt},
    Title = {On the Time and Space Complexity of Computation Using Write-Once Memory - OR - Is Pen Really Much Worse Than Pencil?},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1988},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6043.html},
    Number = {UCB/CSD-88-434},
    Abstract = {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 (such as logarithmic or <i>n^alpha</i> for <i>alpha</i> < 1, where <i>n</i> is the size of the problem) of regular memory, and a polynomial amount of write-once 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. The space requirements of algorithms running on the write-once model are studied. We show that general simulations of algorithms originally running on a RAM with regular memory by algorithms running on our write-once memory model require space proportional to the number of steps simulated. In order to study the space complexity further, we define an analogue of the pebbling game, called the pebble-sticker game. A sticker is different from a pebble in that it cannot be removed once placed on a node of the computation graph. As placing pebbles correspond to writes to regular memory, placing stickers correspond to writes to the write-once memory. Bounds are shown on pebble-sticker tradeoffs required to evaluate trees and planar graphs. Finally, we define the complexity class WO-PSPACE as the class of problems which can be solved with a polynomial amount of write-once memory, and show that it is equal to P.}
}

EndNote citation:

%0 Report
%A Irani, Sandy
%A Naor, Moni
%A Rubinfeld, Ronitt
%T On the Time and Space Complexity of Computation Using Write-Once Memory - OR - Is Pen Really Much Worse Than Pencil?
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-434
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6043.html
%F Irani:CSD-88-434