Intermediate Results on the Complexity of STRIPS 1 1 {}_{1}^{1}

Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel · 2026

Read Intermediate Results on the Complexity of STRIPS 1 1 {}_{1}^{1} by Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08708.txt.

Description

Planning with STRIPS operators is famously hard, but the boundary between hard and easy remains fuzzy for the tiniest operators. Stefan Edelkamp and four co-authors investigate STRIPS with one precondition and one effect per operator, a case where NP-completeness is still unknown. Their arXiv paper builds on Bylander's classic results for larger operators.

Bylander showed plan existence is PSPACE-complete with two preconditions and two effects, even for ground literals. The authors probe the one-and-one case with SAT solvers on small instances, a literal graph construction, and a mapping to Petri nets. Readers get intermediate results on a small-solution hypothesis that could reshape understanding of minimal planning complexity.

Catalog record

CREATORStefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-08708

Browse the full library · About the Tower of Babel