On the Computational Complexity of Planning and Story Understanding

. Other authors have shown that temporal projection---the computation of the consequences for a set of events---is intractable even for severly restricted cases. They have also suggested that temporal projection is the basic problem underlying planning, plan validation, and story understanding. We have earlier shown that plan validation is actually tractable for a broad and important class of plans, thus indicating that temporal projection and plan validation are not as closely related as was believed. In this paper, we show that also planning and story understanding is sometimes tractable when temporal projection is intractable. This means that temporal projcetion is hardly a necessary ingredient of these tasks either. 1 Introduction Dean and Boddy [4] have earlier analyzed the computational complexity of temporal projection (i.e. the problem of computing the consequences of a set of events) in a propositional strips-like [5] language. They found that even severly restricted cases a..