  Epistemic Logic Programs (ELPs), that is, Answer Set Programming (ASP)
extended with epistemic operators, have received renewed interest in recent
years, which led to a flurry of new research, as well as efficient solvers. An
important question is under which conditions a sub-program can be replaced by
another one without changing the meaning, in any context. This problem is known
as strong equivalence, and is well-studied for ASP. For ELPs, this question has
been approached by embedding them into epistemic extensions of equilibrium
logics. In this paper, we consider a simpler, more direct characterization that
is directly applicable to the language used in state-of-the-art ELP solvers.
This also allows us to give tight complexity bounds, showing that strong
equivalence for ELPs remains coNP-complete, as for ASP. We further use our
results to provide syntactic characterizations for tautological rules and rule
subsumption for ELPs.

Logic in Computer Science;Computational Complexity