Reachability in 3-VASS Is Elementary

In this paper we investigate complexity of the reachability problem in $3$-vass. Our main result is the first elementary upper complexity bound for the problem:

In particular, this refutes the natural conjecture that for every $d\ge 3$, the reachability problem for $d$-vass is ${ℱ}_d$-complete and provides the first algorithm, which solves the problem for vass with finite reachability sets faster than exhaustive search.

Our way to prove Theorem 1 is by bounding triply-exponentially the length of the shortest path between the given source and target configurations. This main technical result, formulated in Lemma 2 below, applies to sequential $3$-vass, which are sequences of strongly connected components $V_1,\mathrm{\dots },V_k$ linked by single transitions $u_1,\mathrm{\dots },u_{k-1}$ (see Figure 1; the rigorous definition is given in Section 2).

Given a vass $V$ and source and target configurations $s,t$, by $\text{size}(V,s,t)$ we mean the sum of absolute values of all the numbers occurring in transitions of $V$, $s$ and $t$, plus the number thereof.

Therefore the length of the shortest path in a $k$-component $3$-vass is bounded by $M^{2^{2^{𝒪(k)}}}$, where $M=\text{size}(V,s,t)$ is the size of input, under unary encoding. This is the first bound on the shortest path in vass of dimension higher than 2, that is not based on the size of (finite) reachability sets. Indeed, in a $3$-vass of size $M$, the size of finite reachability sets may be an arbitrary high tower of exponentials.

In consequence of Lemma 2, Theorem 1 follows immediately: the upper bound of Lemma 2 is triple-exponential in the size of input, irrespectively whether unary or binary encoding is used, which implies the same bound on norms of configurations along the shortest path. This yields a nondeterministic double-exponential space algorithm that first guesses a sequence of components leading from the source state to the target one, and then searches for a witnessing path. Note that the complexity bound under unary encoding is not better than under binary encoding.

Lemma 2 immediately yields further upper bounds for the reachability problem, when the number of components is fixed:

Indeed, for every fixed $k\ge 1$, the bound of Lemma 2 is polynomial with respect to unary input size. Therefore the length of the shortest path, as well as the norm of configurations along this path, are polynomially bounded in case of unary encoding, and exponentially bounded in case of binary encoding. This bounds yield membership in NL and PSpace, respectively. Thus for every fixed $k\ge 1$, the complexity of $k$-component $3$-vass matches the complexity of $2$-vass.

We start by introducing notation and basic facts in Section 2. Overview of the proof of our main result, Lemma 2, is presented in Section 3. In Section 4 we focus on 1-component $3$-vass, thus establishing the base of induction for Lemma 2. Next, in Section 5 we introduce the fundamental concept of polynomially approximable sets, and formulate our core technical result: reachability sets of $2$-vass are polynomially approximable. The result is then applied in the inductive proof of Lemma 2 in Section 6. We conclude in Section 7.

Let $d\in {\mathbb{N}}_{>0}$. A $d$-dimensional vector addition system with states ($d$-vass in short) $V=(Q,T)$ consists of a finite set $Q$ of states, and a finite set of transitions $T\subseteq Q\times {\mathbb{Z}}^d\times Q$. A configuration $c$ of $V$ consists of a state $q\in Q$ and a nonnegative vector $w\in {\mathbb{N}}^d$, and is written as $c=q(w)$. A transition $u=(q,v,q^{\prime })$ induces steps $q(w)\stackrel{u}{⟶}{q}^{\prime }(w^{\prime })$ between configurations, where $w^{\prime }=w+v$. We refer to the vector $v\in {\mathbb{Z}}^d$ as the effect of the transition $(q,v,q^{\prime })$ or of an induced step. A path $\pi$ in $V$ is a sequence of steps with the proviso that the target configuration of every step matches the source configuration of the next one:

The effect $\text{eff}(\pi )\in {\mathbb{Z}}^d$ of a path is the sum of effect of all steps, and its length is the number $n$ of steps. We say that the path is from $c_0$ to $c_n$, call $c_0,c_n$ source and target configuration, respectively, of the path, and write $c_0\stackrel{\pi }{⟶}{c}_n$. We also write $c\stackrel{\ast }{⟶}{c}^{\prime }$ if there is some path from $c$ to $c^{\prime }$. A path $q(v)\stackrel{\ast }{⟶}q(v^{\prime })$ in $V$ with the same source and target state we call a cycle. A cycle is simple if the only equality of states along the cycle is the equality of source and target states. When dimension $d$ is irrelevant, we write vass instead of $d$-vass.

By the geometric dimension of a $d$-vass we mean the dimension of the vector space $\text{Lin}(V)\subseteq {\mathbb{Q}}^d$ spanned by effects of all its simple cycles. In the sequel we most often consider $2$-vass and $3$-vass, but also geometrically 2-dimensional $3$-vass, i.e., $3$-vass of geometric dimension at most 2.

