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
| CREATOR | Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-08708