Array processing machines: an abstract model (Q1094879)

We present a new model of parallel computation called the ``array processing machine'' or APM (for short). The APM was designed to closely model the architecture of existing vector- and array processors, and to provide a suitable unifying framework for the complexity theory of parallel combinatorial and numerical algorithms. It is shown that every problem that is solvable in polynomial space on an ordinary, sequential random access machine can be solved in parallel polynomial time on an APM (and vice versa). The relationship to other models of parallel computation is discussed.