On The Complexity of Bounded Time and
Precision Reachability for Piecewise Affine
Systems?
Hugo Bazille3 , Olivier Bournez1 , Walid Gomaa2,4 , and Amaury Pouly1

arXiv:1601.05353v3 [cs.CC] 17 Jan 2017

1

2

École Polytechnique, LIX, 91128 Palaiseau Cedex, France
Egypt Japan University of Science and Technology, CSE, Alexandria, Egypt
3
ENS Cachan/Bretagne et Université Rennes 1, France
4
Faculty of Engineering, Alexandria University, Alexandria, Egypt

Abstract. Reachability for piecewise affine systems is known to be undecidable, starting from dimension 2. In this paper we investigate the
exact complexity of several decidable variants of reachability and control questions for piecewise affine systems. We show in particular that
the region-to-region bounded time versions leads to NP-complete or coNP-complete problems, starting from dimension 2. We also prove that a
bounded precision version leads to P SP ACE-complete problems.

1

Introduction

A (discrete time) dynamical system H is given by some space X and a function f : X → X. A trajectory of the system starting from x0 is a sequence
x0 , x1 , x2 , . . . etc., with xi+1 = f (xi ) = f [i+1] (x0 ) where f [i] stands for ith iterate of f . A crucial problem in such systems is the reachability question: given a
system H and R0 , R ⊆ X, determine if there is a trajectory starting from a point
of R0 that falls in R. Reachabilty is known to be undecidable for very simple
functions f . Indeed, it is well-known that various types of dynamical systems,
such as hybrid systems, piecewise affine systems, or saturated linear systems,
can simulate Turing machines, see e.g., [12,9,14,15].
This question is at the heart of verification of systems. Indeed, a safety property corresponds to the determination if there is a trajectory starting from some
set R0 of possible initial states to the set R of bad states. The industrial and
economical impact of having efficient computer tools, that are able to guarantee that a given system does satisfy its specification, have indeed generated very
important literature. Particularly, many undecidability and complexity-theoretic
results about the hardness of verification of safety properties have been obtained
in the model checking community. However, as far as we know, the exact complexity of natural restrictions of the reachability question for systems as simple
as piecewise affine maps are not known, despite their practical interest.
Indeed, existing results mainly focus on the frontier between decidability
and undecidability. For example, it is known that reachability is undecidable
?

This work was partially supported by DGA Project CALCULS.

for piecewise constant derivative systems of dimension 3, whereas it is decidable
for dimension 2 [1]. It is known that piecewise affine maps of dimension 2 can
simulate Turing machines [13], whereas the question for dimension 1 is still open
and can be related to other natural problems [2,3,5]. Variations of such problems
over the integers have recently been investigated [6].
Some complexity facts follow immediately from these (un)computability results: for example, point-to-point bounded time reachability for piecewise affine
maps is P -complete as it corresponds to configuration to configuration reachability for Turing machines.
However, there remain many natural variants of reachability questions for
whose complexity have not yet been established.
For example, in the context of verification, proving the safety of a system can
often be reduced to a reachability question of the form point-to-region or regionto-region reachability. These variants are more general questions than point-topoint reachability. Their complexities do not follow from existing results.
In this paper we choose to restrict to the case of piecewise affine maps and
we consider the following natural variant of the problem.
BOUNDED TIME: we want to know if region R is reached in less than some
prescribed time T , with f assumed to be continuous.
FIXED PRECISION: given some precision ε = 2−n , we want to know if region
R is reached by f˜ε such that f˜ε (x) = b f (x)
ε cε. This corresponds to truncating f
at precision 2−n on each coordinate, or equivalently assuming that computations
happen at some precision not more that 2−n , for some given n. In other words,
one wants to know if R is reached by the dynamics where precision operation is
applied at each iteration.
Remark 1. We consider a version where everything is rounded downwards to a
multiple of epsilon. Variants could also be considered, with for example closest
or upper rounding. This would not change the complexity.
Remark 2. A variant could also be chain reachability: Deciding the existence of
sequence xn from initial region to target region such that at any intermediate
step i, ||xi+1 − f (xi )|| ≤ . We do not know the complexity of variants based on
this idea.
Remark 3. We consider piecewise affine maps over the domain [0, 1]d , The case
of integer domains has been studied in [6] and turns out to be quite different. We
also assume f to be continuous. This makes the hardness result more natural.
In an orthogonal way, control of systems or constructions of controllers for
systems often yield to dual questions. Instead of asking if some trajectory reaches
region R, one wants to know if all trajectories reach R. The questions of stability,
mortality, or nilpotence for piecewise affine maps and saturated linear systems
have been established in [7]. Still in this context, the complexity of the problem
when restricting to bounded time or fixed precision is not known.

This paper provides an exact characterization of the algorithmic complexity
of those two types of reachability for discrete time dynamical systems. Let P AFd
denote the set of piecewise-affine continuous functions over [0, 1]d . At the end
we get the following picture.
Remark 4. Notice that we expect in several statements time to be given in unary,
in order to get a completeness result. We do not know about the complexity of
the variants where time would be given in binary.
Problem: REACH-REGION
Inputs: a continuous P AFd f and two regions R0 and R in dom(f )
Output: ∃x0 ∈ R0 , t ∈ N, f [t] (x0 ) ∈ R?
Theorem 5 ([13]). Problem REACH-REGION is undecidable (and is recursively
enumerable-complete).
Problem: CONTROL-REGION
Inputs: a continuous P AFd f and two regions R0 and R in dom(f )
Output: ∀x0 ∈ R0 , ∃t ∈ N, f [t] (x0 ) ∈ R?
Theorem 6 ([7]). Problem CONTROL-REGION is undecidable (and is co-recursively
enumerable complete) for d > 2.
Problem: REACH-REGION-TIME
Inputs: a time T ∈ N in unary, a continuous P AFd f and two regions R0 and
R in dom(f )
Output: ∃x0 ∈ R0 , ∃t 6 T, f [t] (x0 ) ∈ R?
Theorem 7 (Theorems 31 and 36). REACH-REGION-TIME is NP-complete for
d > 2.
Problem: CONTROL-REGION-TIME
Inputs: a time T ∈ N in unary, a continuous P AFd f and two regions R0 and
R in dom(f )
Output: ∀x0 ∈ R0 , ∃t 6 T, f [t] (x0 ) ∈ R?
Theorem 8 (Theorems 37 and 38). CONTROL-REGION-TIME is coNP-complete
for d > 2.
Problem: REACH-REGION-PRECISION
Inputs: a continuous P AFd f , two regions R0 and R in dom(f ) and ε = 2−n ,
n given in unary
Output: ∃x0 ∈ R0 , t ∈ N, (f˜ε )[t] (x0 ) ∈ R?
Problem: CONTROL-REGION-PRECISION
Inputs: a continuous P AFd f , two regions R0 and R in dom(f ) and ε = 2−n ,
n given in unary
Output: ∀x0 ∈ R0 , ∃t ∈ N, (f˜ε )[t] (x0 ) ∈ R?

Theorem 9 (Theorems 40 and 40). REACH-REGION-PRECISION is P SP ACEcomplete for d > 2.
Theorem 10 (Theorems 40 and 40). CONTROL-REGION-PRECISION is P SP ACEcomplete for d > 2.
All our problems are region-to-region reachability questions, and requires
new proof techniques.
Indeed, classical tricks to simulate a Turing machine using a piecewise affine
maps encode a Turing machine configuration by a point, and assume that all
the points of the trajectories encode (possibly ultimately) valid Turing machines
configurations.
This is not a problem in the context of point-to-point reachability, but this
can not be extended to region-to-region reachability. Indeed, a (non-trivial) region consists mostly in invalid points: almost all points do not correspond to
encoding of Turing machines for all the encodings considered in [13,7].
In order to establish hardness results, the trajectories of all (valid and invalid)
points must be carefully controlled. This turns out not to be easily possible using
the classical encodings.
Let us insist on the fact that we restrict our results to continuous dynamics.
In this context, this is an additional source of difficulties: Dealing with points
and trajectories not corresponding to valid configurations or evolutions.
A short version of this paper has been presented at the conference “Reachability Problems 2014” [4]. The current journal version contains full proofs for all
statements, and is also providing new results: bounded precision variants (problems REACH-REGION-PRECISION and CONTROL-REGION-PRECISION) were not considered in short version [4].