Two paths $\pi$ and ${\pi }^{\prime }$ can be concatenated (composed), written $\pi ;{\pi }^{\prime }$, if the target configuration of $\pi$ equals the source one of ${\pi }^{\prime }$. As long as it does not lead to confusion, we adopt a convention that when concatenating paths $\pi ;{\pi }^{\prime }$, the latter path ${\pi }^{\prime }$ is silently moved so that its source matches the target of $\pi$, under assumption that the source state of ${\pi }^{\prime }$ is the same as the target state of $\pi$. For instance, we write ${\pi }^m$ to denote the $m$-fold concatenation of a cycle $\pi$, even if $\text{eff}(\pi )\ne \overrightarrow{0}$.

We use the following notation for measuring size of representation of a vass. By norm of a vector $v=(v_1,\mathrm{\dots },v_d)\in {\mathbb{Q}}^d$, denoted $\text{norm}(v)$, we mean the sum of absolute values of all numbers appearing in it: $\text{norm}(v)=|v_1|+\mathrm{\dots }+|v_d|$; and by norm of a set of vectors $P$ we mean the sum of norms of its elements: $\text{norm}(P)=\sum \{\text{norm}(v)\mid v\in P\}$. By norm of a configuration $q(w)$, or of a transition $(q,w,q^{\prime })$, we mean the norm of its vector $w$. By size of a vass $V$, denoted $\text{size}(V)$, we mean the sum of norms of all its transitions, plus the number of transitions $\left|T\right|$. The norm of a vass is the maximal norm of its transition.

We often implicitly extend a vass $V$ with source configuration $s$, or with a pair of source and target configurations $s,t$. Slightly overloading terminology, a pair $(V,s)$ and a triple $(V,s,t)$ we call a vass too. For convenience we overload further and put $\text{size}(V,s)=\text{size}(V)+\text{norm}(s)$ and $\text{size}(V,s,t)=\text{size}(V)+\text{norm}(s)+\text{norm}(t)$. The reverse of a vass $V=(Q,T)$ is defined as $V^{\text{rev}}=(Q,T^{\prime })$, where $T^{\prime }$ is obtained by reversing all transitions in $T$: $T^{\prime }=\{(q^{\prime },-v,q)\mid (q,v,q^{\prime })\in T\}$. Overloading the notation again, we put ${(V,s,t)}^{\text{rev}}:=(V^{\text{rev}},t,s)$.

Given a vass together with an initial configuration $(V,s)$, we write $\text{Reach}(V,s)$ to denote the set of configurations $t$ such that $V$ has a path from $s$ to $t$. For every state $q\in Q$ we write ${\text{Reach}}_q(V,s)$ to denote the set of vectors $w\in {\mathbb{N}}^d$ such that $q(w)\in \text{Reach}(V,s)$. We write shortly $\text{Reach}(s)$ and ${\text{Reach}}_q(s)$ if the vass $V$ is clear from the context. If $t\in \text{Reach}(s)$ we say that $t$ is reachable from $s$. If $t+\mathrm{\Delta }\in \text{Reach}(s)$ for some $\mathrm{\Delta }\in {\mathbb{N}}^d$, we say that $t$ is coverable from $s$.

We consider a variant of vass, called $\mathbb{Z}$-vass, where the nonnegativeness constraint is dropped. Syntactically, $\mathbb{Z}$-vass is the same as vass, namely consists of a finite set of states and a finite set of transitions $(Q,T)$. Semantically, configurations of a $\mathbb{Z}$-vass are $Q\times {\mathbb{Z}}^d$, while all definitions (path, reachability set, etc.) are the same as in case of vass. Equivalently, we may also speak of $\mathbb{Z}$-configurations and $\mathbb{Z}$-paths of a vass, i.e., configurations and paths where the nonnegativeness constraint is dropped. Note that every $\mathbb{Z}$-path $q(w)\stackrel{\pi }{⟶}{q}^{\prime }(w^{\prime })$ may be lifted to become a path $q(w+\mathrm{\Delta })\stackrel{\pi }{⟶}{q}^{\prime }(w^{\prime }+\mathrm{\Delta })$, for some $\mathrm{\Delta }\in {\mathbb{N}}^d$.

