Parallel pointer machines (Q2366720)

The paper describes a parallel version of a pointer machine consisting of finite state processors forming a network. During each (synchronous) transition each node reads the state of the neighbours it is currently connected to and updates its own state following a fixed program shared by all processors. A special input circuit supports reading an \(n\) bit input in sublinear time. This input circuit is more restricted in its operations than the other hardware; on the other hand the input circuit nodes don't contribute to the hardware complexity (being the number of processing nodes). The model differs from \textit{Goldschlagers} Aggregate in that a processor also may redirect its connections to any node within distance two. Furthermore the network is dynamic. A processor can create a new node similar to the corresponding instruction for sequential pointer machines; after being created the new node starts executing the program shared by all processors. In this way an exponential amount of hardware can be created and activated. It should be no surprise that this model obeys the parallel computation hypothesis in the sense that polynomial time for these parallel pointer machines equals polynomial space on the standard sequential devices. As is traditional, this property is proved by simulating sequential space by parallel time and conversely, and using alternating devices as a detour for making the simulation better understandable. The complete chain of simulations from sequential space to parallel time and back to sequential space in general shows a quadratic overhead; the location of this quadratic loss of efficiency differs for the various parallel models: for powerful models sequential space \(S\) is simulated in parallel time \(S\) and the converse simulation introduces the overhead \(S^ 2\); for weaker models the loss is suffered when simulating sequential space by parallel time. The parallel pointer machine is shown to be a strong model in this respect. As a second result the authors show that hardware \(S\) is equivalent to sequential space \(S/\log(S)\); this relation already holds for the sequential version of pointer machines as shown by \textit{D. R. Luginbuhl} and \textit{M. C. Loui} [Hierarchies and space measures for pointer machines, Inf. Comput. 104, 253-270 (1993; Zbl 0781.68055)] and independently by the reviewer \textit{P. van Emde Boas} [Machine models and simulations, in: J. van Leeuwen (ed.), Handbook of theoretical computer science Vol. 1, 1-66, Elsevier (1991; Zbl 0712.68054)] It is important to observe that the main results essentially depend on the fact that the model is chosen to be deterministic. The guess and verify simulation of the parallel pointer machine by an alternative sequential device requires determinism in order to enforce coherence of the guessed states and connections. It has been shown by \textit{Lam} and \textit{Ruzzo} (reference 22 in the paper) that time on the nondeterministic version of a parallel pointer machine is probably more powerful than sequential space. The parallel pointer machine therefore is not a true member of the second machine class is described in [J. van Leeuwen, loc. cit.].