On the complexity of RAM with various operation sets

Janos Simon; Mario Szegedy

doi:10.1145/129712.129773

On the complexity of RAM with various operation sets

Janos Simon, Mario Szegedy

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

We prove that polynomial time bounded RAMs with the instruction set [shift, +, ×, 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.

Original language	American English
Title of host publication	Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
Publisher	Association for Computing Machinery
Pages	624-631
Number of pages	8
ISBN (Electronic)	0897915119
DOIs	https://doi.org/10.1145/129712.129773
State	Published - Jul 1 1992
Externally published	Yes
Event	24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada Duration: May 4 1992 → May 6 1992

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F129722

Other

Other	24th Annual ACM Symposium on Theory of Computing, STOC 1992
Country/Territory	Canada
City	Victoria
Period	5/4/92 → 5/6/92

ASJC Scopus subject areas

Software

Access to Document

10.1145/129712.129773

Cite this

@inproceedings{6ce2bcffc9ef4184b65b1fff00fa4a83,

title = "On the complexity of RAM with various operation sets",

abstract = "We prove that polynomial time bounded RAMs with the instruction set [shift, +, ×, 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.",

author = "Janos Simon and Mario Szegedy",

year = "1992",

month = jul,

day = "1",

doi = "10.1145/129712.129773",

language = "American English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "624--631",

booktitle = "Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992",

note = "24th Annual ACM Symposium on Theory of Computing, STOC 1992 ; Conference date: 04-05-1992 Through 06-05-1992",

}

Simon, J & Szegedy, M 1992, On the complexity of RAM with various operation sets. in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129722, Association for Computing Machinery, pp. 624-631, 24th Annual ACM Symposium on Theory of Computing, STOC 1992, Victoria, Canada, 5/4/92. https://doi.org/10.1145/129712.129773

On the complexity of RAM with various operation sets. / Simon, Janos; Szegedy, Mario.
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, 1992. p. 624-631 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129722).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the complexity of RAM with various operation sets

AU - Simon, Janos

AU - Szegedy, Mario

PY - 1992/7/1

Y1 - 1992/7/1

N2 - We prove that polynomial time bounded RAMs with the instruction set [shift, +, ×, 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.

AB - We prove that polynomial time bounded RAMs with the instruction set [shift, +, ×, 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.

UR - http://www.scopus.com/inward/record.url?scp=0027001837&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027001837&partnerID=8YFLogxK

U2 - 10.1145/129712.129773

DO - 10.1145/129712.129773

M3 - Conference contribution

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 624

EP - 631

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -

On the complexity of RAM with various operation sets

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this