We define the state graph of a vass $V=(Q,T)$: nodes are states $Q$, and there is an edge $(q,q^{\prime })$ if $T$ contains a transition $(q,v,q^{\prime })$ for some $v\in {\mathbb{Z}}^d$. A vass is called strongly connected if its state graph is so. A vass $V=(Q,T)$ is called sequential, if it can be partitioned into a number of strongly connected vass $V_1=(Q_1,T_1),\mathrm{\dots },V_k=(Q_k,T_k)$ with pairwise disjoint state spaces, and $k-1$ transitions $u_i=(q_i,v_i,q_i^{\prime })$, for $i\in [1,k-1]$, where $q_i\in Q_i$ and $q_i^{\prime }\in Q_{i+1}$ (recall Figure 1). Thus $Q=Q_1\cup \mathrm{\dots }\cup Q_k$ and $T=T_1\cup \mathrm{\dots }\cup T_k\cup \{u_1,\mathrm{\dots },u_{k-1}\}$. We call $V$ a $k$-component sequential vass, or $k$-component vass in short, and write down succinctly as $V=(V_1)u_1(V_2)u_2\mathrm{\dots }{u}_{k-1}(V_k).$ The vass $V_1,\mathrm{\dots },V_k$ are called components, and transitions $u_1,\mathrm{\dots },u_{k-1}$ bridges. By definition, a $1$-component sequential vass is just a strongly connected vass.

We will intensively use the following immediate corollary of [23] (see also [5, Prop. 4]):

We prove that if there is a path in a vass achieving a large value on every coordinate, then there is a path of bounded length that achieves simultaneously large values on all coordinates.²²2Lemma 5 is inspired by [19, Lemma 4.13], but the statement and the proof are different. We consider a general case of arbitrary dimension, as we believe it is of an independent interest, but in the sequel we will use it only for dimension $d=3$.

A function $f:\mathbb{N}\to \mathbb{N}$ is called nondecreasing if $f(n)\ge n$ for every $n\in \mathbb{N}$, and for all . Functions used in the sequel are most often nondecreasing. We say that a class $𝒞$ of vass or $\mathbb{Z}$-vass is length-bounded by a non-decreasing function $f:\mathbb{N}\to \mathbb{N}$ if for every $(V,s,t)$ in $𝒞$, if $s\stackrel{\ast }{⟶}t$ then $s\stackrel{\pi }{⟶}t$ for some path $\pi$ of length at most $f(\text{size}(V,s,t))$. A class $𝒞$ which is length-bounded by some nondecreasing polynomial we call polynomially length-bounded. It is known that $2$-vass have this property:

As a corollary of Lemmas 6 and 4, respectively, we derive the property for geometrically 2-dimensional $3$-vass (using [27, Lemma 5.1]) and $3$-$\mathbb{Z}$-vass, respectively:

Lemma 2 states that there exists a constant $C\in \mathbb{N}$ such that for every $k\in \mathbb{N}$, the $k$-component $3$-vass are length-bounded by the function $M\mapsto M^{2^{2^{C\cdot k}}}$. Therefore for every fixed $k\in \mathbb{N}$, the $k$-component $3$-vass are polynomially length-bounded, even if the degree of polynomial grows doubly exponentially in $k$.

A $3$-vass $(V,s,t)$, where $s=p(w)$ and $t=p^{\prime }(w^{\prime })$, is forward-diagonal if $p(w)\stackrel{\ast }{⟶}p(w+\mathrm{\Delta })$ in $V$ for some $\mathrm{\Delta }\in {({\mathbb{N}}_{>0})}^3$. Symmetrically, $(V,s,t)$ is backward-diagonal if ${(V,t,s)}^{\text{rev}}$ is diagonal, i.e., if $p^{\prime }(w^{\prime }+{\mathrm{\Delta }}^{\prime })\stackrel{\ast }{⟶}{p}^{\prime }(w^{\prime })$ in $V$ for some ${\mathrm{\Delta }}^{\prime }\in {({\mathbb{N}}_{>0})}^3$. Finally, $V$ is diagonal if it is both forward- and backward-diagonal. Obviously, the vectors $\mathrm{\Delta }$ and ${\mathrm{\Delta }}^{\prime }$ need not be equal in general.

Let $E=\{e_1,\mathrm{\dots },e_n\}\subseteq {\mathbb{Z}}^3$ be the effects of simple cycles of $V$. We define the (rational) open cone generated by this set to contain all positive rational combinations of vectors from $E$:

$\text{Cone}(V)$ is thus an open cone inside $\text{Lin}(V)$. A 1-component $3$-vass $V$ is called wide if ${({\mathbb{Q}}_{>0})}^3\subseteq \text{Cone}(V)$, i.e., if $\text{Cone}(V)$ includes the whole positive orthant.

Let $\text{Len}(V,s,t)$ denote the set of lengths of paths $s\stackrel{\ast }{⟶}t$ in $V$. We need to argue that there is a nondecreasing polynomial $Q$ such that every 1-component $3$-vass $(V,s,t)$ with a path $s\stackrel{\ast }{⟶}t$, has such path of length at most $Q(M)$, where $M=\text{size}(V,s,t)$. We split the proof into three cases:

