License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.24
URN: urn:nbn:de:0030-drops-74521
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7452/
Almagor, Shaull ;
Ouaknine, Joël ;
Worrell, James
The Polytope-Collision 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 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 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 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.
BibTeX - Entry
@InProceedings{almagor_et_al:LIPIcs:2017:7452,
author = {Shaull Almagor and Jo{\"e}l Ouaknine and James Worrell},
title = {{The Polytope-Collision Problem}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {24:1--24:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7452},
URN = {urn:nbn:de:0030-drops-74521},
doi = {10.4230/LIPIcs.ICALP.2017.24},
annote = {Keywords: linear dynamical systems, orbit problem, algebraic algorithms}
}
|
Keywords: |
|
linear dynamical systems, orbit problem, algebraic algorithms |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
