Complexity Results for 2CNF Default Theories

Article type: Research Article

Authors: Zhao, Xishun | Ding, Decheng

Abstract: This paper is concerned with the complexity of default reasoning with 2CNF default theories (D,W) in which W is a set of literals and D is a set of 2CNF defaults. It is proved that the problem whether a literal occurs in at least one extension can be solved in polynomial time. But the problem whether a literal appears in all extensions is proved to be co-NP-complete. The complexity of some subclasses of 2CNF default theories is also analyzed.

Keywords: 2CNF default theory, credulous reasoning, skeptical reasoning, complexity

Journal: Fundamenta Informaticae, vol. 45, no. 4, pp. 393-404, 2001