关于STRIPS$_{1}^{1}$复杂性的中间结果

本文基于Bylander关于命题STRIPS规划计算复杂性的研究成果。他证明了当仅允许使用地面文字时，即使操作符仅限于两个前提条件和两个后置条件，确定是否存在计划的问题也是PSPACE完全的。尽管NP难性已被确认，但尚不清楚具有仅一个前提条件和一个效果的操作符的命题STRIPS是否为NP完全。本文探讨了STRIPS$^1_1$的小规模解假设是否成立，通过调用SAT求解器处理小实例、引入文字图并将其映射到Petri网来分析该问题。