A Note on the Parameterised Complexity
of Coverability in Vector Addition Systems

Vector addition systems are a well-established model with a very simple definition: a $d$-dimensional vector addition system (VAS) [31] is a finite set $𝑽$ of vectors in ${\mathbb{Z}}^d$, which defines a step relation between configurations in ${\mathbb{N}}^d$: $𝒖{\to }_{𝑽}𝒖+𝒗$ for all $𝒖$ in ${\mathbb{N}}^d$ and $𝒗$ in $𝑽$, provided that $𝒖+𝒗$ is in ${\mathbb{N}}^d$. One usually interprets the $d$ coordinates of a configuration $𝒖\in {\mathbb{N}}^d$ as $d$ counters that may take non-negative integer values; then $𝑽$ represents a set of allowed updates to the counter values, which can be applied only if none of the counters becomes negative.

In spite of this apparent simplicity, vector addition systems can exhibit highly complex behaviours. Famously, their reachability problem is $\mathrm{𝖠𝖢𝖪𝖤𝖱𝖬𝖠𝖭𝖭}$-complete [35, 34, 13]: given as input a $d$-dimensional VAS $𝑽$, an initial configuration $𝒔\in {\mathbb{N}}^d$, and a target configuration $𝒕\in {\mathbb{N}}^d$, the reachability problem asks whether $𝒕$ is reachable from $𝒔\in {\mathbb{N}}^d$ in $𝑽$, i.e., whether $𝒔{\to }_{𝑽}^{\ast }𝒕$. This combination of a simple definition with rich behaviours makes vector addition systems – along with the equivalent model of Petri nets – well-suited whenever one needs to model systems managing multiple discrete resources, e.g., threads in concurrent computations, molecules in chemical reactions [3, 4], organisms in biological processes [5], etc., but also as a theoretical tool involved in establishing decidability and complexity statements for a variety of decision problems in logic, formal languages, verification, etc. [42, Section 5].

In this note, we are interested in a decision problem with a less extreme complexity: given the same input, the coverability problem asks whether there exists a coordinate-wise larger or equal configuration ${𝒕}^{\prime }⊒𝒕$ such that $𝒔{\to }_{𝑽}^{\ast }{𝒕}^{\prime }$. This relaxation of the reachability problem was first shown decidable by Karp and Miller [31], before being proven $\mathrm{𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤}$-hard by Lipton [36] and to belong to $\mathrm{𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤}$ by Rackoff [40].

Like reachability, coverability in vector addition systems inter-reduces with numerous decision problems, notably in relation to the automated verification of safety properties in concurrent or distributed systems [30, 29, 22, 16, 18, 23, 2, 6], as well as reasoning on data-aware logics or systems [15, 25, 1]. These applications have motivated a thorough investigation of the problem [31, 36, 40, 9, 33, 32, 44] and the development of several tools specifically targeted at solving it [19, 8, 24].

Rosier and Yen [41] refined Rackoff’s analysis to identify the contribution of several parameters to the final complexity of the coverability problem. Among those, the main parameter driving the complexity is the dimension, i.e., the number of counters of the system. Indeed, Rackoff obtains his result by showing a bound on the length of the shortest covering runs from the source to the target configuration, which is in $n^{2^{𝒪(d\log d)}}$ when parameterised by the dimension $d$, where $n$ is the size of the input encoded in unary. (While $\mathrm{𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤}$-completeness holds with both a unary and a binary encoding, the complexity landscape changes as soon as one isolates the dimension as a parameter).

