positive (or definite Horn) program, super-coherence of $P$ is a necessary condition—this is straightforward to see because definite Horn programs have exactly one answer set, so a non-super-coherent program cannot be uniformly equivalent to any definite Horn program.

Since super-coherent programs form a strict subset of all [$\rm ASP$]{} programs, another important question arises: Does the restriction to super-coherent programs limit the problems that can be solved by them? In this paper, we show that this is not the case, by embedding all relevant reasoning tasks over [$\rm ASP$]{} (testing answer set existence, query answering, answer set computation) into reasoning tasks over [$\rm ASP^{\rm sc}$]{}. We also show that all reasoning tasks over normal (non-disjunctive) [$\rm ASP$]{} can be embedded into tasks over normal [$\rm ASP^{\rm sc}$]{}. These results essentially demonstrate that [$\rm ASP^{\rm sc}$]{} is sufficient to encode any problem that can be solved by full [$\rm ASP$]{}, and is therefore in a sense “complete”. However, we would like to note that these embeddings were designed for answering this theoretical question, and might lead to significant overhead when evaluated with ASP solvers. We therefore do not advocate to use them in practical settings, and finding efficient embeddings is a 