Proof. **Membership in the class follows from the fact that the problem is coNP-complete**
(Marek & Truszczy´nski, 1991). For the hardness, we adapt the proof of Marek and Truszczy´nski (1991) showing that deciding whether a query **is true in all stable models**
is coNP-hard.

Let ǫkernel be the language {ǫ, G} such that G **is a graph with at least one kernel.**
Let |G| = n, and observe that G **cannot have more vertices than its size** n.

We show that for each n, there exists a logic program Pn **such that for every graph** G
with at most n vertices, there exists a query QG such that G **has a kernel iff** Pn 6|=sm QG.

Let the alphabet of Pn **be composed by the following 2**n 2 + n **propositional letters:**
{ai|i ∈ {1..n} } ∪ {rij , sij |i, j ∈ {1..n} }.

The program Pn **is defined as:**

$$\left.\begin{array}{r l r l}{{a_{j}}}&{{}:-}&{{}\neg a_{i},r_{i j}}\\ {{s_{i j}}}&{{}:-}&{{}\neg r_{i j}}\\ {{r_{i j}}}&{{}:-}&{{}\neg s_{i j}}\end{array}\right\}{\mathrm{for~}}i,j\in\{1..n\}$$

Given a graph G = (V, E), the query QG **is defined as**

$$Q_{G}=(\bigvee_{(i,j)\in E}\neg r_{i j})\vee(\bigvee_{(i,j)\not\in E}r_{i j})$$

The reduction from ǫkernel to sm is defined as: f1(x, n) = Pn, i.e., f1 **depends only on**
its second argument, f2(x, n) = ǫ, i.e., f2 is a constant function, and g = Qy**, i.e., given a**
graph G, the circuit g **computes the query** QG.

As a result, this is a k❀ **reduction. We now show that this reduction is correct, i.e.,**
hǫ, Gi ∈ ǫkernel (G **has a kernel) iff** Pn 6|=SM QG.

If-part. Suppose Pn 6|=SM QG. Then, there exists a stable model M of Pn **such that**
M |= ¬QG. Observe that ¬QG is equivalent to the conjunction of all rij such that (**i, j**) ∈ E,
and all ¬rij such that (i, j) 6∈ E. Simplifying Pn with ¬QG **we obtain the clauses:**

$$a_{j}\ :-\ \neg a_{i},\ \mathrm{for}\ (i,j)\in E$$
aj :− ¬ai, for (i, j) ∈ E (1)
Observe that M contains all sij such that (i, j) 6∈ E**, and in order to be stable, - i.e., to**
support atoms rij such that (i, j) ∈ E - M contains no atom sij such that (**i, j**) ∈ E.

Let H = {j|aj ∈ M}, K = {i|ai 6∈ M}. Now H **is a vertex cover of G, since for each**
edge (i, j) ∈ E, M should satisfy the corresponding clause (1) aj :− ¬ai**, hence either**
ai ∈ M, or aj ∈ M. Moreover, for each j in H, the atom aj is in M, and since M **is a**
stable model, there exists a clause aj :− ¬ai such that ai 6∈ M, that is, i ∈ K**. Therefore,**
K **is a kernel of** G.

Only-if part. Suppose G = (V, E) has a kernel K, and let H = V − K. Let M **be the**
interpretation M = {rij |(i, j) ∈ E} ∪ {sij |(i, j) 6∈ E**} ∪ {**aj |j ∈ H}
Obviously, M 6|= QG. We now show that M is a stable model of Pn, i.e., M **is a least**
Herbrand model of P M
n
. In fact, P M
n**contains the following clauses:**

$$\begin{array}{l l}{{s_{i j}}}&{{\quad\quad\quad\quad\mathrm{for~}(i,j)\not\in E}}\\ {{r_{i j}}}&{{\quad\quad\quad\quad\quad\mathrm{for~}(i,j)\in E}}\\ {{a_{j}}}&{{\quad:-\ r_{i j}}}&{{\mathrm{~for~}i\in K}}\end{array}$$
