## The Polytope-Collision Problem

*Shaull Almagor*,
*Joël
Ouaknine*, and *James Worrell*
The *Orbit Problem* consists of determining, given a matrix
*A* in **R**^{dxd} and vectors
*x*, *y* in **R**^{d},
whether there exists a positive integer *n* such that
*A*^{n} = *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 **R**^{d}. 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
*P*_{1}, and the target is a
polytope *P*_{2}. Then, the question is whether there
exists a positive integer *n* such
that *A*^{n} *P*_{1} intersects
*P*_{2}. 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