The Graph Accessibility Problem and the Universality of the Collision CRCW Conflict Resolution Rule

摘要

We complete the characterization of constant time computations on parallel models with reconfigurable buses: We have shown previously that directed reconfigurable multiple bus machines (DRMBM) with polynomially bounded resources and running in constant time solve exactly the same problems as nondeterministic logarithmic space bounded Turing machines, that write conflict resolution rules such as Priority or even Combining do not add computational power over the Collision rule, and that a bus of width 1 (a wire) suffices for any constant time computation on DRMBM. We now show that the same properties hold for constant time computations of directed reconfigurable networks (DRN). We then study the power of the Collision rule in the general case, linking strongly its universality with the Gapability of the model to compute the graph accessibility problem in constant time.