Intermediate Results on the Complexity of STRIPS 1 1 {}_{1}^{1} Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel Abstract 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 pre-conditions 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 {}_{1}^{1} is true, calling a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets. Introduction STRIPS ( 12 ) , the acronym of the Stanford Research Institute Planning System, is one the earliest formalisms for action planning. The STRIPS planning language has greatly influenced later developments of the planning domain description language PDDL as proposed by McDermott ( 20 ), Fox and Long ( 13 ) or Hoffmann and Edelkamp ( 9 ), and has been compared to other finite-state variable planning such as SAS + ( 3 ; 21 ; 15 ) . Bylander ( 5 ) studied the complexity of STRIPS planning and showed that the problem of determining plan existence is PSPACE-complete, meaning that the decision problem can be solved using polynomial memory, and that every PSPACE-complete problem polynomially reduces to it. Bylander’s reduction proof uses an encoding of a Turing machine with STRIPS operators. PSPACE containment is derived through a divide-and-conquer planning strategy. An important research question is to establish fragments of STRIPS planning that have lower complexity, i.e., being polynomial or NP-complete. One famous fragment of STRIPS planning is delete relaxation ( 17 ) , which is known to be NP-complete. Bylander took a different route and asked what happens if the operators of a STRIPS problem are limited to at most p preconditions and e effects, giving rise to fragments STRIPS {}_{p}^{e} . Concretely, Bylander showed that STRIPS {}_{1}^{1} is NP-hard. This follows from his results for the NP-completeness of STRIPS {}_{1}^{1+} (e.g., the effect must be positive), and since that’s a special case of STRIPS {}_{1}^{1} NP-hardness follows. Later on, Jonsson et al. ( 18 ) proved that STRIPS {}_{2}^{1} is PSPACE-complete. In Chapter 5 they wrote: Bylander showed that the problem of plan existence is PSPACE-complete for STRIPS planning instances whose actions have one postcondition and unbounded number of preconditions (either positive or negative). He did not prove a result for a bounded number k of preconditions, but conjectured that plan existence falls into the polynomial hierarchy in a regular way, with the precise complexity determined by k . In this section we modify our previous reduction such that actions have at most two preconditions, thus showing that plan existence is PSPACE-complete for k=2 and proving Bylander’s conjecture to be wrong. . However, the exact complexity of STRIPS {}_{1}^{1} remains unknown, i.e. there is no proof of containment in NP nor for PSPACE-hardness. In this paper, we consider the following question for STRIPS {}^{1}_{1} : Given a set of n propositions (facts, atoms) is it possible to find a set of STRIPS actions of at most one precondition and one effect that generate shortest plans of exponential size in n ? This paper attempts to shed new light on this question. If there are exponentially long shortest plans, we would need exponential time generating them. While such EXP-TIME problems do not contradict polynomial space (as it was shown with the general STRIPS problem), by definition we could get closer to the assertion that the problem was not in NP. However, from an exponential lower bound on the plan length, we cannot directly infer that the problem was not in NP, as there might be other polynomial certificates. If at least one plan has polynomial length, then we can verify it in polynomial time, implying containment in NP. We aim at closing the gap from different sides: this paper gives proof insights and an AI assisted proof attempt, it introduces the literal graph and overlap tree with examples and observation on plan finding there. We recall a scaling system that leads to plans quadratic in the solution length, we prove with a SAT solver the maximum plan length for n=5 and n=6 is smaller than 2^{n} , we give mathematical derivations indicating that this will always be the case for larger values of n , we provide an LLM generated proof attempt and compilation schemes to conservative safe Petri nets. and cooperative directed MAPF. STRIPS {}_{1}^{1} Let V be a set of propositional variables. A literal l is a positive or negative variable in V , i.e. l=v or l=\bar{v} for some v\in V . A set of literals L is well-defined if and only if v\notin L or \bar{v}\notin L for each v\in V . A state s is a well-defined set of literals such that |s|=|V| . A set of literals L holds in a state s if and only if L\subseteq s . The result of applying a well-defined set of literals L to a state s is a new state s\oplus L=(s\setminus\bar{L})\cup L , where \bar{L}=\{\bar{l}\mid l\in L\} contains the negation of all literals in L . Given a set of propositional variables V , let L(V)=V\cup\bar{V} be the set of all literals on V . A STRIPS planning problem is a tuple \bm{d}=\langle V,A\rangle where V is a set of propositional variables and A is a set of actions. Each action a=\langle\mathrm{pre}(a),\mathrm{eff}(a)\rangle\in A has precondition \mathrm{pre}(a) and effect \mathrm{eff}(a) , both well-defined sets of literals in L(V) . Action a is applicable in state s if and only if \mathrm{pre}(a) holds in s and results in a new state s\oplus\mathrm{eff}(a) . Two states s_{I} and s_{G} induce a planning instance \bm{p}=\langle V,A,s_{I},s_{G}\rangle . A plan for \bm{p} is a sequence of actions \omega=\langle a_{1},\ldots,a_{k}\rangle such that \mathrm{pre}(a_{1}) holds in s_{I} and, for each 1