---
title: "Complexity Results for Planning"
authors:
  - "Tom Bylander"
doi: ""
url: "https://ijcai.org/proceedings/1991/41"
pdf: "https://ijcai.org/proceedings/1991/0041.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "274-278"
track: "Automated Reasoning"
keywords:
---

# Complexity Results for Planning

Tom Bylander

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 274-278.

## 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 planning problems are defined by different restrictions on the preconditions and postconditions of operators. The main results are: Propositional planning is PSPACE-complete, even if operators are restricted to two positive (nonnegated) preconditions and two postconditions, or if operators are restricted to one postcondition (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 positive postcondition. It is tractable in a few restricted cases, one of which is if each operator is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a subproblem of this restricted planning problem.