{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T05:26:53Z","timestamp":1740202013078,"version":"3.37.3"},"reference-count":0,"publisher":"IOS Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"abstract":"<jats:p>There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem have been thoroughly analysed in this respect. We provide a number of upper and lower bound results for both plan satisfiability (PSAT) and length-optimal planning (LOP), with an emphasis on monotone planning (where actions have only positive effects) which is used in, for instance, h+and similar heuristics. Let v and a be the number of variables and actions, respectively. We consider both restrictions on the number and polarity of preconditions and effects of actions and the PUBS restrictions in SAS+. For all such classes, we show that PSAT and LOP is either tractable or cannot be solved in subexponential time 2o&amp;lpar;v&amp;rpar;or time 2o&amp;lpar;a&amp;rpar;, unless the so-called Exponential Time Hypothesis (ETH) is false. There is also a sharp transition: monotone LOP can be solved in time 2o&amp;lpar;v&amp;rpar;ifbut not if a&amp;isin;&amp;Omega;&amp;lpar;v&amp;rpar;. We also study upper bounds and discuss the trade-off between time and space, providing a polynomial-space algorithm for monotone LOP that beats depth-first search in most cases. This raises the important question how lower bounds are affected by polynomial space restrictions.<\/jats:p>","DOI":"10.3233\/978-1-61499-672-9-716","type":"book-chapter","created":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:26:53Z","timestamp":1740133613000},"source":"Crossref","is-referenced-by-count":0,"title":["Upper and Lower Time and Space Bounds for Planning"],"prefix":"10.3233","author":[{"family":"B&auml;ckstr&ouml;m Christer","sequence":"additional","affiliation":[]},{"family":"Jonsson Peter","sequence":"additional","affiliation":[]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2016"],"original-title":[],"deposited":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:53:36Z","timestamp":1740135216000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospressISBN&isbn=978-1-61499-671-2&spage=716&doi=10.3233\/978-1-61499-672-9-716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/978-1-61499-672-9-716","relation":{},"ISSN":["0922-6389"],"issn-type":[{"value":"0922-6389","type":"print"}],"subject":[],"published":{"date-parts":[[2016]]}}}