Steven Fortune
ABSTRACT
A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, deterministic parallel RAM's can accept in polynomial time exactly the sets accepted by polynomial tape bounded Turing machines; nondeterministic RAM's can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines. Similar results hold for other classes. The effect of limiting the size of the common memory is also considered.
- 1.Barnes, G.H., et.al. "The ILLIAC IV Computer", IEEE Trans. Computers. C-17 (Aug. 1968), pp. 746-757.Google Scholar
Digital Library
- 2.Chandra, A.K. and L.J. Stockmeyer. "Alteration", Proc. of the 17th Annual IEEE Symposium on Foundations of Computer Science, Houston, Texas, Oct. 1976, pp. 98-108.Google Scholar
- 3.Cook, S.A. and R.A. Reckhow. "Time Bounded Random Access Machines", JCSS 7 (1973),pp. 354-375.Google ScholarDigital Library
- 4.Csanky, L. "Fast Parallel Matrix Inversion Algorithms", Proc. of the 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, Oct. 1975, pp. 11-12.Google Scholar
- 5.Hartmanis, J. and J. Simon. "On the Power of Multiplication in Random Access Machines", Proc. of the 15th Annual IEEE Symposium on Switching and Automata Theory, New Orleans, Oct. 1974, pp. 13-23.Google ScholarDigital Library
- 6.Hirschberg, D.S. "Parallel Algorithms for the Transitive Closure and the Connected Component Problems", Proc. of the 8th Annual ACM Symposium on Theory of Computing, Hershey, Penn., May 1976, pp. 55-57. Google ScholarDigital Library
- 7.Kogge, P.M. "Parallel Solution of Recurrence Problems", IBM J. Res. Develop. 18 (March 1974), pp. 138-148.Google ScholarDigital Library
- 8.Kozen, D. "On Parallelism in Turing Machines", Proc. of the 17th Annual IEEE Symposium on Foundations of Computer Science, Houston, Texas, Oct. 1976, pp. 89-97.Google Scholar
- 9.Pratt, V.R. and L.J. Stockmeyer. "A Characterization of the Power of Vector Machines", JCSS 12 (1976), pp. 198-221.Google ScholarDigital Library
- 10.Savitch, W.J. "Relationships between Non-deterministic and Deterministic Tape Complexities", JCSS 4 (1970), pp. 177-192.Google ScholarDigital Library
- 11.Savitch, W.J. and M.J. Stimson. "Time Bounded Random Access Machines with Parallel Processing", Sept. 1976, (revised Aug. 1977)., technical report, Dept. APIS, University of California, San Diego, 78-CS-011.Google Scholar
- 12.Savitch, W.J. "Parallel and Nondeterministic Time Complexity Classes", November 1977, technical report, Dept. APIS, University of California, San Diego, 78-CS-012.Google Scholar
Index Terms
- Parallelism in random access machines
Recommendations
Reversal-bounded multipushdown machines
Several representations of the recursively enumerable (r.e.) sets are presented. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. The second states that every r.e. set is accepted by ...
Comments