A Survey on Complexity Results for Non-monotonic Logics

This paper surveys the main results appeared in the literature on the computational complexity of non-monotonic inference tasks. We not only give results about the tractability/intractability of the individual problems but we also analyze sources of complexity and explain intuitively the nature of easy/hard cases. We focus mainly on non-monotonic formalisms, like default logic, autoepistemic logic, circumscription, closed-world reasoning and abduction, whose relations with logic programming are clear and well studied. Complexity as well as recursion-theoretic results are surveyed. Work partially supported by the ESPRIT Basic Research Action COMPULOG and the Progetto Finalizzato Informatica of the CNR (Italian Research Council). The first author is supported by a CNR scholarship 1 Introduction Non-monotonic logics and negation as failure in logic programming have been defined with the goal of providing formal tools for the representation of default information. One of the ideas und..