The Spatial Search Problem: Structure and Complexity

The paper discusses structure and complexity of the spatial search problem. From a set of assumptions it derives a rather general version of the spatial search problem and investigates some of its fundamental properties. Most importantly, the paper shows that the decision problem corresponding to the spatial search problem in this general version is NP-complete.