Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.08708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915786346463232 |
|---|---|
| author | Edelkamp, Stefan Fink, Jiří Gregor, Petr Jonsson, Anders Nebel, Bernhard |
| author_facet | Edelkamp, Stefan Fink, Jiří Gregor, Petr Jonsson, Anders Nebel, Bernhard |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08708 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Intermediate Results on the Complexity of STRIPS$_{1}^{1}$ Edelkamp, Stefan Fink, Jiří Gregor, Petr Jonsson, Anders Nebel, Bernhard Artificial Intelligence 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. |
| title | Intermediate Results on the Complexity of STRIPS$_{1}^{1}$ |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2602.08708 |