On the Complexity of Possible Truth

Dana S. Nau

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."


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.