On the complexity of RAM with various operation sets

1 January 1992

conference paper
Published by Association for Computing Machinery (ACM)

p. 624-631
https://doi.org/10.1145/129712.129773

Abstract

We prove that polynomial time bounded RAMs with the instruction set [shift, +, X, boolean ] accept exactly the languages in PSPACE. This generalizes previous results: [5] showed the same for the instruction set that does not include multiplication, [5] and [7] proved the weaker theorems, that RAMs (and even PRAMs) with this instruction set could be simulated in EXPTAPE. The PRAM result is a simple corollary to our theorems. We also introduce other powerful string-manipulating instructions for RAMs, show a nontrivial simulation of Turing machines by these RAMs, and show that in a sense such simulations are optimal.

Keywords

TURING MACHINE
POWERFUL STRING-MANIPULATING INSTRUCTION
BOUNDED RAMS
GENERALIZES PREVIOUS RESULT
VARIOUS OPERATION SET
SIMPLE COROLLARY
WEAKER THEOREM
POLYNOMIAL TIME
PRAM RESULT
INSTRUCTION SET
NONTRIVIAL SIMULATION

This publication has 0 references indexed in Scilit: