证明三维对称向量加法系统可达性问题为PSPACE完全。
Reachability in 3-VAS
- 通过构造复杂度下界，证明三维对称VAS可达性难题
- 结合已有上界，确认3/4维VAS可达性为PSPACE完全
- 适用于形式验证与自动推理领域的研究者
我们确定了固定低维度下（无状态）向量加法系统（VAS）中可达性问题的精确复杂度。在2至4维范围内，该问题的复杂度此前仅知介于NP与PSPACE之间。本文证明了对称向量加法系统在三维情形（3-VAS）中的可达性问题是PSPACE-hard的，这是通用3-VAS的一个受限片段。结合已有的PSPACE上界，本结果确立了3-VAS和4-VAS及其对称片段中可达性问题的复杂度均为PSPACE-complete。
原文摘要 · Abstract (English)
We settle the exact complexity of the reachability problem in (stateless) vector addition systems (VAS) in fixed low dimension. In dimensions 2-4 it has only been known to be sandwiched between NP and PSPACE. We prove PSPACE-hardness of the reachability problem for symmetric vector addition systems in dimension 3 (3-VAS), a restricted fragment of general 3-VAS. Combined with previously established PSPACE upper bounds, our result settles the complexity of the problem to be PSPACE-complete in 3-VAS and 4-VAS, as well as in their symmetric fragments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。