一句话：证明向量加法系统/ Petri 网的可达性问题属于原始递归复杂度类，即位于 Grzegorczyk 层级之内。
论文研究向量加法系统（等价于 Petri 网）的可达性问题：给定初始配置和目标配置，判断是否存在合法执行序列到达目标。这是并发理论中一个自 1960 年代以来长期未决的核心复杂性问题。作者将可达性问题与 Grzegorczyk 层级（原始递归函数层级）建立联系，利用递归论中的层级工具，构造性地证明该问题是原始递归的，即存在一个原始递归算法判定可达性。这一结果给出了该问题的一个可计算上界，表明其复杂度位于原始递归函数层级之内，从而在长达数十年的开放问题上取得重要进展。
Vector addition systems with states, or equivalently vector addition systems, or Petri nets are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem is reachability: whether from a given initial configuration there exists a sequence of valid execution steps that reaches a given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of computation.
DOI 原文 ·
@inproceedings{paperbot5521,
title = {When Reachability Meets Grzegorczyk},
author = {Jérôme Leroux},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394732}
}