@inproceedings{bylander_complexity_1991,
	title = {Complexity {Results} for {Planning}},
	abstract = {I describe several computational complexity results for planning, some of which identify tractable planning problems. The model of planning, called "propositional planning," is simple—conditions within operators are literals with no variables allowed. The different plan­ ning problems are defined by different restrictions on the preconditions and postconditions of operators. The main results are: Proposi­ tional planning is PSPACE-complete, even if operators are restricted to two positive (nonnegated) preconditions and two postconditions, or if operators are restricted to one postcondi­ tion (with any number of preconditions). It is NP-complete if operators are restricted to positive postconditions, even if operators are restricted to one precondition and one posi­ tive postcondition. It is tractable in a few re­ stricted cases, one of which is if each opera­ tor is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a subproblem of this re­ stricted planning problem.},
	language = {en},
	booktitle = {Automated {Reasoning}},
	author = {Bylander, Tom},
	year = {1991},
	pages = {6},
}

{"_id":"BpPs2kHsehzE4iAhL","bibbaseid":"bylander-complexityresultsforplanning-1991","author_short":["Bylander, T."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Complexity Results for Planning","abstract":"I describe several computational complexity results for planning, some of which identify tractable planning problems. The model of planning, called \"propositional planning,\" is simple—conditions within operators are literals with no variables allowed. The different plan­ ning problems are defined by different restrictions on the preconditions and postconditions of operators. The main results are: Proposi­ tional planning is PSPACE-complete, even if operators are restricted to two positive (nonnegated) preconditions and two postconditions, or if operators are restricted to one postcondi­ tion (with any number of preconditions). It is NP-complete if operators are restricted to positive postconditions, even if operators are restricted to one precondition and one posi­ tive postcondition. It is tractable in a few re­ stricted cases, one of which is if each opera­ tor is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a subproblem of this re­ stricted planning problem.","language":"en","booktitle":"Automated Reasoning","author":[{"propositions":[],"lastnames":["Bylander"],"firstnames":["Tom"],"suffixes":[]}],"year":"1991","pages":"6","bibtex":"@inproceedings{bylander_complexity_1991,\n\ttitle = {Complexity {Results} for {Planning}},\n\tabstract = {I describe several computational complexity results for planning, some of which identify tractable planning problems. The model of planning, called \"propositional planning,\" is simple—conditions within operators are literals with no variables allowed. The different plan­ ning problems are defined by different restrictions on the preconditions and postconditions of operators. The main results are: Proposi­ tional planning is PSPACE-complete, even if operators are restricted to two positive (nonnegated) preconditions and two postconditions, or if operators are restricted to one postcondi­ tion (with any number of preconditions). It is NP-complete if operators are restricted to positive postconditions, even if operators are restricted to one precondition and one posi­ tive postcondition. It is tractable in a few re­ stricted cases, one of which is if each opera­ tor is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a subproblem of this re­ stricted planning problem.},\n\tlanguage = {en},\n\tbooktitle = {Automated {Reasoning}},\n\tauthor = {Bylander, Tom},\n\tyear = {1991},\n\tpages = {6},\n}\n\n\n\n","author_short":["Bylander, T."],"key":"bylander_complexity_1991","id":"bylander_complexity_1991","bibbaseid":"bylander-complexityresultsforplanning-1991","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/matteocarde","dataSources":["BLJPWpPi3hneTGaPF"],"keywords":[],"search_terms":["complexity","results","planning","bylander"],"title":"Complexity Results for Planning","year":1991}