This upper bound on the length of shortest covering runs in unary-encoded VAS was recently improved to $n^{2^{𝒪(d)}}$ by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Węgrzycki [32, Theorem 3.3], and this matches the $n^{2^{\mathrm{\Omega }(d)}}$ lower bound in the family of systems constructed by Lipton [36]. In turn, this upper bound on the length of the shortest covering runs entails that the coverability problem with a unary encoding can be solved either in non-deterministic space $2^{𝒪(d)}\cdot \log n$ or in deterministic time $n^{2^{𝒪(d)}}$ [32, Corollary 3.4]; moreover, the latter time bound is also achieved by the classical backward coverability algorithm [44, Corollary 4.5]. Finally, as also shown by Künnemann et al. through a parameterised reduction from the parameterised clique problem $𝗉\text{-}\mathrm{𝖢𝖫𝖨𝖰𝖴𝖤}$, this time bound is optimal if one assumes the Exponential Time Hypothesis: under the ETH, no algorithm running in deterministic time $n^{o(2^d)}$ for coverability may exist [32, Theorem 4.2].

Surprisingly, in spite of this long line of results focusing on coverability in vector addition systems, and in particular when isolating the dimension as a key parameter, the question of the parameterised complexity of the problem has not been considered (see Section 2.4 for literature on other parameterisations on Petri nets, which are not directly comparable).

From the viewpoint of parameterised complexity, when using a unary encoding, the $n^{2^{𝒪(d)}}$ deterministic time bounds from [32, 44] immediately yield that $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ is in $\mathrm{𝖷𝖯}$, while the parameterised reduction from $𝗉\text{-}\mathrm{𝖢𝖫𝖨𝖰𝖴𝖤}$ in [32] shows $𝖶[1]$-hardness (see Figure 1 for an overview of the parameterised complexity classes discussed in this note).

A long-standing open question on decision problems for VAS, already raised by Hack [26, page 172] and revived in recent years [28, 17, 12], is whether any meaningful statements can be made about the complexity for a fixed VAS. In this direction, Draghici, Haase, and Ryzhikov [17] have recently shown that there exists a fixed $𝑽$ such that the coverability problem (and thus also the reachability problem) for $𝑽$ with a binary encoding of the initial/target configurations is already $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard. This complexity of coverability in a fixed VAS is also related to a question on the length of shortest covering runs by Czerwiński [12]. A natural way to approach these questions within the framework of parameterised complexity is to ask about the complexity of coverability when parameterised by the size of the encoding of the system, which we denote by $\Vert 𝑽\Vert$.

This is an a priori easier problem than the one parameterised by the dimension, as there is a straightforward parameterised reduction from this problem to the one of coverability parameterised by dimension (see Remark 2.1).

Our main contribution in this note is to refine the bounds and pinpoint the exact parameterised complexity of $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$: the problem is $\mathrm{𝖷𝖭𝖫}$-complete under PL reductions with a unary encoding (see Section 3), and $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete under FPT reductions with a binary encoding (see Section 4). These results are mainly applications of the rich literature dedicated to the coverability problem in vector addition systems: the upper bounds stem from the $2^{𝒪(d)}\cdot \log n$ non-deterministic space bounds from Rackoff’s and subsequent works [40, 41, 32], while $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness with a binary encoding follows from the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of coverability in a fixed VAS [17, Corollary 2]. The $\mathrm{𝖷𝖭𝖫}$ lower bound is a new proof, which relies on a result of Wehar [46] on the intersection non-emptiness problem for finite automata. Importantly given the dearth of “natural” complete problems for these two parameterised complexity classes and in particular for $\mathrm{𝖷𝖭𝖫}$, these results significantly enrich the library of known complete problems, as most of the inter-reducible problems we mentioned earlier also have natural parameters that correspond to the dimension.

As a consequence of these results, we also conclude that $𝗉\text{-}\mathrm{𝗌𝗂𝗓𝖾}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ is $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete when using a binary encoding (see Section 4), and in $\mathrm{𝖷𝖭𝖫}$ when using a unary encoding (see Section 3). Our motivation here is to restate the questions about the complexity of coverability and reachability in fixed VAS [28, 17, 12] within the framework of parameterised complexity, which we discuss more extensively in Section 5.