1. 1.

   If $(V,s,t)$ is diagonal and wide, we exploit the fact that $3$-$\mathbb{Z}$-vass are polynomially length-bounded, and use diagonality and wideness to lift a short $\mathbb{Z}$-path into a path.

2. 2.

   If $(V,s,t)$ is diagonal but non-wide, we show that $(V,s,t)$ is length-equivalent to a geometrically 2-dimensional $3$-vass $(\overline{V},\overline{s},\overline{t})$ of polynomially larger size, namely $\text{Len}(V,s,t)=\text{Len}(\overline{V},\overline{s},\overline{t})$.

3. 3.

   Finally, if $(V,s,t)$ is non-diagonal, we show that $(V,s,t)$ is length-equivalent to a set of three geometrically 2-dimensional $3$-vass $\{(V_1,s_1,t_1),(V_2,s_2,t_2),(V_3,s_3,t_3)\}$, namely $\text{Len}(V,s,t)=\text{Len}(V_1,s_1,t_1)\cup \text{Len}(V_2,s_2,t_2)\cup \text{Len}(V_3,s_3,t_3)$ of polynomially larger size.

In the two latter cases we rely on the fact that geometrically 2-dimensional $3$-vass are polynomially length-bounded (Lemma 7). In consequence, $Q$ is to be the sum of polynomials claimed in the respective cases. In the sequel let $(V,s,t)$ be a fixed 1-component $3$-vass with $s\stackrel{\ast }{⟶}t$, where $s=p(w)$ and $t=p^{\prime }(w^{\prime })$.

By diagonality, $p(w)\stackrel{\pi }{⟶}p(w+\mathrm{\Delta })$ and $p^{\prime }(w^{\prime }+{\mathrm{\Delta }}^{\prime })\stackrel{{\pi }^{\prime }}{⟶}{p}^{\prime }(w^{\prime })$ for some $\mathrm{\Delta },{\mathrm{\Delta }}^{\prime }\in {({\mathbb{N}}_{>0})}^3$.

Let $P$ be a nondecreasing polynomial witnessing Lemma 8, i.e., $3$-$\mathbb{Z}$-vass are length-bounded by $P$. As there is a path $s\stackrel{\ast }{⟶}t$ in $V$, there is also a $\mathbb{Z}$-path $s\stackrel{\ast }{⟶}t$, and by Lemma 8 there is a $\mathbb{Z}$-path $s\stackrel{\sigma }{⟶}t$ of length at most $P(M)$. The maximal norm $N$ of $\mathbb{Z}$-configurations along $\sigma$ is thus bounded by $M\cdot P(M)$, as every step may update counters by at most $M$.

By diagonality, the configuration $p(w+\overrightarrow{1})$ is coverable in $V$ from $s$, and symmetrically the configuration $p^{\prime }(w^{\prime }+\overrightarrow{1})$ is coverable in $V^{\text{rev}}$ from $t$. Due to the upper bound of Rackoff [24, Lemma 3.4], there is a nondecreasing polynomial $R$ such that in every $3$-vass of size $m$, the length of a covering path is at most $R(m)$. Therefore the lengths of both paths $p(w)\stackrel{\pi }{⟶}p(w+\mathrm{\Delta })$ and $p^{\prime }(w^{\prime }+{\mathrm{\Delta }}^{\prime })\stackrel{{\pi }^{\prime }}{⟶}{p}^{\prime }(w^{\prime })$ in $V$, where $\mathrm{\Delta },{\mathrm{\Delta }}^{\prime }\in {({\mathbb{N}}_{>0})}^3$, may be assumed to be at most $R(M)$. We argue that there is a cycle from the source configuration $p(w)$ that increases $w$ by some multiplicity of ${\mathrm{\Delta }}^{\prime }$:

Before proving the lemma we use it to complete Case 1. We build a path $p(w)\stackrel{\ast }{⟶}{p}^{\prime }(w^{\prime })$ by concatenating $3$ paths given below. The first one is $\delta$ given by Lemma 10. Note that $\mathrm{\ell }$ is necessarily also bounded by $R{(M)}^{𝒪(1)}$. We replace $\mathrm{\ell }$ by its sufficiently large multiplicity to enforce $\mathrm{\ell }\ge M\cdot P(M)$, which makes the length of $\delta$ and $\mathrm{\ell }$ only bounded by $P(M)\cdot R{(M)}^{𝒪(1)}$. The multiplicity guarantees that the $\mathbb{Z}$-path $p(w)\stackrel{\sigma }{⟶}{p}^{\prime }(w^{\prime }),$ lifted by $\mathrm{\ell }\cdot {\mathrm{\Delta }}^{\prime }$, becomes a path:

