A multiparameter analysis of the boundedness problem for vector addition systems

摘要

Let VASS(k, l, n) denote the class of k-dimensional n-state Vector Addition Systems with States, where the largest integer mentioned, in an instance, can be represented in l bits. Using a modification of the technique used by C. Rackoff (Theoret. Comput. Sci.6 (1978), 223–231) we show that the Boundedness Problem (BP), for VASS(k, l, n), can be solved in O((l + log n)∗2c∗k∗logk) nondeterministic space. By modifying R. Lipton's (“The Reachability Problem Requires Exponential Space,” Report No. 62, Department of Computer Sciences, Yale University, Jan. 1976) result, a lower bound is then shown of O((l + log n)∗2c∗k) non-deterministic space. Thus, the upper bound is optimal with respect to parameters l and n, and is nearly optimal with respect to the parameter k. This yields an improvement over the result of Rackoff, especially when compared with the lower bound of Lipton. This is because the lower bound, of O(2c∗k) space, was essentially given for VASS(k, 1, 1). Now Rackoff's corresponding upper bound, just for the instances of VASS(k, 1, 1) constructed by Lipton, is no better than O(2c∗k2log k) space. (In general, it can get much worse.) Our result, however, yields an upper bound of O(2c∗k∗log k), over the entire class. We also investigate the complexity of this problem for small, but fixed, values of k. We show that the BP is PSPACE-complete for four-dimensional VASSs, and NP-hard for two-dimensional VASSs. The above results can then be extended for the case without states. In particular, we are able to show that the BP is NP-hard for VASS(3, l, 1) and PSPACE-complete for VASS(4, l, 1). Extensions to related problems (e.g., covering and reachability) are also discussed.