Multiplication, division, and shift instructions in parallel random access machines

AbstractWe prove that polynomial time on a parallel random access machine (PRAM) with unit-cost multiplication and division or on a PRAM with unit-cost shifts is equivalent to polynomial space on a Turing machine (PSPACE). This extends the result that polynomial time on a basic PRAM is equivalent to PSPACE to hold when the PRAM is allowed multiplication or division or unrestricted shifts. It also extends to the PRAM the results that polynomial time on a random access machine (RAM) with multiplication is equivalent to PSPACE and that polynomial time on a RAM with shifts (that is, a vector machine) is equivalent to PSPACE. We obtain simulations of uniform circuits by RAMs with enhanced instruction sets and use the enhanced RAMs to simulate PRAMs with enhanced instruction sets