On iterative and cellular tree arrays

摘要

We study the computational complexity of two tree-structured models of parallel computation: the iterative tree array (ITA) and the cellular tree array (CTA). The underlying structure of an ITA is an infinite full binary tree with serial input/output at the root. A CTA, on the other hand, is a finite full binary tree with inputs applied in parallel to the leaves (at level log n) and outputs taken from the root. We show that a CTA and a log n-depth bounded ITA are linear-time related in that one can simulate the other with only linear-time loss. We also show that a sublinear-time bounded CTA (real-time log n-depth bounded ITA) can accept a language which is complete for P with respect to log-space reduction. In contrast, every language accepted by a CTA with one-way (i.e., bottom-up) communication between nodes can be accepted by a Turing machine in log2n/log log n space. The one-way CTA is quite powerful; e.g., it can accept the set of palindromes. To further exhibit the computing power of a CTA, we show that such an array (with the nodes capable of doing simple arithmetic and logical operations) can efficiently solve linear as well as some nonlinear recurrence equations.