30 F. Buccafurri and G. Caminiti Proof
(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 } ⊆ M¯ .

Verifying the above items is feasible in polynomial time. Thus, the problem SC-SOSn **is in NP.**
(2. Hardness)**. Now we prove that a reduction from the NP-complete problem**
SOSn **exists and it is feasible in polynomial time. consider the SOLP collection**
C
′ = {τ(P1), · · · , τ(Pn)}, where, for each i (1 ≤ i ≤ n), τ(Pi**) is a SOLP program**
obtained from Pi **as follows:**
τ(Pi) = Pi ∪ {x ←},
where it holds that, for each i (1 ≤ i ≤ n), x 6∈ Var (Pi**). It is easy to see**
that SOS(P1, · · · ,Pn) 6= ∅ iff for each M¯ ∈ SOS(P1, · · · ,Pn**), there exists** M¯ ′ ∈ SOS(τ(P1), · · · , τ(Pn)) such that M¯ ′ = M¯ ∪ {xP1
, · · · , xPn }**. Thus,** SOSn **is polynomially reducible to** SC-SOSn.

Theorem 8 The problem IC-SOSn is NP-complete.

Proof
(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 ∈ M¯ .

Verifying the above items is feasible in polynomial time. Thus, the problem IC-SOSn **is in NP.**
(2. Hardness)**. Now we prove that a reduction from the NP-complete problem**
SOSn **exists and it is feasible in polynomial time. consider the SOLP collection**
C
′ = {τ(P1), · · · , τ(Pn)}, where, for each i (1 ≤ i ≤ n), τ(Pi**) is a SOLP program**
obtained from Pi **as follows:**
τ(Pi) = Pi ∪ {x ←},
where it holds that, for each i (1 ≤ i ≤ n), x 6∈ Var (Pi**). It is easy to see**
that SOS(P1, · · · ,Pn) 6= ∅ iff for each M¯ ∈ SOS(P1, · · · ,Pn**), there exists** M¯ ′ ∈ SOS(τ(P1), · · · , τ(Pn**)) such that** M¯ ′ = M¯ ∪{xP1
, · · · , xPn }. Moreover, since {xP1, **· · ·** ,
xPn } ⊆ M¯ ′, there exists j (1 ≤ j ≤ n) such that xPj ∈ M¯ ′**. Thus,** SOSn **is polynomially reducible to** IC-SOSn.

## 7 Knowledge Representation With Solp Programs

In this section, we provide interesting examples showing the capability of our language of representing common knowledge.