A deterministic finite automaton (DFA) $𝒟=(\mathrm{\Sigma },Q,T,q^{\text{init}},F)$ over a finite alphabet $\mathrm{\Sigma }$, consists of a finite set $Q$ of states, a set $T\subseteq Q\times \mathrm{\Sigma }\times Q$ of transitions, an initial state $q^{\text{init}}\in Q$, and a set $F\subseteq Q$ of final states, with the restriction that, for every state $p\in Q$ and letter $\sigma \in \mathrm{\Sigma }$, there is at most one state $q\in Q$ such that $(p,\sigma ,q)\in T$. For a transition $t=(p,\sigma ,q)$; for a word $w={\sigma }_1{\sigma }_2\mathrm{\cdots }{\sigma }_n$ is a sequence $(q_0,{\sigma }_1,q_1),(q_1,{\sigma }_2,q_2)\mathrm{\cdots }(a_{n-1},{\sigma }_n,q_n)$; it is accepting if $q_n\in F$ is final. The language $L(𝒟)\subseteq {\mathrm{\Sigma }}^{\ast }$ recognised by $𝒟$ is the set of words for which there exists some accepting run. We shall assume that a DFA is specified by its adjacency matrix, and therefore that the size of a given DFA $𝒟=(\mathrm{\Sigma },Q,T,q^{\text{init}},F)$ is $|𝒟|\stackrel{\text{def}}{=}|Q|\cdot |\mathrm{\Sigma }|$.

Our interest for DFAs stems from their intersection non-emptiness problem, a well-known $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete problem, which when parameterised by the number of DFAs is one the very few known $\mathrm{𝖷𝖭𝖫}$-complete problems in the literature [46, Corollary 3.5].

The lower bound in Theorem 3.1 follows from the PL reduction from $𝗉\text{-}\mathrm{𝖨𝖭𝖳𝖤𝖱𝖲𝖤𝖢𝖳𝖨𝖮𝖭}\text{-}\mathrm{𝖭𝖮𝖭𝖤𝖬𝖯𝖳𝖨𝖭𝖤𝖲𝖲}(\mathrm{𝖣𝖥𝖠})$ to $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲𝖲})$ captured by the following statement.

Suppose ${𝒟}_i=(\mathrm{\Sigma },Q_i,T_i,q_i^{\text{init}},F_i)$ for every $1⩽i⩽k$. Without loss of generality, we shall assume that $s=|Q_1|=\mathrm{\dots }=|Q_k|$. It will also be convenient for us to number the states; $Q_i=\{q_{i,1},\mathrm{\dots },q_{i,s}\}$ and we may also assume without loss of generality that $q_i^{\text{init}}=q_{i,1}$.

We construct a VASS $𝒱$ with $2k$ counters that come in $k$ pairs: for each $i\in \{1,\mathrm{\dots },k\}$, there are counters ${𝗑}_{𝗂}$ and ${𝗒}_{𝗂}$ used to store the current state of automaton ${𝒟}_i$. Precisely, that the current state of ${𝒟}_i$ is $q_{i,j}$, for some $1⩽j⩽s$, is reflected by counter values ${𝗑}_{𝗂}=j$ and ${𝗒}_{𝗂}=s-j$. The construction of $𝒱$ ensures that, except for some intermediate configurations, the following invariant is maintained: for each $i\in \{1,\mathrm{\dots },k\}$, we have ${𝗑}_{𝗂}+{𝗒}_{𝗂}=s$ and ${𝗑}_{𝗂}⩾1$.

With this way of encoding of a selection of states of ${𝒟}_1,\mathrm{\dots },{𝒟}_k$, we emulate applying a transition of any ${𝒟}_i$ through a pair of transitions in $𝒱$ as follows. Suppose we would like to apply a transition of ${𝒟}_i$ that goes from $q_{i,a}$ to $q_{i,b}$, for some $a,b\in \{1,\mathrm{\dots },s\}$: then, we may apply two transitions in $𝒱$

