On the compilability of diagnosis, planning, reasoning about actions, belief revision, etc
Paolo Liberatore · 1998
In this paper we investigate the usefulness of preprocessing part of the input of a given problem to improve the efficiency. We extend the results of [Cadoli et al., 1996] by giving sufficient conditions to prove the unfeasibility of reducing the on-line complexity via an offline preprocessing. We analyze the problems of diagnosis [Peng and Reggia, 1986], planning [Bylander, 1991], reasoning about actions [Gelfond and Lifschitz, 1993], and belief revision [Williams, 1994]. We analyze other problems from various fields.