The length of $\sigma$ is bounded by $P(M)$. Finally, let ${\delta }^{\prime }={({\pi }^{\prime })}^{\mathrm{\ell }}$ be the $\mathrm{\ell }$-fold concatenation of the cycle ${\pi }^{\prime }$:

The length of this path is bounded by $\mathrm{\ell }\cdot R(M)\le P(M)\cdot R{(M)}^{𝒪(1)}$. We concatenate the three paths, $\tau :=\delta ;\sigma ;{\delta }^{\prime }$, to get a required path

of length bounded by $P(M)\cdot R{(M)}^{𝒪(1)}$. It thus remains to prove Lemma 10 in order to complete Case 1.

Let ${\pi }_1$ be a cycle that visits all states (it exists since the considered vass is strongly connected), and let ${\mathrm{\Delta }}_1\in {\mathbb{Z}}^3$ be its effect. Relying on $\mathrm{\Delta }\in {({\mathbb{N}}_{>0})}^3$, take a sufficiently large multiplicity $m\in {\mathbb{N}}_{>0}$ so that $\tilde{\pi }={\pi }^m;{\pi }_1$ is a path with nonnegative effect. The path $\tilde{\pi }$ is a cycle and its effect is $\tilde{\mathrm{\Delta }}=m\cdot \mathrm{\Delta }+{\mathrm{\Delta }}_1\in {\mathbb{N}}^3$.

As ${\mathrm{\Delta }}^{\prime }\in {({\mathbb{N}}_{>0})}^3$, there is ${\mathrm{\ell }}^{\prime }\in {\mathbb{N}}_{>0}$ such that ${\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime }-\tilde{\mathrm{\Delta }}\in {({\mathbb{Q}}_{>0})}^3$, and hence, by wideness of $(V,s)$, we have ${\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime }-\tilde{\mathrm{\Delta }}\in \text{Cone}(V)$, namely

for some positive rationals $r_1,\mathrm{\dots },r_n\in {\mathbb{Q}}_{>0}$. By Carathéodory’s Theorem [26, p.94], ${\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime }-\tilde{\mathrm{\Delta }}$ is a combination of some $3$ vectors among $e_1,\mathrm{\dots },e_n$, say $e_1,e_2,e_3$:

for some positive rationals $r_1,r_2,r_3\in {\mathbb{Q}}_{>0}$. Therefore, the system of $3$ equations

with unknowns $\mathrm{\ell },r_1,r_2,r_3$, has a positive integer solution. We rewrite the system to:

Let ${\sigma }_i$ be simple cycle of effect $e_i$, for $i\in [1,3]$. Let $\sigma$ be a $\mathbb{Z}$-path that starts (and ends) in state $p$ and consists of $\mathrm{\ell }$-fold concatenation of the cycle ${\pi }_1$, with attached $(r_1)$-fold concatenation of ${\sigma }_1$, $(r_2)$-fold concatenation of ${\sigma }_2$, and $(r_3)$-fold concatenation of ${\sigma }_3$ (since ${\pi }_1$ visits all states, this is possible). The effect of $\sigma$ is the right-hand side of (2), and therefore $\sigma$ is a $\mathbb{Z}$-path from $p(w+\mathrm{\ell }m\cdot \mathrm{\Delta })$ to $p(w+\mathrm{\ell }{\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime })$:

It need not be a path in general, and therefore we are going to lift it. Let $k\in {\mathbb{N}}_{>0}$ be a multiplicity large enough so that $\sigma$ becomes a path when lifted by $(k-1)\mathrm{\ell }m\cdot \mathrm{\Delta }$, i.e., when starting in $p(w+k\mathrm{\ell }m\cdot \mathrm{\Delta })$, and also becomes a path when lifted by $(k-1)\mathrm{\ell }{\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime }$, i.e., when ending in $p(w+k\mathrm{\ell }{\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime })$. In this case, the $k$-fold concatenation of $\sigma$ is also a path:

since all points visited in the inner iterations of $\sigma$ are bounded from both sides by corresponding points visited in the first and the last iteration of $\sigma$. Precomposing this path with $p(w)\stackrel{{\pi }^{k\mathrm{\ell }m}}{⟶}p(w+k\mathrm{\ell }m\cdot \mathrm{\Delta })$ yields a path $p(w)\stackrel{\ast }{⟶}p(w+k\mathrm{\ell }{\mathrm{\ell }}^{\prime }\cdot {\mathrm{\Delta }}^{\prime })$, as required.