• $\mathrm{■}$

  first, one that subtracts $a$ from ${𝗑}_{𝗂}$ and $s-a$ from ${𝗒}_{𝗂}$, and

• $\mathrm{■}$

  then, one that adds $b$ to $x_i$ and $s-b$ to ${𝗒}_{𝗂}$.

Thanks to the invariant, the first transition can be fired only if we indeed have ${𝗑}_{𝗂}=a$ and ${𝗒}_{𝗂}=s-a$ (and the state encoded by those counters is $q_{i,a}$), and firing it brings both counters to $0$. Then the second transition sets ${𝗑}_{𝗂}=b$ and ${𝗒}_{𝗂}=s-b$. Thus, firing the two transitions in $𝒱$ both verifies that the current state is $q_{i,a}$, and updates this state to $q_{i,b}$.

With this basic gadget understood, we may explain the overall construction of $𝒱$, depicted in Figure 3. We create two special states: the starting state $p$ and the ending state $q$. The initial configuration is $p(𝒖)$ where $𝒖\stackrel{\text{def}}{=}(1,s-1,\mathrm{\dots },1,s-1)$, which corresponds to setting every automaton ${𝒟}_i$ to its initial state. Next, for each $\sigma \in \mathrm{\Sigma }$ we construct a $\sigma$-section, which is essentially a loop that goes from $p$ back to $p$, and a checking section, which is essentially a path from $p$ to $q$. Thus, any run from $p$ to $q$ first loops some number of times through the $\sigma$-sections, and finally proceed through the checking section to $q$. The intention is that the effect of performing a loop through the $\sigma$-section, for some $\sigma \in \mathrm{\Sigma }$, is an update of the values of the counters of $𝒱$ that corresponds to performing a $\sigma$-transition in each of the automata ${𝒟}_1,\mathrm{\dots },{𝒟}_k$. This is done within $k$ consecutive parts of the $\sigma$-section, each responsible for updating the state of a different ${𝒟}_i$ using the gadgets described in the previous paragraph. Thus, choosing consecutive loops through the $\sigma$-sections corresponds to choosing consecutive letters of a word $w$ over $\mathrm{\Sigma }$, and simulating the runs of all the automata ${𝒟}_1,\mathrm{\dots },{𝒟}_k$ on $w$. Finally, we construct the checking section using a similar method so that it can be traversed if and only if each automaton ${𝒟}_i$ is in a final state; this verifies that $w$ is in the intersection of the languages of ${𝒟}_1,\mathrm{\dots },{𝒟}_k$. Again, the checking section consist of $k$ parts, each responsible for checking the state of a different ${𝒟}_i$. See Section 3.1 for an illustration of this construction.

We start by constructing the two special states $p$ and $q$. Next, for every $\sigma \in \mathrm{\Sigma }$ we construct the $\sigma$-section. It contains one part for each $i\in \{1,\mathrm{\dots },k\}$ defined as follows. Let $m_{\sigma ,i}$ be the number of $\sigma$-transitions in ${𝒟}_i$. Then we introduce $m_{\sigma ,i}+2$ many states: one starting state, one ending state, and one intermediate state for each $\sigma$-transition in ${𝒟}_i$. Furthermore, for every $\sigma$-transition $t=(q_{i,a},\sigma ,q_{i,b})$ in ${𝒟}_i$, we construct two transitions in $𝒱$: the first transition from the starting state to the intermediate state $q_t$ that updates the counters by subtracting $a$ from ${𝗑}_{𝗂}$ and $s-a$ from ${𝗒}_{𝗂}$ (and does not update the other counters); the second transition from the intermediate state $q_t$ to the ending state that updates the counters similarly by adding $b$ to ${𝗑}_{𝗂}$ and $s-b$ to ${𝗒}_{𝗂}$ (and does not update the other counters). Finally, we connect all the parts of the $\sigma$-section into a path as follows by adding for each $i\in \{1,\mathrm{\dots },k-1\}$, a counter-neutral (not changing the values of the counters) transition from the ending state of the $i$-th part to the starting state of the $(i+1)$-st part. The section is connected to the rest of the VASS by counter-neutral transitions from $p$ to the starting state of the first part, and from the ending state of the last part to $p$.

