Abduction and Memoing

Abduction is a inference procedure with wide applicability to knowledge-based processing. Abduction is known to be NP-hard; i.e. over models of since N , runtimes are expected to be O(k N ). Memoing is a technique for storing the results of prior computations, thus decreasing the inferencing time required if some particular inference is required more than once. Memoing is known to decrease the runtimes of certain computations. Here, we experiment with memoing to reduce the computational cost of abduction. These experiments were unsuccessful. We conclude that memoing is not suitable for optimising abduction due to the context-dependent nature of abductive inference. KEYWORDS: Abduction, memoing, complexity. 1 Introduction The premises of this paper are that (i) abduction is an important inference procedure; and (ii) techniques for optimising abduction would be applicable to a wide variety of KBS tasks. Memoing is a general optimisation technique which we tried to apply to abduction...