Complexity of Reachability in Fixed-Dimensional Continuous VASS
A -dimesional continuous VASS is a counter system, which consists of a finite set of states and counters, each of which can hold a non-negative rational number. A transition of such a machine consists of an integer vector , which allows us to update the counters as follows: Upon taking this transition, we first select some non-zero fraction and then add the vector co-ordinate-wise to our current counter values. Since each counter can only hold a non-negative rational number, while adding the vector , 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 is fixed and all vectors are encoded in binary, it is known that the problem is NL-complete if and NP-complete if . However when 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 is fixed?
