Parallel Random Access Machines with both Multiplication and Shifts

AbstractWe prove that the class of languages accepted in polynomial time by Parallel Random Access Machines with both multiplication and shifts using exponentially many processors (PRAM[*, ⇑, ⇓] − PTIME) includes the class of languages accepted in exponential time and polynomial alternations by an alternating Turing machine and is included in EXPSPACE. It follows that the class of languages accepted by a PRAM[*, ⇑, ⇓] in logarithmic time (using polynomially many processors) includes the polynomial hierarchy and is included in PSPACE. Thus, a PRAM[*, ⇑, ⇓] may be more powerful, to within a polynomial in time, than either a PRAM[*] or a PRAM[⇑, ⇓], since PRAM[*] − PTIME = PRAM[⇑, ⇓] − PTIME = PSPACE