A SURVEY OF COMPLEXITY RESULTS FOR NONMONOTONIC LOGICS

This paper surveys the main results appearing 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.