Discrete Mathematics and Theoretical Computer Science (subm.), by the authors, 2–rev On the Relation Between Parallel Real-Time Computations and Logarithmic Space †

We show that all the problems solvable by a nondeterministic machine with logarithmic work space (NLOGSPACE) can be solved in real time by a parallel machine, no matter how tight the real-time constraints are. We also show that, once real-time constraints are dropped, several other real-time problems are in effect solvable in nondeterministic logarithmic space. Therefore, we conjecture that NLOGSPACE contains exactly all the computations that admit efficient (poly(n) processors) real-time parallel implementations. The issue of real-time optimization problems over independence systems is also investigated. We identify the class of such problems that are solvable in real time. Finally, we address the problem of obtaining approximate real-time solutions for problems not solvable in real time. In the process, we determine the computational power of directed reconfigurable multiple bus machines (DRMBMs) with polynomially bounded resources (processors and buses) and running in constant time, which is found to be exactly the same as the power of directed reconfigurable networks of polynomially bounded size and constant running time. In addition, we show that sophisticated and of questionable feasibility write conflict resolution rules (such as Priority or even Common) do not add computational power over the Collision rule, and are thus unnecessary, and that a bus of width 1 (i.e., a wire) suffices for any constant time computation on DRMBM