Approximating the Stable Model Semantics is Hard
Georg Gottlob, Mirosław Truszczyński · Fundamenta Informaticae · 1996
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