A dichotomy in the complexity of prepositional circumscription

Lefteris M. Kirousis, Phokion G. Kolaitis

Research output: Contribution to journalArticlepeer-review


The inference problem for prepositional circumscription is known to be highly intractable and, in fact, harder than the inference problem for classical prepositional logic. More precisely, in its full generality this problem is ∏2P-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 prepositional circumscription. Our main result yields a complete classification of the "truly hard" (∏2P-complete) and the "easier" cases of this problem (reducible to the inference problem for classical prepositional logic). Specifically, we establish a dichotomy theorem which asserts that each such restricted case either is ∏2 P-complete or is in coNP. Moreover, we provide efficiently checkable criteria 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 classification into hard and easy cases of the model-checking problem in circumscription was established.

Original languageEnglish (US)
Pages (from-to)695-715
Number of pages21
JournalTheory of Computing Systems
Issue number6
StatePublished - Dec 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'A dichotomy in the complexity of prepositional circumscription'. Together they form a unique fingerprint.

Cite this