2
2.1

Preliminaries
Notations

The set of non-negative integers is denoted N and the set of the first n naturals
is denoted Nn = {0, 1, . . . , n − 1}. For any finite set Σ, let Σ ∗ denote the set of
finite words over Σ. For any word w ∈ Σ ∗ , let |w| denote the length of w. Finally,
let λ denote the empty word. If w is a word, let w1 denote its first character,
w2 the second one and so on. For any i, j ∈ N, let wi...j denote the subword
wi wi+1 . . . wj . For any σ ∈ Σ, and k ∈ N, let σ k denote the word of length k
where all symbols are σ. For any function f , let f  E denote the restriction of
f to E and let dom(f ) denote the domain of definition of f .
2.2

Piecewise affine functions

Let I denote the unit interval [0, 1]. Let d ∈ N. A convex closed polyhedron in
the space I d is the solution set of some linear system of inequalities:
Ax ≤ b

(1)

with coefficient matrix A and offset vector b. Let P AFd denote the set of
piecewise-affine continuous functions over I d : That is to say, any f : I d → I d
in P AFd , f satisfies:
• f is continuous,
• there exists a sequence (Pi )1≤i≤p of convex closed polyhedra with nonempty
Sp
interior such that fi = f  Pi is affine, I d = i=1 Pi and P̊i ∩ P˚j = ∅ for
i 6= j, where P̊ denotes the interior of P .
In the following discussion we will always assume that any polyhedron P can
be defined by a finite set of linear inequalities, where all the elements of A and
b in (1) are all rationals. A polyhedron over which f is affine will also be called
a region.
2.3

Decision problems

In this paper, we will show hardness results by reduction from known hard
problems. We give the statement of these latter problems in the following.
Problem: SUBSET-SUM
Inputs: a goal B ∈ N andP
integers A1 , . . . , An ∈ N.
Output: ∃I ⊆ {1, . . . , n}, i∈I Ai = B?
Theorem 11 ([8]). SUBSET-SUM is NP-complete.
Problem: NOSUBSET-SUM
Inputs: a witness B ∈ N and
P integers A1 , . . . , An ∈ N.
Output: ∀I ⊆ {1, . . . , n}, i∈I Ai 6= B?
Theorem 12. NOSUBSET-SUM is coNP-complete.
Proof. Basically the same proof as Theorem 11 [8].

t
u

Problem: LINSPACE-WORD
Inputs: A Linear Bounded Automaton (i.e. a one-tape TM that does not use
any space besides the input) M and a word w ∈ Σ ∗ .
Output: does M accept w?
Theorem 13 (see e.g. [10]). LINSPACE-WORD is PSPACE-complete.

3

Hardness of Bounded Time Reachability

In this section, we will show that REACH-REGION-TIME is an NP-hard problem
by reducing SUBSET-SUM to it.

3.1

Solving SUBSET-SUM by iteration