We now (roughly) bound the magnitudes of all items involved in the above reasoning by a constant power of $R(M)$. W.l.o.g. we may assume that the cycle ${\pi }_1$ uses every transition at most $\left|Q\right|\le M$ times, and thus both the length and norm of the effect of ${\pi }_1$ are bounded by $M^2$. In consequence, ${\pi }_1$ may decrease counters by at most $M^2$. Therefore $m\le M^2$, and norms of vectors $\mathrm{\Delta },{\mathrm{\Delta }}^{\prime },\tilde{\mathrm{\Delta }}$ are all bounded by $𝒪(M^3\cdot R(M))$. The effects $e_1,e_2,e_3$ of simple cycles ${\sigma }_1,{\sigma }_2,{\sigma }_3$ are at most $M$, as no transition repeats along a simple cycle. Therefore by Lemma 4, the system (2) has a solution $(\mathrm{\ell },r_1,r_2,r_3)$ of norm at most $D=𝒪{(M^3\cdot R(M))}^3=𝒪(M^9\cdot R{(M)}^3)$, and $\sigma$ has length at most $M^2\cdot D$ (since ${\pi }_1$ has length at most $M^2$). Therefore we deduce $k\le M^3\cdot D$, and hence the path (3) has length at most $M^5\cdot D^2$. In consequence of the above bounds, $k\mathrm{\ell }m\le M^5\cdot D^2$, and the final path $p(w)\stackrel{\ast }{⟶}p(w+k\mathrm{\ell }v)$ has length at most $R(M)\cdot M^5\cdot D^2\le 𝒪(R{(M)}^{30})\le R{(M)}^{𝒪(1)}$. $◀$

Every non-zero vector $a=(a_1,a_2,a_3)\in {\mathbb{Z}}^3$ defines an open half-space

where $a\diamond x=a_1{x}_1+a_2{x}_2+a_3{x}_3$ stands for the inner product of $x=(x_1,x_2,x_3)$ and $a$. As $V$ is assumed to be of geometric dimension 3, $\text{Cone}(V)$ is an intersection of open half-spaces:

Norms of vectors generating $\text{Cone}(V)$ – i.e., effects of simple cycles – are at most $M$, as no transition repeats along a simple cycle. Consider vectors $a$ orthogonal to some of the facets of $\text{Cone}(V)$, i.e., orthogonal to two of the vectors generating $\text{Cone}(V)$. The vector $a$ is thus an integer solution of a system of 2 linear equations with 3 unknowns, where absolute values of coefficients are bounded by $M$. By Lemma 4, there is such an integer solution with $\text{norm}(a)\le 𝒪(M^2)$. This completes the proof. $\mathrm{⊲}$

As $V$ is non-wide, due to Claim 11 we know that $\text{Cone}(V)$ is a non-empty intersection of half-spaces $H_a$. Therefore for some of these $H_a$ we have $\text{Cone}(V)\subseteq H_a$, i.e., all points $x\in \text{Cone}(V)$ have positive inner product $a\diamond x>0$. This implies that the value of inner product with $a$ may not decrease along any cycle in $V$:

In consequence, on every path $s\stackrel{\ast }{⟶}t$ the value of inner product with $a$ is polynomially bounded:

Let $s=p(w)$ and $t=p^{\prime }(w^{\prime })$, and let $b=a\diamond w$ and $b^{\prime }=a\diamond w^{\prime }$. Every path $s\stackrel{\ast }{⟶}t$ may be decomposed into simple cycles, whose effect may only preserve or increase the inner product with $a$, plus a short path without cycles, and hence without repetitions of a transitions. The effect of the latter path is thus in $[-M,M]$. Therefore, as inner product may at most multiply norms, every configuration $q(x)$ on a path from $s$ to $t$ satisfies $b-M\cdot D\le a\diamond x\le b^{\prime }+M\cdot D$. Knowing that $\text{norm}(a)\le D$, $\text{norm}(w),\text{norm}(w^{\prime })\le M$, and that inner product may at most multiply norms, by Claim 11 we deduce

and therefore $-2\cdot M\cdot D\le a\diamond x\le 2\cdot M\cdot D$, which implies the claim. $\mathrm{⊲}$

We define a geometrically 2-dimensional $3$-vass $\overline{V}=(\overline{Q},\overline{T})$ by extending states with the possible values of inner product with $a$ (bounded polynomially by Claim 13). We call $\overline{V}$ the ($a$, $B$)-trim of $V$. The set of states $\overline{Q}$ contains states of the form $q_b$, where $q\in Q$ and $-B\le b\le B$, with the intention that every configuration $c=q(x)$ of $V$ has a corresponding configuration $\overline{c}=q_b(x)$ in $\overline{V}$, where $a\diamond x=b$. Therefore, for each transition $(q,v,q^{\prime })\in T$ and for all $b,b^{\prime }\in [-B,B]$ such that $b+a\diamond v=b^{\prime }$, we add to $\overline{T}$ the transition

By construction, the effect of each cycle in $\overline{V}$ is orthogonal to $a$, and therefore $\text{Lin}(\overline{V})$ is included in a $2$-dimensional vector space. $\mathrm{⊲}$ Relying on Claim 13, paths $s\stackrel{\ast }{⟶}t$ in $V$ have corresponding paths in $\overline{V}$, and hence we get:

