Page 12 - 《软件学报》2026年第1期
P. 12

陈蔚骏 等: 向量加法系统可达性问题复杂性下界研究综述                                                        9


                  2.1   一进制编码下的可达性问题

                    1  维  VASS  和  2  维  VASS  可达性下界相对容易. 例  2  中给出了如何将   VASS  转换为带向量标签的多重图. 事
                 实上传统有向图可以看作是          0-VASS  模型实例  (即只有状态迁移关系); 类似地, d-VASS       模型亦可看作     (d+1)-VASS
                 模型的实例. 如前所述, 我们用        ⩽ L 、 ⩽ p  分别表示对数空间归约和多项式时间归约, 用          PATH  表示图上的可达性问
                 题. 则有: PATH   ⩽ L  0-VASS reachability   ⩽ L  1-VASS reachability  ⩽ L  2-VASS reachability. 其中, PATH  是著名的  NL-完备
                 问题, 它给出了这些问题的下界.
                    在上界方面, Blondin  等人  [21] 证明了如下引理.
                    引理   4 [21] . 对任意  2-VASS   V = (2,Q,T), 若   p(u)→ V q(v), 则存在长度为  (|V| 1 +u+v) O(1)   的证据  π ∈ T  ∗   使得
                     π
                 p(u) → q(v).
                    此引理表明在      2-VASS   V  中, 若从初始状态   p(u) 可以到达某个状态    q(v), 则一定存在一个“短”的可达证据         π,
                            V、u、v 的一进制编码长度的多项式. 这个结论使得我们可以用非确定图灵机猜测一条长度受限的
                 其长度是关于
                 运行, 并检验该路径是否是合法的可达路径, 并且此过程至多需要使用对数量级的空间. 因此一进制编码下的
                 2-VASS  可达性问题在    NL  中. 这也是  Blondin  等人在该项工作中的主要贡献. 这些结论总结如下.
                    定理  1 [18] . 一进制编码下, 1-VASS  和  2-VASS  的可达性问题都是  NL-完备的.

                  2.2   二进制编码下的可达性问题
                    二进制编码下, 低维      VASS  可达性证据长度及用于归约的问题如表              2  所示. 其中, 1-VASS  的证据长度数据来
                 自文献   [22], 2-VASS  的证据长度数据来自文献     [21].

                                                   (⩽ 2)-VASS 可达性证据长度及用于归约的问题
                                  表 2 二进制编码下

                                关键算法性质                (普通或测零) 1-VASS              2-VASS
                                  证据长度                     2 poly(n)               2 poly(n)
                                  归约问题                   子集和问题                   子集和博弈

                  2.2.1    上界证明技术
                    此部分完备性结论的上界证明较为复杂精细, 由于本文主要聚焦于                       VASS  可达性问题复杂性下界, 故在此仅
                 对证明思路做简要概述, 读者可以参考原文             [23] 及一些综述  [16] 进一步了解相关证明细节.
                    引理  4  本质上是一个与编码方案无关的命题. 若我们将               2-VASS  可达性问题中的所有向量编码为二进制, 则
                     π  的长度是问题输入规模的指数量级. 同理使用非确定图灵机逐步猜测-验证方法, 可证该编码方案下
                 证据
                 2-VASS  可达性问题在    PSPACE  中. 然而, 这一简单的思路不适用于          1-VASS  的可达问题上界的推导. 这是因为
                 1-VASS  并不能得到比指数更好的可达证据长度上界. 要证明该问题在                   NP  中, 需要寻找更简洁的证据表示方法.
                 Haase 等人的思路   [23] 是将  VASS  看作流图  (flow graph) 并使用  Parikh  像  (Parikh image) 来表示一条路径. 该方法仅
                 记录每条边出现的次数        (而不记录具体的出现次序). 要注意的是, 一个满足欧拉条件的                  Parikh  像可以导出一段迁
                 移序列, 但并不保证一定能导出一条“合法”的              VASS  的运行: 还需要判断该过程中向量值是否始终落在自然数集
                   N 中. 仅有满足某些特定条件的         Parikh  像可以高效地验证是否存在一条对应的证据, 这类             Parikh  像被称作可达
                 合
                 证书  (reachability certificate).
                    直观上, 1-VASS  有独特的算法性质: 向量仅有一个维度, 这使得各类操作无须考虑维度之间的相互影响. Haase
                 等人  [23] 借此证明了  1-VASS  具有可泵性   (pumpability), 并进一步说明每个可达的问题实例都存在形如             π 1 ◦π 2 ◦π 3
                              π i  的长度至多为指数, 并均可以通过可达证书表征. 因此最终非确定算法只需猜测                      3  段对应的可
                 的证据. 其中, 各
                 达证书并进行高效验证即可, 这证明了             1-VASS  可达性问题在    NP  中. 值得注意的是, Haase   等人的证明是基于
                 1-计数器机器进行的. 而由抽屉原理, 测零            1-VASS  中一次没有重复格局的运行至多进行              |Q|  次测零. 即测零
                 1-VASS  可达性问题可以转换为线性个         (无测零) 1-VASS  的可达性问题. 故在只有一个计数器的情形下, 能否测零
                 不影响可达性问题的复杂性.
   7   8   9   10   11   12   13   14   15   16   17