Next, we present the construction of the checking section, which amounts to constructing the $i$-th part, for each $i\in \{1,\mathrm{\dots },k\}$, each with two states: one starting state and one ending state. Further, we construct $|F_i|$ many transitions: one for each final state of ${𝒟}_i$. Precisely, for each final state $q_{i,f}$ of ${𝒟}_i$ (for some $f\in \{1,\mathrm{\dots },s\}$), we construct a transition in $𝒱$ from the starting state to the ending state that subtracts $f$ from ${𝗑}_{𝗂}$ and $s-f$ from ${𝗒}_{𝗂}$ (and does not update the other counters). It is important to note that this is only possible if ${𝗑}_{𝗂}=f$ and ${𝗒}_{𝗂}=s-f$ (i.e., when ${𝒟}_i$ is currently at $f$). Accordingly, the only possible way to go is through the $i$-th part of the checking section is if ${𝒟}_i$ is currently in a final state. We connect again all the parts of the checking section into a path by adding counter-neutral transitions from $p$ to the starting state of the first part, from the ending state of the last part to $q$, and from the ending state of the $i$-th part to the starting state of the $(i+1)$-st part, for each $i\in \{1,\mathrm{\dots },k-1\}$.

Finally, we set the initial configuration of $𝒱$ to $p(𝒖)$, where $𝒖$ sets ${𝗑}_{𝗂}=1$ and ${𝗒}_{𝗂}=s-1$ for every $i\in \{1,\mathrm{\dots },k\}$, and the target configuration to $q(\mathrm{𝟎})$ (so $𝒗=\mathrm{𝟎}$). The following claim verifies the correctness of the reduction.

Let us finally observe that the VASS $𝒱$ can be constructed in space $𝒪\left(\log (k)+\log (|{𝒟}_1|+\mathrm{\dots }+|{𝒟}_k|)\right)$, because the states and transitions of $𝒱$ can be computed using three pointers

• $\mathrm{■}$

  $i\in \{1,\mathrm{\dots },k\}$ for the current automaton ${𝒟}_i$,

• $\mathrm{■}$

  $\sigma \in \mathrm{\Sigma }$ for the current letter, and

• $\mathrm{■}$

  $q_{i,a}\in Q_i$, which together with $\sigma$ determines the transition $(q_{i,a},\sigma ,q_{i,b})$ in the deterministic automaton ${𝒟}_i$.