Finally, we argue that the size of $\overline{V}$ is bounded polynomially with respect to the size of $V$:

Recalling Claims 11 and 13, namely $\text{norm}(a)\le D$, $B=𝒪(M\cdot D)$, we deduce that transitions (4) contribute at most $(2B+1)M\le 𝒪(M\cdot B)$ to the size of $\overline{V}$. $\mathrm{⊲}$ We are now prepared to complete Case 2. Let $P$ be the polynomial witnessing Lemma 7, i.e., geometrically 2-dimensional $3$-vass are length-bounded by $P$. As $V$ has a path $s\stackrel{\ast }{⟶}t$, By Claim 15, $\overline{V}$ has a path $\overline{s}\stackrel{\ast }{⟶}\overline{t}$. By Lemma 7, $\overline{V}$ has thus a path $\overline{s}\stackrel{\ast }{⟶}\overline{t}$ of length at most $P(\text{size}(\overline{V}))$, i.e., relying on Claim 16, of length at most $P(𝒪(M^2\cdot D))=𝒪(P(M^4))$. By Claim 15 again, we get a path $s\stackrel{\ast }{⟶}t$ in $V$ of length $𝒪(P(M^4))$. This completes Case 2.

W.l.o.g. assume that $(V,s)$ is not forward-diagonal (otherwise replace $V$ by $V^{\text{rev}}$). Therefore for all states $q$ the configuration $s^{\prime }=q(w+(\overrightarrow{M+1}))$ is not coverable from $s=p(w)$. Indeed, using strong-connectedness of $V$, if $s^{\prime }$ were coverable from $s$ then the configuration $p(w+\overrightarrow{1})$ would be coverable form $p(w)$, by extending the covering path of $s^{\prime }$ with an arbitrary shortest path back to state $p$ (that cannot decrease a counter by more than $M$), which would contradict forward non-diagonality.

By Lemma 5, in every path from $s$, some coordinate $j\in [1,3]$ is bounded by $B:=P_3(M,M,M+1)$ (we take $M$ as an upper bound for $n$ and $N$, relying on $P_3$ being nondecreasing, and take $U=M+1$). This property allows us, intuitively speaking, to describe all the paths of $V$ by paths of three geometrically 2-dimensional $3$-vass $V_j$, for $j\in [1,3]$, where $V_j$ behaves exactly like $V$ except that dimension $j$ is additionally kept in state. Formally, let $V_j:=(Q_j,T_j)$, where

The source and target configurations in $V_j$ are $s_j=p_{w_j}(w)$ and $t_j=p_{w_j^{\prime }}^{\prime }(w^{\prime })$, and there is a tight correspondence between paths in $V$ and paths in $V_1,V_2,V_3$:

The size of each of $V_j$ is bounded polynomially with respect to the size of $V$:

Let $P$ be the polynomial witnessing Lemma 7. As $p(w)\stackrel{\ast }{⟶}{p}^{\prime }(w^{\prime })$ in $V$, by Claim 17 there is a path $p_{w_j}(w)\stackrel{\ast }{⟶}{p}_{w_j^{\prime }}^{\prime }(w^{\prime })$ in $V_j$ for some $j\in [1,3]$. Therefore, by Lemma 7 there is such a path of length at most $P(R(M))$ which, again using Claim 17, implies a path $p(w)\stackrel{\ast }{⟶}{p}^{\prime }(w^{\prime })$ in $V$ of the same length. This polynomial bound completes Case 3, and hence also the proof of Lemma 9.

Let $V=(V_1)u_1(V_2)u_2\mathrm{\dots }{u}_{k-1}(V_k)$ be a $k$-component $3$-vass that has a path $s=q(w)\stackrel{\ast }{⟶}{q}^{\prime }(w^{\prime })=t$. If $V$ is diagonal and wide, we use the pumping cycles $q(w)\stackrel{\ast }{⟶}q(w+\mathrm{\Delta })$ in $V_1$ and $q^{\prime }(w^{\prime }+{\mathrm{\Delta }}^{\prime })\stackrel{\ast }{⟶}{q}^{\prime }(w^{\prime })$ in $V_k$ to lift a $\mathbb{Z}$-path $s\stackrel{\ast }{⟶}t$, polynomially length-bounded due to Lemma 8, until it becomes a path (as in Case 1 in the proof of Lemma 9).

