Institut Mittag-Leffler
The Royal Swedish Academy of Sciences


Reports Institut Mittag-Leffler
ISSN: 1103-467X
ISRN: IML-R


A Dichotomy in the Complexity of Propositional Circumscription
Source file as TeX DVI Data Postscript Document Portable Document Format

Lefteris Kirousis , Phokion Kolaitis

Preprint series: Mathematical Logic - 2000/2001, No. 25

MSC 2000

03D15 Complexity of computation
03B70 Logic in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68T27 Logic in artificial intelligence

Keywords: nonmonotonic reasoning, circumscription, minimal models, computational complexity, NP-completeness