research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleA dichotomy in the complexity of propositional cir- cumscription
Bibtex cite IDRACTI-RU1-2004-4
Journal Theory of Computing Systems
Year published 2004
Volume 37
Number 6
Pages 695-715
Note Springer Science+Business Media, Inc.
The inference problem for propositional circumscription is known to be highly intractable and, in fact, harder than the inference problem for classi- cal propositional logic. More precisely, in its full generality this problem is P - 2 complete, which means that it has the same inherent computational complexity as the satisfiability problem for quantified Boolean formulas with two alternations (universal-existential) of quantifiers. We use Schaefer?s framework of generalized satisfiability problems to study the family of all restricted cases of the inference problem for propositional circumscription. Our main result yields a complete clas- sification of the ?truly hard? ( P -complete) and the ?easier? cases of this problem 2 (reducible to the inference problem for classical propositional logic). Specifically, we establish a dichotomy theorem which asserts that each such restricted case either is P -complete or is in coNP. Moreover, we provide efficiently checkable criteria 2 that tell apart the ?truly hard? cases from the ?easier? ones. We show our results both when the formulas involved are and are not allowed to contain constants. The present work complements a recent paper by the same authors, where a complete classifi- cation into hard and easy cases of the model-checking problem in circumscription was established.
Kirousis, Lefteris
Kolaitis, Ph.
j6.pdf (main file)
Publication ID180