On the other hand, if $V$ is non-diagonal or non-wide, our strategy is to reduce the number of components by 1, and to rely on the induction assumption for $k-1$, by replacing the first component $V_1$ by one of finitely many geometrically 2-dimensional $3$-vass (as in Cases 2 and 3 of the proof of Lemma 9). Relying on the fact that the reachability sets in a geometrically 2-dimensional $3$-vass are semi-linear [11], the proof could go as follows (yielding however only the already known Tower upper bound [11]). Using any of the linear sets $L=a+P^{\ast }$ describing the set ${\text{Reach}}_{q_2}(V,s)$, where $q_2$ is the source state of the second component $V_2$, transform $V$ into a $(k-1)$-component $3$-vass $V^{\prime }$ by dropping the first component $V_1$ and the first bridge $u_1$, and by adding to the remaining $(k-1)$-component $3$-vass $(V_2)u_2\mathrm{\dots }{u}_{k-1}(V_k)$ the self-looping transitions $(q_2,r,q_2),$ one for every period $r\in P$. The source configuration of $V^{\prime }$ is $s^{\prime }=q_2(a)$, i.e., its vector is the base of $L$. The transformation preserves behaviour of $V$. In one direction, a path $s\stackrel{\ast }{⟶}{q}_2(x)\stackrel{\ast }{⟶}t$ in $V$ crossing through $q_2(x)$ for some $x\in L$ has a corresponding path $q_2(a)\stackrel{\ast }{⟶}{q}_2(x)\stackrel{\ast }{⟶}t$ in $V^{\prime }$. Conversely, each path $q_2(a)\stackrel{\ast }{⟶}{q}_2(x)\stackrel{\ast }{⟶}t$ in $V^{\prime }$ gives rise to a path $s\stackrel{\ast }{⟶}t$ in $V$, by replacing executions of the self-looping transitions $q_2(a)\stackrel{\ast }{⟶}{q}_2(x)$ (w.l.o.g. executed in the beginning), by a path $s\stackrel{\ast }{⟶}{q}_2(x)$ in $V_1$, bounded polynomially due to Lemma 9. However, $\text{size}(V^{\prime })$ may blow-up exponentially with respect to $\text{size}(V)$, as bases and periods of $L$ are only bounded exponentially, and therefore this approach could only yield a $k$-fold exponential bound on the length of the shortest path in $k$-component $3$-vass.

Polynomially approximable sets are designed as a remedy against the $k$-fold exponential blowup. The idea is to measure the norms of base and periods of a semi-linear set $L$ parametrically with respect to, intuitively speaking, the prospective length $B$ of a path $s^{\prime }\stackrel{\ast }{⟶}t$ in $V^{\prime }$. This allows us to control the blow-up of size of $V^{\prime }$, also parametrically with $B$, but requires going outside of semi-linear sets and considering their $B$-approximations, namely sets sandwiched between $a+P^{\le B}$ and $a+P^{\ast }$, good enough for correctness of the above-described transformation of $V$ to $V^{\prime }$. As the outcome, the exponent of our bound on length of the shortest path in $k$-component $3$-vass is, roughly speaking, square of the exponent of the respective bound in $(k-1)$-component $3$-vass. For $k$-component $3$-vass this yields exponent doubly-exponential in $k$, and hence the bound triply-exponential in $k$. The rigorous reasoning is given in the proof of Lemma 25 in Section 6.

Let $A,B\in \mathbb{N}$. By a $B$-approximation of a linear set $a+P^{\ast }\subseteq {\mathbb{N}}^d$ we mean any set $S\subseteq {\mathbb{N}}^d$ satisfying $a+P^{\le B}\subseteq S\subseteq a+P^{\ast }.$ A set $X\subseteq {\mathbb{N}}^d$ is ($A$, $B$)-approximately semi-linear if it is a finite union of:

• $\mathrm{■}$

  linear sets $a+P^{\ast }\subseteq {\mathbb{N}}^d$ with $\text{norm}(a)\le B\cdot A$ and $\text{norm}(P)\le A$; and

• $\mathrm{■}$

  $B$-approximations of linear sets $a+P^{\ast }\subseteq {\mathbb{N}}^d$ with $\text{norm}(a)\le A$ and $\text{norm}(P)\le A$.

Thus $X$ either includes $B$-approximation of a linear set $a+P^{\ast }$, whose norm of base is bounded by $A$, or $X$ includes a whole linear set $a+P^{\ast }$, whose norm of base is only bounded by $B\cdot A$. In both cases, norms of periods are bounded by $A$.

We say that a class $𝒞$ of $d$-vass is $F$-approximable for a function $F:\mathbb{N}\to \mathbb{N}$, if for every vass $(V,s)$ in $𝒞$, its state $q$, and $B\in \mathbb{N}$, the set ${\text{Reach}}_q(V,s)$ is ($F(M)$, $B$)-approximately semi-linear, where $M=\text{size}(V,s)$. The class $𝒞$ is polynomially approximable if it is $F$-approximable, for some nondecreasing polynomial $F$.