We will now show how to solve the SUBSET-SUM problem by iterating a function. Consider an instance I = (B, A1 , . . . , An ) of SUBSET-SUM. We will need to
introduce some notions before defining our piecewise affine function. Our first
notion is that of configurations, representing partial summation of the number
for a given choice of I.
Remark 14. Without loss of generality, we will only consider instances where
Ai 6 B, for all i. Indeed, if Ai > B, it will never be an element of a solution to
the instance and so we can simply remove this variable from the problem. This
ensures that Ai < B + 1 in everything that follows.
Definition 15 (Configuration). A configuration of I is a tuple (i, σ, εi , . . . , εn )
where i ∈ {1, . . . , n + 1}, σ ∈ {0, . . . , B + 1}, εj ∈ {0, 1} for all i ≤ j. Let CI be
the set of all configurations of I.
The intuitive understanding of a configuration, made formal in the next definition, is the following: (i, σ, εi , . . . , εn ) represents a situation where after having
summed a subset of {A1 , . . . , Ai−1 }, we got a sum σ and εj is 1 if and only if we
are to pick Aj in the future.
Definition 16 (Transition function). The transition function TI : CI → CI ,
is defined as follows:
(
(i, σ)
if i = n + 1
TI (i, σ, εi , . . . , εn ) =
(i + 1, min (B + 1, σ + εi Ai ) , εi+1 , . . . , εn ) otherwise
It should be clear, by definition of a subset sum that we have the following
simulation result.
Lemma 17. For any configuration c = (i, σ, εi , . . . , εn ) and k ∈ {0, . . . , n + 1 −
i},

[k]
i+k−1
εj Aj , εi+k , . . . , εn )
TI (c) = (i + k, min B + 1, σ + Σj=i
t
u

Proof. By induction.

A consequence of this simulation is that we can reformulate satisfiability in
terms of reachability.
Lemma 18. I is a satisfiable instance ( i.e., admits a subset sum equal to the
target value) if and only if there exists a configuration c = (1, 0, ε1 , . . . , εn ) ∈ CI
[n]
such that TI (c) = (n + 1, B).
Proof. TheP
“only if” direction is the simplest: assume there exists I ⊆ {1, . . . , n}
such
that
i∈I Ai = B. Define εi = 1 if i ∈ I and 0 otherwise. We get that
Pn
ε
A
=
B. Apply Lemma 17 to get that:
i
i
i=1
!
n
X
[n]
TI (1, 0, ε1 , . . . , εn ) = (n + 1, min B + 1, 0 +
ε i Ai )
i=1

= (n + 1, min(B + 1, B)) = (n + 1, B)

The “if” direction is very similar: assume that there exists c = (1, 0, ε1 , . . . , εn )
[n]
such that TI (c) = (n + 1, B). Lemma 17 gives:
[n]
TI (1, 0, ε1 , . . . , εn )

= (n + 1, min B + 1, 0 +

n
X

!
εi Ai )

i=1

Pn
We can easily
Pconclude that i=1 εi Ai = B and thus by defining I = {i | εi =
1} we get that i∈I Ai = B. Hence, I is satisfiable.
t
u
3.2

Solving SUBSET-SUM with a piecewise affine function

In this section, we explain how to simulate the function TI using a piecewise affine function and some encoding of the configurations for a given I =
(B, A1 , . . . , An ). Since the reduction is quite technical, we start with some intuitions. In order to simulate the function TI , we first need to encode configurations
with real numbers. Let c = (i, σ, εi , . . . , εn ) be a configuration, we encode it using two real numbers in [0, 1]: the first one encodes i and σ and the second one
encodes εi , . . . , εn . A simple approach is to encode them as digits of dyadics
numbers, as depicted below:
hci =

i
.
0. 0 . . εi

0.

σ
. . . εn

!


i2−p + σ2−q
.
εi 2−1 + εi+1 2−2 + · · ·


=

In the above encoding, we allocate p bits to i and q − p bits to σ. We simply
need to choose them large enough to accomodate the largest possible value. The
rationale behind this encoding is that it is easy to implement the transition
function fI with a linear function. Note that for technical reasons explained
later, we need to encode the second coordinate in basis β = 5 instead of 2. We
now encode 0 as 0? = 1 and 1 as 1? = 4. Graphically, the action of f is very
simple:
?

if εi = 0 then fI

?

if εi = 1 then fI

0.

i
0. 0 . . . εi

σ
εi+1 . . . ε
n

!

i
.
0. 0 . . εi

σ
εi+1 . . . ε
n

!

0.

=

0.

i+1
0. 0 . . . 0

σ
εi+1 . . . ε
n

!

i+1
0. 0 . . . 0

σ + Ai
εi+1 . . . ε
n

!

0.

=

,

.

For technical reasons, we will in fact split the case εi = 1? into two, depending
on whether σ + Ai becomes greater then B + 1 or not. This is similar to what
we did in Definition 16 with min(B + 1, σ + Ai ):
if σ + Ai > B then fI

σ
i
?
0. 0 . . . 1 εi+1 . . . εn
0.

!
=

i+1
0. 0 . . . 0
0.

B+1
εi+1 . . . ε
n

!
.

We can formulate the “if εi = α” by using regions. Indeed, the set of encodings such that εi = α is
(

i
.
0. 0 . . α

0.

σ
εi+1 . . . ε
n

!

)
: σ ∈ N, εj ∈ {0, 1}

 −p −p

i2 , i2 + 2−p−1 
.
× αβ −i , (α + 1)β −i

⊂

It is crucial to note that the statement of the problems only allows for polyhedral
regions. This is why in the above equation, we had to overapproximate the
region by intervals on each coordinate. This overapproximation is the root of all
difficulties. Indeed, the region now contains many points that do not correspond
to encodings anymore. We now go to the details of the construction.
Definition 19 (Encoding). Define p = dlog2 (n + 2)e, ω = dlog2 (B + 2)e,
q = p + ω + 1 and β = 5. Also define 0? = 1 and 1? = 4. For any configuration
c = (i, σ, εi , . . . , εn ), define the encoding of c as follows:

hci = i2−p + σ2−q , 0? β −n−1 +

n
X


ε?j β −j 

j=i

Also define the following regions for any i ∈ {1, . . . , n+1} and α ∈ {0, . . . , β −1}:
R0 = [0, 2−p−1 ] × [0, 1]

Ri = [i2−p , i2−p + 2−p−1 ] × [0, β −i+1 ]


 

Ri,α = i2−p , i2−p + 2−p−1 × αβ −i , (α + 1)β −i
 −p −p
 

lin
Ri,1
, i2 + (B + 1 − Ai )2−q × 1? β −i , 5β −i
? = i2

(i > 1)

Ri = ∪α∈Nβ Ri,α
sat
lin
Ri,1
? = Ri,1? \ Ri,1?

As noted before, we use basis β = 5 on the second component to get some
“space” between consecutive encodings. The choice of the value 1 and 4 for the
encoding of 0 and 1, although not crucial, has been made to simplify the proof
as much as possible.
The region R0 is for initialization purposes and is defined differently from the
other Ri . The regions Ri correspond to the different values of i in the configuration (the current number). Each Ri is further divided into the Ri,α corresponding
to all the possible values of the next ε variable (recall that it is encoded in basis
β). In the special case of ε = 1, we cut the region Ri,1? into a linear part and a
saturated part. This is needed to emulate the min(σ +Ai , B +1) in Definition 16:
the linear part corresponds to σ + Ai and the saturated part to B + 1. Figure 1
and Figure 2 give a graphical representation of the regions.
Lemma 20. For any configuration c = (i, σ, εi , . . . , εn ), if i = n + 1 then hci ∈
Rn+1,0? , otherwise hci ∈ Ri,ε?i . Furthermore if εi = 1 and σ + Ai 6 B + 1, then
lin
sat
hci ∈ Ri,1
? , otherwise hci ∈ Ri,1? .

1

R0

R1

R2
0
0

1

Rn+1

B=2

n=2

p=2

ω=2

β=5

Fig. 1. Graphical representation of the regions

Proof. Recall that ω = dlog2 (B + 2)e so B + 1 < 2ω , and q = p + ω + 1. Since
σ 6 B + 1 by definition, (n + 1)2−p 6 hci1 6 (n + 1)2−p + (B + 1)2−p−1−ω 6
(n + 1)2−p + 2−p−1 . This shows the result for the first component. In the case
where σ + Ai 6 B + 1 then σ2−q 6 (B + 1 − Ai )2−q yielding the result for the
second part of the result for the first component.
If i = n + 1, then hci2 = 0? β −p−1 and it trivially belongs to [0? β −n−1 , (0? +
1)β −n−1 ]. Otherwise,
ε?i β −i 6 hci2 6 ε?i β −i +

n+1
X

1? β −j 6 ε?i β −i + 1? β −i−1

j=i+1

6 ε?i β −i + 4β −i−1

1 − β n−i
1 − β −1

β
6 ε?i β −i + β −i 6 (ε?i + 1)β −i .
β−1

This shows the result when i < n+1, for the second component of the result.

t
u

We can now define a piecewise affine function that will mimic the behavior
of T I . The region R0 is here to ensure that we start from a “clean” value on the
first coordinate.
Definition 21 (Piecewise affine simulation).


(2−p , b)





(a, b)
fI (a, b) = (a + 2−p , b − 0? β −i )



(a + 2−p + Ai 2−q , b − 1? β −i )



((i + 1)2−p + (B + 1)2−q , b − 1? β −i )

if
if
if
if
if

(a, b) ∈ R0
(a, b) ∈ Rn+1
(a, b) ∈ Ri,0?
lin
(a, b) ∈ Ri,1
?
sat
(a, b) ∈ Ri,1
?

Lemma 22 (Simulation is correct). For any configuration c ∈ CI , hTI (c)i =
fI (hci).
Proof. Let c = (i, σ, εi , . . . , εn ). There are several cases to consider: if i = n + 1
then TI (c) = c, also by Lemma 20, hci ∈ Rn+1,0? . Thus by definition of f ,
fI (hci) = hci = hT (c)i and this shows the result. If i < n + 1, we have three
more cases to consider: the case where we don’t take the value (εi = 0) and the
two cases where we take it (εi = 1) with and without saturation.
– If εi = 0 then TI (c) = (i + 1, P
σ, εi+1 , . . . , εn ). On the other hand, hci =
n
(a, b) = (i2−p + σ2−q , 0? β −i + j=i+1 εj β −j + 0? β −n−1 ). By Lemma 20,
hci ∈ Ri,0? so by definition of f :
fI (hci) = (a + 2−p , b − 0? β −i )
= ((i + 1)2−p + σ2−q ,

n
X

εj β −j + 0? β −n−1 )

j=i+1

= h(i + 1, σ, εi+1 , . . . , εn )i = hTI (c)i
– If εi = 1 and σ + Ai 6 B + 1 then TI (c) = (i + 1, σP
+ Ai , εi+1 , . . . , εn ). On the
n
other hand, hci = (a, b) = (i2−p + σ2−q , 1? β −i + j=i+1 εj β −j + 0? β −n−1 ).
lin
By Lemma 20, hci ∈ Ri,1? so by definition of f :
fI (hci) = (a + 2−p + Ai 2−q , b − 1? β −i )
n
X
= ((i + 1)2−p + (σ + Ai )2−q ,
εj β −j + 0? β −n−1 )
j=i+1

= h(i + 1, σ + Ai , εi+1 , . . . , εn )i = hTI (c)i
– If εi = 1 and σ + Ai > B + 1 then TI (c) = (i + 1, B + 1, εi+1 , . . . , εn ). By
sat
Lemma 20, hci ∈ Ri,1
? so by definition of f :
fI (hci) = ((i + 1)2−p + (B + 1)2−q , b − 1? β −i )
= h(i + 1, B + 1, εi+1 , . . . , εn )i = hTI (c)i
t
u
3.3

Making the simulation stable

In the previous section, that we have defined fI over a subset of the entire space
and it is clear that this subspace is not stable in any way5 . In order to match
the definition of a piecewise affine function, we need to define f over the entire
space or a stable subspace (containing the initial region). We follow this second
approach and extend the definition of f on some more regions. More precisely,
we need to define f over Ri = Ri,0 ∪ Ri,1 ∪ Ri,2 ∪ Ri,3 ∪ Ri,41 and at the moment
we have only defined f over Ri,1 = Ri,0? and Ri,4 = Ri,1? . Also note that
5

For example R1,1 ⊆ f (R0 ) but f is not defined over R1,1 .

lin
sat
Ri,4 = Ri,4
∪ Ri,4
and we define f separately on those two subregions. In order
to correctly and continuously extend f , we will need to further split the region
lin
sat
Ri,3 into linear and saturated parts Ri,3
and Ri,3
: see Figure 2.
Before jumping into the technical details of the extension, we start with the
intuition. First, it is crucial to understand that our main constraint is continutity:
since we already defined f over Ri,1 and Ri,4 , our extension need to agree with
f on the borders of those regions. Furthermore, f still needs to be affine, leaving
us with little flexibility. Second, the behaviour of f on those regions needs to
be carefully chosen. Indeed, as we mentioned before, we had to overapproximate
regions in several places and our simulation now includes extra points. We do not
want these extra points to have completely unpredictable trajectories, otherwise
they might reach the final region by chance and break the reduction. Therefore,
our strategy is to define f in such a way that its behaviour on those “wrong
points” still has a valid interpretation in the original SUBSET-SUM problem.
We detail this idea for the various region right after.
Let (a, b) ∈ Ri,0 ∪ Ri,2 ∪ Ri,3 : intuitively, this point corresponds to a configuration c = (i, σ, εi , . . . , ε) where εi ∈
/ {0? , 1? }. We know by construction that
this point does not correspond to a proper trajectory so it is tempting to simply
discard it. A very simple way of discarding point is to send them to a point x
that is (i) stable by f (f (x) = x) and (ii) not in the accepting region. That way
we trap the trajectory of invalid points into a useless region of the space. Let us
illustrate this on Ri,0 : let (a, b) ∈ Ri,0 and take fI (a, b) = (a, b). It is now trivial
that the point is stuck in Ri,0 . Unfortunately, fI is not continuous anymore.
Indeed, for (a, b) = (a, β −i ) ∈ Ri,0 ∩ Ri,1 we have a discontinuity on the first
coordinate. Indeed, f1 (a, b) = a on one side but f1 (a, b) = a + 2−p on the other.
A simple fix is to take f (a, b) = (a + 2−p , 0), this corresponds to:
!
!
σ
σ
i
0. i + 1
0.
=
.
if εi = 0 then fI
0. 0 . . . εi εi+1 . . . εn
0. 0 . . . 0 0 . . . 0

One can check that f is also continuous on the second coordinate. The reason
why this choice is clever is because f (Ri,0 ) ⊆ Ri+1,0 . Although the invalid points
are not stable, they are now stuck in the bottom regions Rj,0 for the rest of the
simulation.
Unfortunately, this trick now does not work on Ri,2 because of the continuity requirement on the second coordinate. Indeed, on Ri,1 ∩ Ri,2 we have that
f (a, b) = (a + 2−p , β −i ). To understand what it means, imagine a configuration
where εi = 2 and all the remaining εj are 0, then its image by f corresponds
to a configuration
were all the remaining εj are 4 = 1? plus an error. Indeed,
P∞
−n
−i
β = n=i+1 4β . In other words, we have:
!
!
σ
σ
i
0.
0. i + 1
if εi = 2 then fI
=
.
0. 0 . . . εi 0 . . . 0
0. 0 . . . 0 4 . . . 4 4 . . .
Furthermore, thinking about the future a bit, on Ri,3 ∩Ri,4 we have that f (a, b) =
(a + 2−p , 0). In other words, somewhere on Ri,2 ∪ Ri,3 , the second coordinate

has to go from β −i to 0 in a continuous fashion. This is where the clever tricks
comes in: we can continuously change the second coordinate from 1 to 0 such
that the action of f looks like all εj were “flipped”: 0 is exchange with 4 and 1
with 2. To visualise how this possible, simply think about the configuration as
having an infinite number of εj (although we use a finite amount of them) that
gets turned into an infinite number of µj where µj = 4 − εj :
!
!
σ
σ
0. i + 1
0. i + 1
=
.
fI
0. 0 . . . 2 εi+1 . . . εn εn+1. . .
0. 0 . . . 0 µi+1 . . . µn µn+1. . .
This might seem convoluted at first until one realises why this is helpful. Imagine
an extended SUBSET-SUM simulation where we now have three actions instead
of two:
– εi = 0: go to next number,
– εi = 1: add Ai and go to next number,
– εi = 2: flip all remaining εj and go to next number.
Our simulation corresponds to this extended problem, which is still NP-complete.
The remaining region Ri,3 follows the same principle as Ri,0 , with a slight complication because of the saturated sum. Figure 3 gives the interpretation of the
definition of f on each subregion.
Definition 23 (Extended region splitting). For i ∈ {1, . . . , n} and α ∈
{0, . . . , β − 1}, define:


2−p−1 + i2−p − a
lin
sat
lin
Ri,3
= Ri,3 ∩ (a, b) bβ i − 3 6 −p−1
Ri,3
= Ri,3 \Ri,3
2
− (B + 1 − Ai )2−q
sat
lin
sat
It should be clear by definition that Ri,3
= Ri,3
∪ Ri,3
and that the two
subregions are disjoint except on the border.

Definition 24 (Extended piecewise affine simulation).

(a + 2−p , 0)



(a + 2−p , 3β −i − b)
fI (a, b) =

(a + 2−p + Ai 2−q (bβ i − 3), 0)



((i + 23 )2−p − (bβ i − 3)(2−p−1 − (B + 1)2−q ), 0)

if
if
if
if

(a, b) ∈ Ri,0
(a, b) ∈ Ri,2
lin
(a, b) ∈ Ri,3
sat
(a, b) ∈ Ri,3

This extension was carefully chosen for its properties. In particular, we will
see that f is still continuous, Also, the domain of definition of f is f -stable (i.e.
f (dom f ) ⊆ dom f ). And finally, we will see that f is somehow “reversible”.
Lemma 25 (Simulation is continuous). For any i ∈ {1, . . . , n}, fI (Ri ) is
well-defined and continuous over Ri .
Proof. As outlined on Figure 2, we need to check that the definitions of f match
at the borders of each subregions of Ri . More precisely, we need to check that
Definition 21 and Definition 24 agree on all borders.

β −i+1
lin
−p
Ri,1
+ Ai 2−q , b − 1? β −i )
? : (a + 2

sat
Ri,1
? :

((i + 1)2−p + (B + 1)2−q ,
b − 1? β −i )

4β −i
sat
Ri,3
: (?)

lin
Ri,3
: (a + 2−p + Ai 2−q (bβ i − 3), 0)

3β −i
Ri,2 : (a + 2−p , 3β −i − b)
2β −i
Ri,0? : (a + 2−p , b − 0? β −i )
β −i
Ri,0 : (a + 2−p , 0)
0
i2−p

i2−p + (B + 1 − Ai )2−q

i2−p + 2−p−1

(?) : ((i + 1)2−p + 2−p−1 − (bβ i − 3)(2−p−1 − (B + 1)2−q ), 0)

Fig. 2. Zoom on one Ri with the subregions and formulas.
β −i+1
lin
Ri,1
? : add Ai

sat
Ri,1
? : set sum to B + 1

4β −i
lin
Ri,3
:



sat
Ri,3
: (?)

set all remaining εj to 0
add a funny amount†

3β −i
Ri,2 : flip all remaining εj
2β

−i

Ri,0? : go to next number
β −i
Ri,0 : set all remaining εj to 0
0
i2−p

i2−p + (B + 1 − Ai )2−q


(?) :

set all remaining εj to 0
add a funny amount†

i2−p + 2−p−1

†

The amount depends on (a, b) and
has no simple interpretation.

Fig. 3. Interpretation of the behaviour of f on each suregion. See also Figure 2 and
Section 3.2. All regions include an implicit “go to next number”.

– (a, b) ∈ Ri,0 ∩ Ri,0? : the first component is computed using the same formula
so is clearly continuous, the second component is always 0 on both side of
the border because b − 0? β −i = 0 for b = β −i
– (a, b) ∈ Ri,0? ∩ Ri,2 : the first component is computed using the same formula
so is clearly continuous, the second component is always β −i on both side of
the border because b − 0? β −i = 3β −i − b = β −i for b = 2β −i
lin
– (a, b) ∈ Ri,2 ∩ Ri,3
: the first component is a + 2−p and the second component
is 0 on both side of the border because 3β −i − b = bβ i − 3 = 0 for b = 3β −i
−p
lin
lin
+ Ai 2−q and the second
– (a, b) ∈ Ri,3
∩ Ri,1
? : the first component is a + 2
component is 0 on both side of the border because bβ i −3 = 1 and b−1? β −i =
0 for b = 4β −i
lin
sat
– (a, b) ∈ Ri,3
∩ Ri,3
: the second component is always 0 on both regions so is
Y
holds on
clearly continuous. From Definition 23 one can see that bβ i −3 = X
−p−1
−p
−p−1
the border where Y = 2
+ i2 − a and X = 2
− (B + 1 − Ai )2−q .
Consequently, if we compute the difference between the two expression at
the borders, we get:

(i + 1)2−p + 2−p−1 − (bβ i − 3)(2−p−1 − (B + 1)2−q )

− a + 2−p + Ai 2−q (bβ i − 3)
Y
= i2−p + 2−p−1 − a − (2−p−1 − (B + 1)2−q + Ai 2−q )
X
Y
=Y − X=0
X
this proves that they are equal.
sat
sat
−p
– (a, b) ∈ Ri,3
∩ Ri,1
+ (B + 1)2−q and the
? : the first component is (i + 1)2
second component is 0 on both side of the border because bβ i − 3 = 1 and
b − 1? β −i = 0 for β = 4β −i
lin
sat
−p
– (a, b) ∈ Ri,1
+ (B + 1)2−q on
? ∩ Ri,1? : the first component is (i + 1)2
−p
−q
both side of the border because a = i2 + (B + 1 − Ai )2 , and the second
component is computed using the same formula so is clearly continuous
t
u
Lemma 26 (Simulation is stable). For any i ∈ {1, . . . , n}, fI (Ri ) ⊆ Ri+1 .
Furthermore, f (R0 ) ⊆ R1 and f (Rn+1 ) ⊆ Rn+1 .
Proof. We need to examinate all possible cases for (a, b) ∈ Ri . Since Ri =
S4
lin
sat
α=0 Ri,α and that Ri,α = Ri,α ∪ Ri,α we indeed cover all cases.
– If (a, b) ∈ R0 : then fI (a, b) = (a+2−p , b) so fI (R0 ) = fI ([0, 2−p−1 ]×[0, 1]) =
[2−p , 2−p + 2−p−1 ] × [0, 1] = R1 .
– If (a, b) ∈ Rn+1 : then fI (a, b) = (a, b) so fI (Rn+1 ) = Rn+1 .
– If (a, b) ∈ Ri,0 : then fI (a, b) = (a + 2−p , 0) so fI (Ri,0 ) = fI ([i2−p , i2−p +
2−p−1 ] × [0, β −i ]) = [(i + 1)2−p , (i + 1)2−p + 2−p−1 ] × {0} ⊆ Ri+1 .
– If (a, b) ∈ Ri,1 = Ri,0? : then fI (a, b) = (a + 2−p , b − 0? β −i ) so fI (Ri,1 ) =
fI ([i2−p , i2−p + 2−p−1 ] × [β −i , 2β −i ]) = [(i + 1)2−p , (i + 1)2−p + 2−p−1 ] ×
[0, β −i ] = Ri+1 .

– If (a, b) ∈ Ri,2 : then fI (a, b) = (a+2−p , 3β −i −b) so fI (Ri,2 ) = fI ([i2−p , i2−p +
2−p−1 ] × [2β −i , 3β −i ]) = [(i + 1)2−p , (i + 1)2−p + 2−p−1 ] × [0, β −i ] = Ri+1 .
lin
: the image of the second component is always 0 so it’s
– If (a, b) ∈ Ri,3
easy for this one, also from Definition 23, bβ i − 3 6
2−p−1 +i2−p −a
Ai 2−q
−p−1

−p−1

−q

2−p−1 +i2−p −a
2−p−1 −(B+1−Ai )2−q
−q
ω −q

6

2−p−1 +i2−p −a
2−p−1 −(B+1−Ai )2−q

>

because 2
− (B + 1)2 > 0 since (B + 1)2 6 2 2 6
2
. Consequently, for the first coordinate we get that fI (a, b)1 6 a +
−p−1
−p
−a
2−p + Ai 2−q 2 A+i2
6 (i + 1)2−p + 2−p−1 . Also, since i2−p 6 a 6
−q
i2
−p
−p−1
lin
i2 + 2
, it is clear that fI (a, b)1 > (i + 1)2−p . So finally, fI (Ri,3
)⊆
[(i + 1)2−p , (i + 1)2−p + 2−p−1 ] × {0} ⊂ Ri+1 .
sat
– If (a, b) ∈ Ri,3
: the image of the second component is always 0 so it’s
easy for this one, also from Definition 23, bβ i − 3 >
2−p−1 +i2−p −a
2−p−1 −(B+1)2−q

because Ai > 0. Consequently, for the first coordinate we get
−p−1

−p

2
+i2 −a
that fI (a, b)1 6 (i + 1)2−p + 2−p−1 − (2−p−1 − (B + 1)2−q ) 2−p−1
−(B+1)2−q 6
−p
−p−1
−p
−p−1
−p
−p−1
(i + 1)2 + 2
+ i2 + 2
− a 6 (i + 1)2 + 2
since a 6
i2−p + 2−p−1 . Also since bβ i − 3 6 1 we get that fI (a, b)1 > (i + 1)2−p +
2−p−1 − (2−p−1 − (B + 1)2−q ) × 1 > (i + 1)2−p + (B + 1)2−q . So finally,
sat
fI (Ri,3
) ⊆ [(i + 1)2−p + (B + 1)2−q , (i + 1)2−p + 2−p−1 ] × {0} ⊂ Ri+1 .
lin
lin
−p
– If (a, b) ∈ Ri,4
= Ri,1
+ Ai 2−q , b − 1? β −i ) so
? : then fI (a, b) = (a + 2
lin
−p
−p
−q
−i
fI (Ri,4 ) = fI ([i2 , i2 + (B + 1 − Ai )2 ] × [4β , 5β −i ]) = [(i + 1)2−p +
Ai 2−q , (i+1)2−p +(B +1)2−q ]×[0, β −i ] ⊆ Ri+1 because (B +1)2−q 6 2−p−1 .
sat
sat
– If (a, b) ∈ Ri,4
: then fI (a, b) = ((i + 1)2−p + (B + 1)2−q , 0) so fI (Ri,4
)=
−p
−q
{(i + 1)2 + (B + 1)2 } × {0} ⊆ Ri+1 .
t
u

We now get to the core lemma of the simulation. Up to this point, we were
only interested in forward simulation: that is given a point, what are the iterates
of x. In order to prove the NP-hardness result, we need a backward result:
given a point, what are the possible preimages of it. To this end, we introduce
new subregions Riunsat of the Ri , that we call unsaturated. Intuitively, Riunsat
corresponds to the encodings where σ 6 B, that is the sum did not saturate at
B + 1. We also introduce the Rf in region, that will be the region to reach. We
will be interested in the preimages of Rf in .
Definition 27 (Unsaturated regions). For i ∈ {1, . . . , n + 1}, define
Riunsat = [i2−p , i2−p + B2−q ] × [β −n−1 , β −i+1 − β −n−1 ]
Rf in = [(n + 1)2−p + B2−q − 2−q−1 , (n + 1)2−p + B2−q ] × [β −n−1 , 2β −n−1 ]
Lemma 28 (Simulation is reversible). Let i ∈ {2, . . . , n} and (a, b) ∈ Riunsat
Then the only points x such that fI (x) = (a, b) are:
unsat
– x = (a − 2−p , b + 0? β −i+1 ) ∈ Ri−1,0? ∩ Ri−1
−p
i
? −i+1
unsat
– x = (a − 2 , β − b + 0 β
) ∈ Ri−1,2 ∩ Ri−1

lin
unsat
– x = (a − 2−p − Ai 2−q , b + 1? β −i+1 ) ∈ Ri−1,1
(only if a > 2−p +
? ∩ Ri−1
−q
Ai 2 )

Proof. First notice that since fI (Ri ) ⊆ Ri+1 for all i ∈ {0, . . . , n}, the only
candidates for x must belong to Ri−1 . Furthermore, on each affine region, there
can only be one candidate except if the function is trivial.
A close look at the proof of Lemma 26 reveals that:
– fI (Ri−1,0 ) ⊆ [(i + 1)2−p , (i + 1)2−p + 2−p−1 ] × {0} shareing no point with
Riunsat so there is no possible candidate
– fI (Ri−1,1 ) = Ri and there is only one possible candidate
– fI (Ri−1,2 ) = Ri and there is only one possible candidate
– fI (Ri−1,3 ) ⊆ [(i + 1)2−p , (i + 1)2−p + 2−p−1 ] × {0} so like Ri−1,0 there is no
possible candidate
lin
– fI (Ri−1,4
) ⊆ Ri and there is only one possible candidate
sat
– fI (Ri−1,4 ) ⊆ [(i + 1)2−p + (B + 1)2−q , (i + 1)2−p + 2−p−1 ] × [0, β −i ] sharing
no point with Riunsat so there is no possible candidate
It is then only a matter of checking that the claimed formulas work and they
lin
trivially do except for the case of Ri−1,4
where we need the potential candidate
to belong to the region.
t
u
The goal of those results is to show that if there is a point in Rf in that is
reachable from R0 then we can extract, from its trajectory, a configuration that
also reaches Rf in . Furthermore, we arranged so that Rf in contains the encoding
of only one configuration: (n + 1, B) (see Lemma 18).
Lemma 29 (Backward-forward identity). For any point x ∈ Rf in , if there
[k]
exists a point y ∈ R0 and an integer k such that fI (y) = x then there exists a
[k]
configuration c = (1, 0, ε1 , . . . , εn ) such that fI (hci) ∈ Rf in .
Proof. Define y0 = y and yi+1 = fI (yi ) for all i ∈ {0, k − 1}. Since y0 ∈ R0 ,
we immediately get that yi ∈ Ri using Lemma 26 and in particular, k > n + 1
because yk = x ∈ Rn+1,0? .
unsat
Now apply Lemma 28 starting from yn+1 ∈ Rn+1
: we conclude that for
lin
all i > 1, yi ∈ (Ri,1 ∪ Ri,2 ∪ Ri,4
) ∩ Rnunsat . Define εi = 0 if yi ∈ Ri,1 ∪ Ri,2
lin
and 1 if yi ∈ Ri,4
. Write yi = (ai , bi ). Again using Lemma 26 we get that
−p
ai−1 = ai −2 −εi Ai 2−q (just check all three cases). Also since x = yn+1 ∈ Rf in
then an+1 ∈ [(n + 1)2−p + B2−q − 2−q−1 , (n + 1)2−p + B2−q ]. Finally, y0 ∈ R0 so
fI (a0 , b0 ) = (2−p , 0) = (a1 , b1 ). We conclude that a1 = 2−p . Putting everything
together we get:

Pn
an+1 = (n + 1)2−p + 2−q i=1 εi Ai
an+1 ∈ [(n + 1)2−p + B2−q − 2−q−1 , (n + 1)2−p + B2−q ]
Since the Ai , B are integers and εi ∈ {0, 1}, we get that B =
Lemma 22 on the configuration to conclude.

Pn

i=1

Ai εi . Apply
t
u

Lemma 30 (Final region is accepting). For any configuration c, if hci ∈
Rf in then c = (n + 1, B).


Pn
Proof. Write c = (i, σ, εi , . . . , εn ), thenhci = i2−p + σ2−q , j=i ε?i β −i + 0? β −n−1 .
It implies that i2−p + σ2−q ∈ [(n + 1)2−p + B2−q − 2−q−1 , (n + 1)2−p + B2−q ]
and because i is an integer in range [0, n + 1] and σ an integer in range [0, B + 1],
necessarily i = n + 1 and σ = B.
t
u
3.4

Complexity result

We now have all the tools to show that REACH-REGION-TIME is an NP-hard
problem.
Theorem 31. REACH-REGION-TIME is NP-hard for d > 2.
Proof. Let I = (B, A1 , . . . , An ) be an instance of SUBSET-SUM. We consider the
instance J of REACH-REGION-TIME defined in the previous section with maximum number of iterations set to n (the number of Ai ), the initial region set
to R0 and the final region set to Rf in . One easily checks that this instance has
polynomial size in the size of I. The two directions of the proof are:
– If I is satisfiable then use Lemma 17 and Lemma 22 to conclude that there
[n]
is a point x ∈ R0 in the initial region such that fI (x) ∈ Rf in so J is
satisfiable.
[k]
– If J is satisfiable then there exists x ∈ R0 and k 6 n such that fI (x) ∈
Rf in . Use Lemma 29 and Lemma 22 to conclude that there exists a config[k]
[k]
uration c = (1, 0, ε1 , . . . , εn ) such that hTI (c)i = fI (hci) ∈ Rf in . Apply Lemma 30 and use the injectivity of the encoding to conclude that
[k]
TI (c) = (n + 1, B) and Lemma 18 to get that I is satisfiable.
t
u

4

Bounded Time Reachability is in NP

In the previous section we have shown that the REACH-REGION-TIME problem
is NP-hard. We now give a more precise characterization of the complexity of
this problem, by proving that it is NP-complete. Since we have shown its NPhardness, the only thing that remains to be shown is that REACH-REGION-TIME
belongs to NP. This is done in this section.
4.1

Notations and definitions

For any i ∈ {1, . . . , d}, let πid : Rd → R denote the ith projection function, that
is, π(x1 , . . . , xd ) = xi . Let gd : Rd+1 → Rd be defined by gd (x1 , . . . , xd+1 ) =
(x1 , . . . , xd ). For a square matrix A of size (d + 1) × (d + 1) define the following
pair of projection functions. The first function h1,d takes as input a square matrix

A of size (d + 1) × (d + 1) and returns a square matrix of size d × d that is the
upper-left block of A. The second function h2,d takes as input a square matrix A
of size (d+1)×(d+1) and returns the vector of size d given by [a1,d+1 · · · ad,d+1 ]T
(the last column of A minus the last element).
Let s denote the size function, its domain of objects will be overloaded and
understood from the context. For x ∈ Z, s(x) is the length of the encoding of
x in base 2. For x ∈ Q with x = pq with p and q coprime, we have s(x) =
max(s(p), s(q)). For an affine function f we define the size of f (x) = Ax + b
(where all entries of A and b are rationals) as: s(f ) = max(maxi,j (s(ai,j )), max(s(bi ))).
We define the size of a polyhedron r defined by Ax 6 b as: s(r) = max(s(A), s(b)).
We define the size of a piecewise affine function f as: s(f ) = maxi (s(fi ), s(ri ))
where fi denotes the restriction of f to ri the ith region.
We define the signature of a point x as the sequence of indices of the regions
traversed by the iterates of f on x (that is, the region trajectory).
4.2

REACH-REGION-TIME is in NP

In order to solve a reachability problem, we will formulate it with linear algebra.
However a crucial issue here is that of the size of the numbers, especially when
computing powers of matrices. Indeed, if taking the nth power of A yields a
representation of exponential size, no matter how fast our algorithm is, it will
run on exponentially large instances and thus be slow.
First off, we show how to move to homogeneous coordinates so that f becomes
piecewise linear instead of piecewise affine.
Lemma 32. Assume that f (x) = Ax 
+ b with
 A = (ai,j )16i,j6d and let y =
Ab
0
T
0
A (x, 1) where A is the block matrix
. Then f (x) = gd (A0 (x, 1)T ).
0 1
Remark 33. Notice that this lemma extends nicely to the composition of affine
functions: if f (x) = Ax + b and h(x) = Cx + d then h(f (x)) = gd (C 0 A0 (x, 1)T ).
We can now state the main lemma, namely that the size of the iterates of f
vary linearly in the number of iterates, assuming that f is piecewise affine.
Lemma 34. Let d > 2 and f ∈ P AFd . Assume that all the coefficients of f
on all regions are rationals. Then for all t ∈ N, s(f [t] ) 6 (d + 1)2 s(f )pt + (t −
1)dlog2 (d + 1)e where p is the number of regions of f . This inequality holds even
if all rationals are taken to have the same denominator.
Proof. Using Lemma 32, we get that f [t] (x) = gd (h[t] ([x 1]T )), where h is a
piecewise linear function in dimension d + 1 such that s(h) = s(f ). We show this
result by induction on t for h. The result then follows for f . In all cases we take
all rationals to have the same denominator.
In the case t = 1, it suffices to see that taking all rationals to have the same
denominator involves multiplying the numerator and denominators by at most
2
the lowest common multiple of all numbers, and hence is at most 2s(f )(p(d+1) ) .

Indeed the greatest number is 2s(h) by definition, and there are (d + 1)2 numbers
per region (the entries of the matrix).
Assume the result is true for t ∈ N. Let y ∈ Qd+1 . Then h[t+1] (y) =
Bt+1 · · · B1 y, where Bi ’s are the matrices corresponding to some regions of
h. In particular, s(Bi ) 6 s(h). From the induction hypothesis we can assume
that all rationals have the same denominator and we get that s(Bt · · · B1 ) 6
(d + 1)2 s(h)pt + (t − 1)dlog2 (d + 1)e. It follows6 that for any 1 6 i, j 6 d + 1:

s((Bt+1 · · · B1 )i,j ) = s

d+1
X

!
(Bt+1 )i,k (Bt · · · B1 )k,j

k=1

6 dlog2 (d + 1)e + s(Bt+1 ) + s(Bt · · · B1 )
6 dlog2 (d + 1)e + s(h) + (d + 1)2 s(h)pt + (t − 1)dlog2 (d + 1)e
6 (d + 1)2 s(h)p(t + 1) + tdlog2 (d + 1)e
This shows the result for the particular region where y belongs. Since the
bound does not depend on y and h[t+1] has finitely many regions, it is true for
all regions of h[t+1] .
t
u
Finally, we need some result about the size of solutions to systems of linear
inequalities. Indeed, if we are going to quantify over the existence of a solution
of polynomial size, we must ensure that the size constraints do not change the
satisfiability of the system.
Lemma 35 ([11]). Let A be a N × d integer matrix and b an integer vector.
If the Ax 6 b system admits a solution, then there exists a rational solution xs
such that s(xs ) 6 (d + 1)L + (2d + 1) log2 (2d + 1) where L = max(s(A), s(b)).

Proof. See Theorem 5 of [11]: s(xs ) 6 s (2d + 1)!2L(2d+1) .
t
u
Putting everything together, we obtain a fast nondeterministic algorithm to
solve REACH-REGION-TIME. The nondeterminism allows us to choose a signature
for the solution. Once the signature is fixed, we can write it as a linear program
of reasonable size using Lemma 34 and solve it. The remaining issue is the one
of the size of solution but fortunately Lemma 35 ensures us that there is a small
solution that can be found quickly.
Theorem 36. REACH-REGION-TIME is in NP.
Proof. The idea of the proof is to nondeterministically choose a signature for a
solution, that is a sequence of regions for the iterates of the solution. We then
build a system of linear inequalities stating that a point x belongs to the initial
region and that the iterates match the signature chosen and finally that the
iterates reach the final region. Using the results of the previous section, we can
build this system in polynomial time and solve it in non-deterministic polynomial
time. Here is an outline of the algorithm:
6

Use elementary properties of the size function: s(xy) 6 s(x)+s(y), s(x1 +· · ·+xk ) 6
s(k) + maxk s(xk )

–
–
–
–
–

Non-deterministically choose t 6 T
Non-deterministically choose regions r1 , . . . , rt−1 regions of f
Define r0 = R0 the initial region and rt = R the final region
Build (S) the system Ax 6 b stating that the signature of x matches r
Non-deterministically choose xs a rational of polynomial size in the size of
(S)
– Accept if Axs 6 b

We have two things to prove. First we need to show that this algorithm
indeed has non-deterministic polynomial running time. Second we need to show
that it is correct. Recall that T is a unary input of the problem.
The complexity of the algorithm is clear, assuming that (S) is of polynomial
size. Indeed verifying that a rational point satisfies a system of linear inequalities
with rationals coefficients can be done in polynomial time.
We build (S) this way: (S) = ∪ti=1 (Si ) where (Si ) states that f [i] (x) ∈
ri . Since we choose a signature of x we know that if x satisfies the system
then from Lemma 32 f [i] (x) = gd A0i−1 · · · A01 (x, 1)T where A0j is the matrix
corresponding to the region rj . Write Ci = A0i−1 · · · A01 and define (Si ) by the
system gd Ci (x, 1)T ∈ ri . Since ri is a polyhedron, (Si ) is indeed a system of
linear inequalities7 .
We can now see that S is of polynomial size using Lemma 34. Indeed,
s(Ci ) 6 s(f [i] ) 6 poly(s(f ), i), thus s((Si )) 6 s(Ci ) + s(ri ) 6 poly(s(f ), i)
because the description of the regions is part of the size of f . And finally
s((S)) 6 poly(s(f ), t).
The correctness follows from the construction of the system and Lemma 35.
More precisely we show that x ∈ (S) if and only if ∀i ∈ {0, . . . , t}, f [i] (x) ∈ ri .
Indeed, (S) ⇔ ∀i ∈ {0, . . . , t}, x ∈ (Si ) and by definition (Si ) ⇔ f [i] (x) ∈ ri
since gd (Ci (x, 1)T ) = f [i] (x). Then by Lemma 35, we get that ∃x ∈ (S) ⇔ ∃x ∈
(S) and s(x) 6 poly(s((S))).
t
u

5

Other Bounded Time Results

In this section, we give succinct proofs of the other result mentioned in the introduction about CONTROL-REGION-TIME. The proof is based on the same arguments
as before.
Theorem 37. Problem CONTROL-REGION-TIME is coNP-hard for d > 2.
Proof. The proof is exactly the same except for two details:
– we modify f over Rn+1 as follows: divide Rn+1 in three regions: Rlow that
is below Rf in , Rf in and Rhigh that is above Rf in . Then build f such that
f (Rlow ) ⊆ Rlow , f (Rf in ) ⊆ Rf in and f (Rhigh ) ⊆ Rlow .
– we choose a new final region Rf0 in = Rlow .
7

More precisely if ri is defined by Pi (x, 1)T 6 0 then (Si ) is the system Pi Ci (x, 1)T 6 0

Let I = (B, A1 , . . . , An ) be an instance of NOSUBSET-SUM, let J be the
corresponding instance of CONTROL-REGION-TIME we just built. We have
to show that I has no subset sum if and only if J is “controlled”. This is the
same as showing that I has a subset sum if and only if J has points never
reaching Rf0 in .
Now assume for a moment that the instance is in SUBSET-SUM (as opposed
to NOSUBSET-SUM), then by the same reasoning as the previous proof, there
will be a point that reaches the old Rf in region (and is disjoint from Rf0 in ). And
since Rf in is a f -stable region, this point will never reach Rf0 in .
And conversely, if the control problem is not satisfied, necessarily there is
a point whose trajectory went through the old Rf in (otherwise if would have
reached either Rlow = Rf0 in or Rhigh but f (Rhigh ) ⊆ Rlow ). Now we proceed as
in the proof of Theorem 31 to conclude that there is a subset that sums to B,
and thus I is satisfiable.
t
u
Theorem 38. Problem CONTROL-REGION-TIME is in coNP for d > 2.
Proof. Again the proof is very similar to that of Theorem 36: we have to build
a non-deterministic machine that accepts the “no” instances. The algorithm is
exactly the same except that we only choose signatures that avoid the final
region (as opposed to ending in the final region) and are of maximum length
(that is t = T as opposed to t 6 T ). Indeed, if there is a such a trajectory, the
problem is not satisfied. And for the same reasons as Theorem 36, it runs in
non-deterministic polynomial time.
t
u

6

Fixed Precision Results

Theorem 39. REACH-REGION-PRECISION and CONTROL-REGION-PRECISION are
P SP ACE-hard.
Proof. Consider a polynomial space Turing machine M = (Q, Σ, B, q0 , F, δ).
Without loss of generality, we can assume that F = {qf } ⊂ Q (there is a single
accepting state) and that the working alphabet is Σ = {0, 1, 2, . . . , β}, assuming
that B = 0 is the blank character, and δ : Q×Σ → Q×Σ ×{/, , .} is complete.
We also assume the set of internal states to be such that Q ⊆ Σ m for some m.
Let c be an instantaneous configuration (sometimes also called ID for Instataneous Description) of M. We write c = (x, σ, q, y) where x (resp. y) is encoding
the part of the tape on the left (resp. right) of the head, σ is the symbol under
the head, and q is the state of the machine. Specifically, if the non-blank part of
the tape is s−n . . . s−1 σs1 s2 . . . sm , with the head in front of σ, then x is encoded
as word s−1 s−2 . . . s−n , and y as word s1 s2 . . . sm .
Define the encoding of configuration c as hci = (hxi, hqσyi) where for any
P|w|
word w ∈ Σ ∗ , hwi = i=1 2wi (2γ )−i , where γ is such that 2β + 1 6 2γ . Define
regions Rα,q,σ = [hαi] × [hqσi] where [hwi] is a shortcut for [hwi] = [hwi, hwi +
(2γ )−|w| ]. Intuitively, Rα,q,σ contains all configurations in state q, with symbol σ
under the head and symbol α immediately at the left of the head. By construction

hci ∈ Rx1 ,q,σ with the above notations. Finally, for α, σ ∈ Σ, q ∈ Q, define f on
region Rα,q,σ by:

−γ
0
γ
0

a2 + hσ i, (b − hqσi)2 + hq i)
f (a, b) = (a, b − hqσi + hq 0 σ 0 i)


