COMPLEXITY RESULTS FOR SAS(+) PLANNING

We have previously reported a number of tractable planning problems de fined in the SAS(+) formalism. This article complements these results by providing a complete map over the complexity of SAS(+) planning und er all combinations of the previously considered restrictions. We anal yze the complexity of both finding a minimal plan and finding any plan . In contrast to other complexity surveys of planning, we study not on ly the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS(+)-PUS problem is the m aximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the SAS(+)-US problem, which we prov e to be the maximal tractable problem in this case.