探究单条件单效果规划的复杂性，验证其NP完全性猜想
Intermediate Results on the Complexity of STRIPS$_{1}^{1}$
- 用SAT求解器处理小规模实例，验证复杂性假设
- 构建字面量图并映射为佩特里网，揭示结构特性
- 为规划理论提供新分析工具，适合逻辑与复杂性研究者
本文基于Bylander对命题型STRIPS规划计算复杂性的研究。他证明：当仅允许使用基元文字时，即使操作符限制在两个前提和两个后置条件，判断计划存在性仍是PSPACE完全的。虽然已确定NP难性，但尚不清楚仅含一个前提和一个效果的操作符的命题型STRIPS是否为NP完全。本文通过调用SAT求解器处理小规模实例，引入字面量图，并将其映射为佩特里网，以探讨这一小型解假设在STRIPS₁¹中的正确性。
原文摘要 · Abstract (English)
This paper is based on Bylander's results on the computational complexity of propositional STRIPS planning. He showed that when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. While NP-hardness is settled, it is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete. We shed light on the question whether this small solution hypothesis for STRIPS$^1_1$ is true, calling a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。