Approximating the stable model semantics is hard

Georg Gottlob, Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review


In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of a polynomially computable approximation is within a constant factor from the size of the intersection (union) of stable models of a program. We also show that unless P=NP, no approximation exists that uniformly bounds the intersection (union) of stable models.

Original languageEnglish
Pages (from-to)123-128
Number of pages6
JournalFundamenta Informaticae
Issue number1-2
StatePublished - Nov 1996


  • Computational complexity
  • Logic programming
  • Stable models
  • Well-founded semantics

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics


Dive into the research topics of 'Approximating the stable model semantics is hard'. Together they form a unique fingerprint.

Cite this