论文标题
在固定尺寸库中的可及性问题的下限
Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
论文作者
论文摘要
我们研究了固定尺寸的状态（vasses）的矢量添加系统的可及性问题的复杂性。我们提供四个下限，改善了当前已知的最新最新：\ np-bardness for Unary Flat $ 4 $ vasses（vasses in Dimension 4），2）\ pspace-hardness for Unary $ 5 $ - vasses，3）\ expspace-hardsess for binary $ 6 $ $ 6 $ - vasses＆4）\ 4）\ 4）\ tower $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8 $ 8
We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) \np-hardness for unary flat $4$-VASSes (VASSes in dimension 4), 2) \pspace-hardness for unary $5$-VASSes, 3) \expspace-hardness for binary $6$-VASSes and 4) \tower-hardness for unary $8$-VASSes.
