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.
A SURVEY OF COMPLEXITY RESULTS FOR NONMONOTONIC LOGICS / Cadoli, Marco; Schaerf, Marco. - In: JOURNAL OF LOGIC PROGRAMMING. - ISSN 0743-1066. - 17:2-4(1993), pp. 127-160. [10.1016/0743-1066(93)90029-g]
A SURVEY OF COMPLEXITY RESULTS FOR NONMONOTONIC LOGICS
CADOLI, Marco;SCHAERF, Marco
1993
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
