@techreport{R-93-34,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-93-34+ps},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-93-34+abstr},
ABSTRACT = {We have previously reported a number of tractable planning problems
defined in the \SASx\ formalism.
This \paper\  complements these results by providing a complete map 
over the complexity of \SASx\ planning
under all combinations of the previously considered restrictions.
We analyze the complexity both of finding a minimal plan and of finding any
plan.
In contrast to other complexity surveys of planning we  study not only
the complexity of the 
decision problems but also of the 
generation problems.
We prove that the \SASx-PUS problem is the maximal 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 \SASx-US problem, which we prove to be the maximal tractable
problem in this case.
},
TITLE = {Complexity Results for SAS+ Planning},
AUTHOR = {Christer B{\"a}ckstr{\"o}m and Berhard Nebel},
EMAIL = {chrba@ida.liu.se},
YEAR = {1993},
NUMBER = {R-93-34},
INSTITUTION = ida,
ADDRESS = idaaddr,
IDANR = {LiTH-IDA-R-93-34},
NOTE = {A short version of this report appears in the Proceedings of the 13th International Conference on Artificial Intelligence, Chambery, France, Aug 29 - Sep 3, 1993}