Complexity of the Unique Extension Problem in Default Logic

Fundamenta Informaticae

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.

 @article{zhao-libe-02,
 title = {Complexity of the Unique Extension Problem in Default Logic},
 year = {2002},
 author = {Zhao, Xishun and Liberatore, Paolo},
 journal = {Fundamenta Informaticae},
 pages = {79-104},
 number = {1},
 volume = {53},
 }