Affiliations: Institute of Logic and Cognition, Zhongshan
University, Guangzhou, 510275, P. R. China | Department of Computer and System Sciences, University
of Rome ``La Sapienza'', Via Salaria 113, 00198, Rome, Italy
Abstract: In this paper we analyze the problem of checking whether a default
theory has a single extension. This problem is important for at least three
reasons. First, if a theory has a single extension, nonmonotonic inference can
be reduced to entailment in propositional logic (which is computationally
easier) using the set of consequences of the generating defaults. Second, a
theory with many extensions is typically weak i.e., it has few consequences;
this indicates that the theory is of little use, and that new information has
to be added to it, either as new formulae, or as preferences over defaults.
Third, some applications require as few extensions as possible (e.g.
diagnosis). We study the complexity of checking whether a default theory has a
single extension. We consider the combination of several restrictions of
default logics: seminormal, normal, disjunction-free, unary, ordered.
Complexity varies from the first to the third level of the polynomial
hierarchy. The problem of checking whether a theory has a given number of
extensions is also discussed.
Keywords: default logic, complexity, unique extension existence problem
