← All problems
Unverified

Complexity of Reachability in Fixed-Dimensional Continuous VASS

A dd-dimesional continuous VASS is a counter system, which consists of a finite set of states and dd counters, each of which can hold a non-negative rational number. A transition of such a machine consists of an integer vector v∈Zd\mathbf{v} \in \mathbb{Z}^d, which allows us to update the counters as follows: Upon taking this transition, we first select some non-zero fraction α∈(0,1]\alpha \in (0,1] and then add the vector α⋅v\alpha \cdot \mathbf{v} co-ordinate-wise to our current counter values. Since each counter can only hold a non-negative rational number, while adding the vector α⋅v\alpha \cdot \mathbf{v}, we have to ensure that no counter value becomes negative.

The reachability problem for continuous VASS is the problem of deciding whether a given source configuration of a continuous VASS can reach a given target configuration. It is known that this problem is NP-complete. When the dimension dd is fixed and all vectors are encoded in binary, it is known that the problem is NL-complete if d=1d = 1 and NP-complete if d≥2d \ge 2. However when dd is fixed and all vectors are encoded in unary, the complexity is unknown, which leads to the following question: What is the complexity of reachability in continuous VASS when the dimension dd is fixed?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu