Page 4 - 《软件学报》2026年第1期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(1):1−33 [doi: 10.13328/j.cnki.jos.007441] [CSTR: 32375.14.jos.007441] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
向量加法系统可达性问题复杂性下界研究综述

陈蔚骏 1 , 傅育熙 2 , 龙 环 2

1
(上海交通大学 软件学院, 上海 200240)
2
(上海交通大学 计算机科学与工程系, 上海 200240)
通信作者: 傅育熙, E-mail: fu-yx@cs.sjtu.edu.cn

摘 要: 并发与可扩展性是绝大多数复杂系统的关键性质. 作为并发建模的常用语言, Petri 网被大量应用于众多领
域. Petri 网的数学抽象, 即向量加法系统是计算机科学中的重要研究对象, 向量加法系统的可达性问题的算法与复
杂性刻画是过去 50 年理论计算机科学中最重要的问题之一. 对向量加法系统可达性问题的复杂性下界研究进行
系统而全面的总结与阐述, 主要内容包括: (1) 向量加法系统的定义、等价模型、向量加法系统的可达性问题; (2) 向
量加法系统可达性问题复杂性的研究进展; (3) 固定维度的可达性问题的下界证明方法及其之间的联系 ; (4) 当前的
研究瓶颈及有待解决的问题、未来的研究方向与挑战.
关键词: Petri 网; 向量加法系统; 可达性; 计算复杂性
中图法分类号: TP301

中文引用格式: 陈蔚骏, 傅育熙, 龙环. 向量加法系统可达性问题复杂性下界研究综述. 软件学报, 2026, 37(1): 1–33. http://www.jos.
org.cn/1000-9825/7441.htm
英文引用格式: Chen WJ, Fu YX, Long H. Survey on Complexity Lower Bound Research for Reachability Problem in Vector Addition
Systems. Ruan Jian Xue Bao/Journal of Software, 2026, 37(1): 1–33 (in Chinese). http://www.jos.org.cn/1000-9825/7441.htm

Survey on Complexity Lower Bound Research for Reachability Problem in Vector Addition
Systems

1
2
CHEN Wei-Jun , FU Yu-Xi , LONG Huan 2
1
(School of Software, Shanghai Jiao Tong University, Shanghai 200240, China)
2
(Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)
Abstract: Concurrency and scalability are fundamental properties of most complex systems. As a widely used formalism for modeling
concurrency, Petri nets have been applied across various fields. Their mathematical abstraction, the vector addition system (VAS), has
become a central object of study in theoretical computer science. The reachability problem of VAS, along with its algorithmic and
complexity characterizations, has been regarded as one of the most fundamental and long-standing challenges in the field over the last 50
years. This study presents a comprehensive survey of the research on the complexity lower bounds of the VAS reachability problem. The
definitions of VAS, their equivalent models, and the core verification problem, the reachability problem, are introduced. Known
completeness results concerning the complexity of the reachability problem are reviewed. For the fixed-dimension case, proof frameworks
based on multiplication triples and amplifiers are outlined, and the state-of-the-art achievements as well as core proof techniques are
summarized. Finally, the current research bottlenecks, major open problems, and future challenges are discussed.
Key words: Petri net; vector addition system (VAS); reachability; computational complexity

20 世纪中叶, 随着信息技术的进步, 通常的串行模型在为现实中各类复杂系统建模时常无法很好地满足可扩
[1]
展的需求. 为了解决此类问题, 1962 年 Petri 提出了一种网络建模方法. 他放弃了全局的状态控制而是使用许多子

* 基金项目: 国家自然科学基金 (62072299); 上海市科委“科技创新行动计划” (24BC3200500, 24BC3200300)
收稿时间: 2024-07-23; 修改时间: 2024-11-02; 采用时间: 2025-03-31; jos 在线出版时间: 2025-11-03
CNKI 网络首发时间: 2025-11-04