This sums up to $𝒪(\log (k\cdot (|\mathrm{\Sigma }|\cdot |Q_1|+\mathrm{\dots }+|\mathrm{\Sigma }|\cdot |Q_k|))$ space for the reduction; as furthermore $|{𝒟}_i|=|\mathrm{\Sigma }|\cdot |Q_i|$ for each $i$, this is indeed the same as $𝒪\left(\log (k)+\log (|{𝒟}_1|+\mathrm{\dots }+|{𝒟}_k|)\right)$ space. $◀$

We may now conclude this section by proving Theorem 3.1.

Membership in $\mathrm{𝖷𝖭𝖫}$ follows from the algorithm in nondeterministic space $2^{𝒪(d)}\cdot \log n$ from Corollary 2.5 (c.f. [32, Corollary 3.4]). The $\mathrm{𝖷𝖭𝖫}$-hardness follows from ˜2.2 and the PL reduction described by Lemma 3.3 along with the $\mathrm{𝖷𝖭𝖫}$-hardness of $𝗉\text{-}\mathrm{𝖨𝖭𝖳𝖤𝖱𝖲𝖤𝖢𝖳𝖨𝖮𝖭}\text{-}\mathrm{𝖭𝖮𝖭𝖤𝖬𝖯𝖳𝖨𝖭𝖤𝖲𝖲}(\mathrm{𝖣𝖥𝖠})$ proven by Wehar [46, Corollary 3.5]. $◀$

Regarding the upper bound, recall that the coverability problem can be solved in non-deterministic space $2^{𝒪(d)}\cdot \log n$ where $d$ is the dimension and $n=\mathrm{𝑠𝑖𝑧𝑒}(𝑽)+{\Vert 𝒔\Vert }_1+{\Vert 𝒕\Vert }_1$ is the size of the input in unary [32, Corollary 3.4]. This in turn provides an algorithm working in non-deterministic space $2^{𝒪(d)}\cdot N$ where $N=\mathrm{𝑏𝑖𝑡𝑠𝑖𝑧𝑒}(𝑽)+d\left({\log }_2({\Vert 𝒔\Vert }_{\mathrm{\infty }}+1)+{\log }_2({\Vert 𝒕\Vert }_{\mathrm{\infty }}+1)\right)$ is the size of the input in binary, showing that $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ is in $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. By the parameterised reduction from Remark 2.1, this also shows that $𝗉\text{-}\mathrm{𝗌𝗂𝗓𝖾}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ is in $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$.

Regarding the lower bound, [17, Corollary 2] shows that there exists a fixed VASS ${𝒱}_0$ (thus of fixed size, and actually of dimension $6$) such that the coverability problem for ${𝒱}_0$ is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard under the assumption that the starting and the target configuration are encoded in binary. By ˜2.2, there is a fixed VAS ${𝑽}_0$ (of dimension $9$) with the same property, thus showing that $𝗉\text{-}\mathrm{𝗌𝗂𝗓𝖾}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ and $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ are $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard under FPT reductions.¹¹1The $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of $𝗉\text{-}\mathrm{𝖽𝗂𝗆}\text{-}\mathrm{𝖢𝖮𝖵𝖤𝖱𝖠𝖡𝖨𝖫𝖨𝖳𝖸}(\mathrm{𝖵𝖠𝖲})$ also follows from the fact that coverability in binary-encoded $2$-VASS is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard [20, 7], which implies that coverability in binary-encoded $5$-VAS is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard. $◀$

A consequence is that, while coverability with either parameterisation is in $\mathrm{𝖷𝖯}$ when encoded in unary, if the problem with a binary encoding were to belong to $\mathrm{𝖷𝖯}$, then $𝖯=\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. Indeed, if this were the case, then coverability in the fixed VAS ${𝑽}_0$ provided by [17, Corollary 2] would be in $𝖯$.

Quite a few of these questions have negative answers. In the case of parameterisation by dimension, we have the following:

• $\mathrm{■}$

  A positive answer to (CP) would entail $\mathrm{𝖷𝖭𝖫}\subseteq \mathrm{𝖥𝖯𝖳}$ in the case of a unary encoding by Theorem 3.1, which would bring in particular a collapse of the $𝖶$- and $𝖠$-hierarchies down to $\mathrm{𝖥𝖯𝖳}$, because $\mathrm{𝖠𝖶}[\mathrm{𝖲𝖠𝖳}]\subseteq {[\mathrm{𝖷𝖭𝖫}]}^{\mathrm{𝖿𝗉𝗍}}$ by [11, Proposition 23] (recall Figure 1). It would entail $\mathrm{𝖥𝖯𝖳}=\mathrm{𝗉𝖺𝗋𝖺}\text{-}\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ in the case of a binary encoding by Theorem 4.1, which is if and only if $𝖯=\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$.

• $\mathrm{■}$

  (CL) has an unconditional negative answer regardless of the choice of encoding by ˜2.6: Lipton’s construction [36] yields a family of inputs to the coverability problem in dimension $𝒪(d)$ where the shortest witnesses have length at least $n^{2^d}$.

• $\mathrm{■}$

  (RP) and (RL) have a negative answer regardless of the choice of encoding since the reachability problem in dimension $𝒪(d)$ is hard for the fast-growing complexity class ${𝐅}_d$ [34, 13], and the shortest witnesses in their instances have length at least $F_d(n)$ where $F_d$ is the $d$th fast-growing function (see [43] for a reference on fast-growing complexity).

Turning our attention to parameterisation by size and a binary encoding, we have:

• $\mathrm{■}$

  A positive answer to either (CP) or (RP) would again entail $𝖯=\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ by Theorem 4.1.

• $\mathrm{■}$

  Finally, (CL) and (RL) have a negative answer, since with a binary encoding and a fixed VAS of constant size, one can easily ensure that shortest witnesses have length exponential in the size of the input.

Our questions are therefore only relevant in the case of a unary encoding and a parameterisation by size. In that setting, (CL) is essentially Question 3 by Czerwiński [12]²²2Hack observed [26, page 171] that shortest coverability witnesses were of linear length if, in addition to the VAS, the initial configuration was fixed (thanks to the coverability tree construction [31]). On a similar note, Rackoff’s analysis [40] even yields a constant bound on the length of shortest coverability witnesses if we fix both the VAS and the target configuration. and (RL) is essentially a conjecture due Hack [26, page 172] that has recently been restated by Jecker [28]. Both of these questions were originally phrased in terms of an $𝒪(n)$ upper bound in a fixed VAS; here we cast them in the terminology of parameterised complexity.

Those two questions are connected to (CP) and (RP): an FPT length on shortest witnesses implies the existence of a nondeterministic algorithm that guesses and checks this witness. With a unary encoding, this entails that the problem is in $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖭𝖯}$, while with a binary encoding, this entails that the problem is in $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. Recall that all we know at the moment are $\mathrm{𝖷𝖭𝖫}$ and $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ upper bounds for coverability with unary and binary encoding, and no reasonable upper bounds for reachability. Thus (CL) and (RL) provide an original angle of attack on (CP) and (RP), respectively, and a positive answer would yield

