The Polytope-Collision Problem

Shaull Almagor, Joël Ouaknine, and James Worrell

The Orbit Problem consists of determining, given a matrix A in Rdxd and vectors x, y in Rd, whether there exists a positive integer n such that An = y. This problem was shown to be decidable in a seminal work of Kannan and Lipton in the 1980s. Subsequently, Kannan and Lipton noted that the Orbit Problem becomes considerably harder when the target y is replaced with a subspace of Rd. Recently, it was shown that the problem is decidable for vector-space targets of dimension at most three, followed by another development showing that the problem is in PSPACE for polytope targets of dimension at most three.

In this work, we take a dual look at the problem, and consider the case where the initial vector x is replaced with a polytope P1, and the target is a polytope P2. Then, the question is whether there exists a positive integer n such that An P1 intersects P2. We show that the problem can be decided in PSPACE for dimension at most three. As in previous works, decidability in the case of higher dimensions is left open, as the problem is known to be hard for long-standing number-theoretic open problems.

Our proof begins by formulating the problem as the satisfiability of a parametrized family of sentences in the existential first-order theory of real-closed fields. Then, after removing quantifiers, we are left with instances of simultaneous positivity of sums of exponentials. Using techniques from transcendental number theory, and separation bounds on algebraic numbers, we are able to solve such instances in PSPACE.

Proceedings of ICALP 17, LIPIcs 80, 2017. 14 pages.

PDF © 2017 Shaull Almagor, Joël Ouaknine, and James Worrell.

Imprint / Data Protection