On the complexity of deadlock detection in families of planar nets

AbstractWe are interested in some properties of massively parallel computers which we model by finite automata connected together on a 2-dimensional grid. We wonder whether it is possible to anticipate a possible appearance of a deadlock in such nets. Thus, we look for efficient algorithms to predict whether deadlocks can appear in grids of bounded size. From the point of view of worst-case complexity, we prove that this problem is NP-complete whereas it is quadratic for linear structures. The method we use is a reduction from a tiling problem.We also prove that this problem, associated with a natural probability distribution on its instances, is RNP-complete (Random NP-complete) in the theory proposed by Levin and developed by Gurevich. Very few randomized problems are known to be RNP-complete. Under classical complexity hypotheses, this result proves that there does not exist any algorithm that solves this problem efficiently on the average case. We present other extentions of our results for different planar underlying communication graphs, and we present a Σ2-complete problem for networks with inputs