Title :
The power of parallel random access machines with augmented instruction sets
Author :
Trahan, Jerry L. ; Ramachandran, Vijaya ; Loui, Michael C.
Author_Institution :
Dept. of Electr. & Comput. Eng., Louisiana State Univ., Baton Rouge, LA, USA
Abstract :
It is proved that the class of languages accepted in polynomial time by a parallel random access machine (PRAM) with both multiplication and shifts contains NEXPTIME and is contained in EXPSPACE. Thus, such a PRAM may be more powerful, to within a polynomial in time, that one with either multiplication or shifts alone. Bounds are established on the simulation of PRAMs with augmented instruction sets by sequential random access machines with the same instruction sets
Keywords :
computational complexity; instruction sets; parallel processing; EXPSPACE; NEXPTIME; augmented instruction sets; languages; parallel random access machines; polynomial time; Computational modeling; Concurrent computing; Instruction sets; Parallel machines; Phase change random access memory; Polynomials; Power engineering computing; Read-write memory; Turing machines; Writing;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41815
