A Knowledge-Representation Language with Social Features 29
(1. Membership). We need to guess a candidate social interpretation M¯ for C
and, then, to verify that:
(i) M¯ ∈ SOS(P1, · · · ,Pn**), and**
(ii) ∃j | 1 ≤ j ≤ n ∧ xPj 6∈ M¯ .

Verifying the above items is feasible in polynomial time. Thus, the complementary problem of SS-SOSn **is in NP.**
(2. Hardness)**. Now we prove that a reduction from the NP-complete problem**
SOSn **to the complementary problem of** SS-SOSn **is feasible in polynomial time.**
Consider an atom x **such that, for each** i (1 ≤ i ≤ n), x 6∈ Var (Pi**). It is easy**
to see that SOS(P1, · · · ,Pn) 6= ∅ iff there exists M¯ ∈ SOS(P1, · · · ,Pn**) such that**
{xP1
, · · · , xPn } 6⊆ M¯ . Moreover, in case {xP1, · · · , xPn } 6⊆ M¯ **, it results that** ∃j | 1 ≤ j ≤ n ∧ xPj 6∈ M¯ **. Thus,** SOSn **is polynomially reducible to the complementary**
problem of SS-SOSn.

Theorem 6 The problem IS-SOSn is coNP-complete.

Proof It suffices to prove that the complementary problem of IS-SOSn **is NP-complete.**
Such a problem may be described as follows:
Instance: A SOLP collection C = {P1, · · · ,Pn} **and an atom** x .

Question: Does it hold that there exists M¯ ∈ SOS(P1, · · · ,Pn**) such that** ∀j
(1 ≤ j ≤ n), xPj 6∈ M¯ , i.e. {xP1, · · · , xPn **} 6⊆** M¯ ?

(1. Membership). We need to guess a candidate social interpretation M¯ for C
and, then, to verify that:
(i) M¯ ∈ SOS(P1, · · · ,Pn**), and**
(ii) {xP1
, · · · , xPn **} 6⊆** M¯ .

Verifying the above items is feasible in polynomial time. Thus, the complementary problem of IS-SOSn **is in NP.**
(2. Hardness)**. Now we prove that a reduction from the NP-complete problem**
SOSn **to the complementary problem of** IS-SOSn **is feasible in polynomial time.**
Consider an atom x **such that, for each** i (1 ≤ i ≤ n), x 6∈ Var (Pi**). It is easy**
to see that SOS(P1, · · · ,Pn) 6= ∅ iff there exists M¯ ∈ SOS(P1, · · · ,Pn**) such that**
{xP1
, · · · , xPn } 6⊆ M¯ **. Thus,** SOSn **is polynomially reducible to the complementary**
problem of IS-SOSn.

Theorem 7 The problem SC-SOSn is NP-complete.