Complexity results for 2CNF default theories
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.
complexity 2cnf default theory credulous reasoning skeptical reasoning