COMPLEXITY RESULTS FOR THE DEFAULT-LOGIC AND THE AUTOEPISTEMIC LOGIC

The default logic (Rei 80) and the autoepistemic logic (Mo 85) are non-monotonic logics. In default logic a default theory consists of a set of propositional sentences W and a set of defaults D. A sentence is defined to be derivable from a given default theory if it belongs to an extension of the default theory. A central question is: Given a default theory DELTA = (D, W) and a sentence beta, is there an extension of DELTA which contains beta? This question is the extension-membership-problem for DELTA and beta (abbr. EMP(DELTA, beta)). We show that this problem, as well as the problem whether a given sentence belongs to every extension of a given default theory (abbr. AEMP(DELTA, beta)), is NP-hard for default theories and for normal default theories. Let DELTA = (D, W) be a finite normal default theory such that the union of W and the consequents of the elements of D is satisfiable. We show for such theories that the EMP is polynomial time Turing reducible to the satisfiability problem in classical propositional logic and it is solvable in polynomial time, if the elements of W, the prerequesites and consequents of the defaults and -beta are Horn sentences. Moreover it is shown that the problem is P-complete for such theories. On account of the theorem of Konolige (Ko 88) we get the analogous results for propositional autoepistemic logic. Furthermore we show the NP-hardness of the EMP and AEMP for the modified default-logic (Lu 88). We show that the EMP for normal theories for the default logic and the EMP for the modified default logic are polynomial time nondeterministic Turing reducible to the satisfiability problem in classical propositional logic.