Complexity results for 2CNF default theories

Authors
Zhao, XS Ding, DC
Citation
Xs. Zhao et Dc. Ding, Complexity results for 2CNF default theories, FUNDAM INF, 45(4), 2001, pp. 393-404
Citations number
13
Categorie Soggetti
Computer Science & Engineering
Journal title
FUNDAMENTA INFORMATICAE
ISSN journal
01692968 → ACNP
Volume
45
Issue
4
Year of publication
2001
Pages
393 - 404
Database
ISI
SICI code
0169-2968(200103)45:4<393:CRF2DT>2.0.ZU;2-2
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 2 CNF 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 wheth er 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.