(a − hαi)2γ , (b − hqσi)2−γ + hq 0 ασ 0 i)

if δ(q, σ) = (q 0 , σ 0 , .)
if δ(q, σ) = (q 0 , σ 0 , )
if δ(q, σ) = (q 0 , σ 0 , /)

It is clear from the definition that f is piecewise affine over its domain of
definition. Let T be the function corresponding to one step of computation of M:
T is acting on configurations and maps any configuration c to the corresponding
next configuration according to the program of M. A simple case analysis shows
that for any configuration c, hT (c)i = f (hci), using the fact that the blank
character B was chosen to be 0.
Observe furthermore that by the choice of the encoding, all the regions Rα,q,σ
are closed and at positive distance from each other: Rα,q,σ ∩ Rα0 ,q0 ,σ0 = ∅ whenever (α, q, σ) 6= (α0 , q 0 , σ 0 ). It follows that f can be easily extended to a continuous piecewise linear function defined over the whole domain [0, 1] (similar
arguments are used in [12]). By construction it will still satisfy that for any
configuration c, hT (c)i = f (hci).
We can now state the reduction from problem LINSPACE-WORD: consider an
instance (M, w) of this decision problem. Define ε = (2γ )−(|w|+m+1) where the
choice of m was explained above. Then for any configuration c reachable from the
initial configuration c0 = (ε, q0 , w1 , w2 · · · w|w| ), we have the stronger property
that hci = b hci
ε cε. Indeed, by assumption the machine never uses more space
than the size of the input, thus the left and right part of tape are always smaller
than |w| at any point during the computation, and we simply need an extra m+1
space to store the current state of the machine. In other words, rounding to ε
does not perturbate the simulation. Consequently, we get that for any reachable
configuration c, hT (c)i = fε (hci).
Define R0 = {hc0 i} and R = [0, 1] × [hqf i] that are convex regions. Then the
instance (f, R0 , R, ε) of REACH-REGION-PRECISION is satisfiable if and only if
(M, w) belongs to problem LINSPACE-WORD. One easily checks that (f, R0 , R, ε)
has polynomial size in the size of (M, w).
The same instance also works for CONTROL-REGION-PRECISION. If we want to
make R0 a region with non-empty interior, just take a ball of radius smaller that
ε(2γ )−2 around hc0 i so that any input error is removed after the first application
of the function fε .
t
u
Theorem 40. REACH-REGION-PRECISION and CONTROL-REGION-PRECISION are
in P SP ACE.
Proof. Let N = bε−1 c and consider the graph G = (V, E) where
V = {0, . . . , N − 1}d

