Lower Bounds for Geometrical and Physical Problems
Jürgen Sellen · SIAM Journal on Computing · 1996
Motion planning involving arbitrarily many degrees of freedom is known to be PSPACE-hard. In this paper, we examine the complexity of generalized motion-planning problems for planar mechanisms consisting of independently movable objects. Our constructions constitute a general framework for reducing problems in information processing to motion planning, leading to easy proofs of known PSPACE-hardness results and to exponential lower bounds for geometrical problems related to motion planning. Particulalrly, we show that the problem of deciding whether a given mechanism A can always avoid a collision with another mechanism B is EXPSPACE-hard. New lower bounds are also obtained for the problem of planning under given physical side conditions. We consider the case that certain motions require forces, e.g., to subdue friction, and ask for motions that stay under a given energy limit. Within our framework, we show that such shortest-path problems are EXPTIME-hard if we use number representations by mantissa and exponent, and even undecidable if we allow that some motions require no force or an infinite amount. The proof consists of a simulation of Turing machines with infinite tape and shows that the notion of Turing computability can be interpreted in purely geometrical terms. The geometrical model obtained is capable of expressing a variety of physical-planning problems.