## Complexity of the Unique Extension Problem in Default
Logic

**Xishun Zhao and Paolo Liberatore**
*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},
}

HTTP download.