Cα =

d
Y

k=1

αk ε, (αk + 1)ε



(α ∈ V )

E = {(α, β) | f (Cα ) ∩ Cβ 6= ∅}

S = {α | f (R0 ) ∩ Cα 6= ∅}

T = {α | R ∩ Cα 6= ∅}
We can now restate our reachability problem in the graph G as an accessibility
problem from S to T . This can be done in space logarithmic in the size of the
graph, using the fact that accessibility in a graph with N vertices can be done
in non-deterministic space O(log N ), and using the fact that N SP ACE(N ) =
2
SP ACE(N
) (Savitch’s Theorem) [16,

 Theorem 8.5].
 Since the
 graph is of size
d
O N , this requires space O log2 N = O − log2 ε = O n2 if ε = 2−n . Also
note that computing the transitions of the graph is fast since f is a piecewise
affine function. The same proof applies to CONTROL-REGION-PRECISION except
we now want to know if for every vertex in S there is a path to T .
t
u

References
1. Asarin, E., Maler, O., Pnueli, A.: Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science 138(1), 35–65
(Feb 1995)
2. Asarin, E., Schneider, G.: Widening the boundary between decidable and undecidable hybrid systems. In: Brim, L., Jancar, P., Kretı́nský, M., Kucera, A.
(eds.) CONCUR 2002 - Concurrency Theory, 13th International Conference, Brno,
Czech Republic, August 20-23, 2002, Proceedings. Lecture Notes in Computer Science, vol. 2421, pp. 193–208. Springer (2002), http://link.springer.de/link/
service/series/0558/bibs/2421/24210193.htm
3. Asarin, E., Schneider, G., Yovine, S.: On the decidability of the reachability
problem for planar differential inclusions. In: Benedetto, M.D.D., SangiovanniVincentelli, A.L. (eds.) Hybrid Systems: Computation and Control, 4th International Workshop, HSCC 2001, Rome, Italy, March 28-30, 2001, Proceedings. Lecture Notes in Computer Science, vol. 2034, pp. 89–104. Springer (2001), http:
//link.springer.de/link/service/series/0558/bibs/2034/20340089.htm
4. Bazille, H., Bournez, O., Gomaa, W., Pouly, A.: On the complexity of bounded
time reachability for piecewise affine systems. In: Ouaknine, J., Potapov, I., Worrell, J. (eds.) Reachability Problems, Lecture Notes in Computer Science, vol.
8762, pp. 20–31. Springer International Publishing (2014), http://dx.doi.org/
10.1007/978-3-319-11439-2_2
5. Bell, P., Chen, S.: Reachability problems for hierarchical piecewise constant derivative systems. In: Abdulla, P., Potapov, I. (eds.) Reachability Problems, Lecture
Notes in Computer Science, vol. 8169, pp. 46–58. Springer Berlin Heidelberg (2013),
http://dx.doi.org/10.1007/978-3-642-41036-9_6
6. Ben-Amram, A.M.: Mortality of iterated piecewise affine functions over the integers: Decidability and complexity. In: STACS. pp. 514–525 (2013)
7. Blondel, V.D., Bournez, O., Koiran, P., Tsitsiklis, J.: The stability of saturated
linear dynamical systems is undecidable. Journal of Computer and System Science
62(3), 442–462 (May 2001), http://dx.doi.org/10.1006/jcss.2000.1737
8. Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co
(1979)
9. Henzinger, T.A., Kopke, P.W., Puri, A., Varaiya, P.: What’s decidable about hybrid automata? Journal of Computer and System Sciences 57(1), 94–124 (Aug
1998)

10. Karp, R.M.: Reducibility among combinatorial problems. Springer (1972)
11. Koiran, P.: Computing over the reals with addition and order. Theor. Comput.
Sci. 133(1), 35–47 (1994)
12. Koiran, P., Cosnard, M., Garzon, M.: Computability with low-dimensional dynamical systems. Theoretical Computer Science 132(1-2), 113–128 (Sep 1994)
13. Koiran, P., Cosnard, M., Garzon, M.: Computability with Low-Dimensional Dynamical Systems. Theoretical Computer Science 132, 113–128 (1994)
14. Moore, C.: Generalized shifts: unpredictability and undecidability in dynamical
systems. Nonlinearity 4(3), 199–230 (1991)
15. Siegelmann, H.T., Sontag, E.D.: On the computational power of neural nets. Journal of Computer and System Sciences 50(1), 132–150 (Feb 1995)
16. Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company
(1997)

