Epistemic Logic Programs (ELPs) [1]}, [2]}, [3]} add epistemic operators to the language of Answer Set Programming
(ASP) [4]}, [5]}, [6]}, a generic, fully
declarative logic programming language that allows for encoding problems such
that the resulting answers (called answer sets) directly correspond to
solutions of the encoded problem. In ASP, negation is usually interpreted
according to the stable model semantics [7]}, that is, as
negation-as-failure or default negation. Intuitively, a default negated atom
\(\lnot a\)  is true if there is no justification for \(a\)  being true in the same
answer set. Hence, default negation is a “local” operator defined relative to
the answer set under consideration. ELPs (as defined in [3]})
extend ASP with the epistemic negation operator \(\mathbf {not}\,\) . An epistemically
negated atom \(\mathbf {not}\,a\)  intuitively means that atom \(a\)  cannot be proven
to be true, in the sense that it is not true in every answer set. Epistemic
negation is thus defined with respect to a set of answer sets, referred to as a
world view. Deciding whether such a world view exists is
\(\Sigma _{\mathit {P}}^{\mathit {3}}\) -complete in general [3]}, whereas deciding answer set existence
for ASP can be done in \(\Sigma _{\mathit {P}}^{\mathit {2}}\)  [10]}, one level lower on the
polynomial hierarchy.
