S.D. Bruda and S.G. Akl (Canada)
Real time, parallel computation, parallel real-time complexity, reconfigurable buses.
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 in NLOGSPACE. There fore, we conjecture that NLOGSPACE contains exactly all the computations that admit efficient (poly(n) processors) real-time parallel implementations. In the process, we determine the computational power of directed reconfigurable multiple bus machines (DRMBMs) with polynomially bounded resources and running in constant time, which is found to be exactly the same as the power of directed reconfigurable networks with the same properties. We also show that write conflict resolution rules such as Priority or even Common do not add computational power over the Collision rule, and that a bus of width 1 (i.e., a wire) suffices for any constant time computation on DRMBM.
Important Links:
Go Back
