On the Complexity of Possible Truth

Foundations of Automatic Planning - The Classical Approach and Beyond

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

Chapman’s paper, "Planning for Conjunctive Goals," has been widely acknowledged as a major step towards understanding the nature of nonlinear planning, and it has been one of the bases of later work by others. But as with much pioneering work, it is not free of problems---and this has led to much confusion about the meaning of his results. Previous papers have dealt with some of these problems, and the current paper discusses another one. In particular, I show that given a plan P and a proposition p, it is NP-hard to determine whether or not there exists a completion of P that can be executed to produce a situation in which p is true. I also discuss the conflict between this result and Chapman’s statements, and how this affects the way we should interpret the term "possible truth."