Almagor, Shaull ;
Ouaknine, Joël ;
Worrell, James
The PolytopeCollision Problem
Abstract
The Orbit Problem consists of determining, given a matrix A in R^dxd and vectors x,y in R^d, whether there exists n in 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 vectorspace 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 n in N such that A^n P_1 intersection P_2 does not equal the empty set. 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 longstanding numbertheoretic open problems.
Our proof begins by formulating the problem as the satisfiability of a parametrized family of sentences in the existential firstorder theory of realclosed 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.
BibTeX  Entry
@InProceedings{almagor_et_al:LIPIcs:2017:7452,
author = {Shaull Almagor and Jo{\"e}l Ouaknine and James Worrell},
title = {{The PolytopeCollision Problem}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {24:124:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7452},
URN = {urn:nbn:de:0030drops74521},
doi = {10.4230/LIPIcs.ICALP.2017.24},
annote = {Keywords: linear dynamical systems, orbit problem, algebraic algorithms}
}
2017
Keywords: 

linear dynamical systems, orbit problem, algebraic algorithms 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 