On the Computational Complexity of Temporal Projection and Plan Validation

Abstract

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 story understanding, planning, and plan validation. We show that one particular simple case of temporal projection on partially ordered events turns out to be harder than previously conjectured. However, given the restrictions of this problem, story understanding, planning, and plan validation appear to be easy. In fact, we show that plan validation, one of the intended applications of temporal projection, is tractable for an even larger class of plans. Introduction The problem of temporal projection is to compute the consequences of a set of events. Dean and Boddy [ 1988 ] analyze this problem for sets of partially ordered events assuming a propositional strips-like [ Fikes and Nilsson, 1971 ] representation of events. They investigate the computational complexity of a number of restricted proble...