On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes

Classifying the complexity of arithmetic computations is a crucial endeavour in theoretical computer science. Particularly interesting are the decidability and complexity issues pertaining to iterative arithmetic computations, i.e. computations consisting of a repeated application of some set of arithmetic operations on some initial value. Examples of such problems include matrix powering over various semirings [16, 9], the Skolem problem ("Does a given linear recurrent sequence contain a zero term?") and its variants [26, 27, 6], or the related Orbit problem [21, 4]. It is often natural to consider bounded or finite-horizon variants of the problems, which ask, given a time horizon H, whether a certain property holds within the first H iterations of the computation [9]. In this paper, we study the complexity of finite-horizon arithmetic computations arising in algorithmic decision making and operations research.