On the computational complexity of temporal projection, planning, and plan validation

摘要

One kind of temporal reasoning is temporal projection—the computation of the consequences of a set of events. This problem is related to a number of other temporal reasoning tasks such as plan validation and planning. We show that one particular, simple case of temporal projection on partially ordered events turns out to be harder than previously conjectured, while planning is easy under the same restrictions. Additionally, we show that plan validation is tractable for an even larger class of plans—the unconditional plans—for which temporal projection is NP-hard, thus indicating that temporal projection may not be a necessary ingredient in planning and plan validation. Analyzing the partial decision procedure for the temporal projection problem that has been proposed by other authors, we notice that it fails to be complete for unconditional plans, a case where we have shown plan validation tractable.