Parallelism in Random Access Machines.

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. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1978
Accession Number
ADA058427

Entities

People

  • James Wyllie
  • Steve Fortune

Organizations

  • Department of Computer Science, Cornell University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accumulators
  • Automata
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Instructions
  • Language
  • Machines
  • Military Research
  • Parallel Computing
  • Parallel Processors
  • Polynomials
  • Programming Languages
  • Simulations

Readers

  • Mathematical Modeling and Probability Theory.