• $\mathrm{■}$

  the $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-completeness of reachability parameterised by size with a binary encoding, and

• $\mathrm{■}$

  an indication that the complexity of the problems parameterised by size with a unary encoding is likely lower than $\mathrm{𝖷𝖭𝖫}$ or $\mathrm{𝗉𝖺𝗋𝖺}$-$\mathrm{𝖭𝖯}$.

In summary, we believe that (CP) and (RP) are excellent open questions in parameterised complexity that deserve further investigation, whereas (CL) and (RL) are auxiliary conjectures whose resolution might be very insightful for (CP) and (RP).

As a further indication on the easiness of coverability and reachability parameterised by size with a unary encoding, note that in a fixed VAS ${𝑽}_0$, the coverability problem and the reachability problem are sparse languages, meaning that there exists a polynomial $p$ such that, for all $n$, the number of instances $x$ of the language of length $|x|=n$ is bounded by $p(n)$. Indeed, as ${𝑽}_0$ and thus its dimension $d$ are fixed, there are at most $\left(\genfrac{}{}{0pt}{}{n}{2d}\right)⩽n^{2d}$ possible pairs of initial and target configurations such that ${\Vert 𝒔\Vert }_1+{\Vert 𝒕\Vert }_1=n$. This tells us that if there exists a fixed ${𝑽}_0$ such that either coverability or reachability for ${𝑽}_0$ with unary encoding is $\mathrm{𝖭𝖯}$-hard, then $𝖯=\mathrm{𝖭𝖯}$ by Mahaney’s Theorem [37, Theorem 3.1]. Similarly, $\mathrm{𝖭𝖫}$-hardness entails $𝖫=\mathrm{𝖭𝖫}$ [10, Corollary 3].