fixpoints. Thus, checking whether a SOLP collection containing at least one nonpositive SOLP program has a social model is trivially NP-hard. Moreover, since this problem is easily seen to be in NP, it is NP-complete.

Now, we introduce several computationally interesting decision problems associated with the social semantics. Each of them corresponds to a computational task involving labeled atom search inside the social models of a SOLP collection.

The traditional approach used for classical non-monotonic semantics of logic programs, typically addresses the two following problems:
(a) Skeptical Reasoning, i.e. deciding whether an atom x **occurs in all the models**
of a given program P;
(b) Credulous Reasoning, i.e. deciding whether an atom x **occurs in some model**
of a given program P. Since a social model is a social interpretation, i.e. a set of labeled atoms, we have to extend the above problems (a) and (b**) by introducing a further search** dimension, expressing the sociality **degree of the agents represented by the SOLP**
collection. More informally, we are also interested in how many **SOLP programs a**
given atom - occurring as a labeled atom in a social model - is entailed by.

As a consequence, given a collection C = {P1, · · · ,Pn} **of SOLP programs, a**
social model M¯ of P1, · · · ,Pn and an atom x **, we distinguish two cases. Either:**
(1) for each P in C, ∀i (1 ≤ i ≤ n), xPi ∈ M¯ **, or** (2) for some P in C, ∃i | 1 ≤ i ≤ n ∧ xPi ∈ M¯ .

In words, in case (1) the agents corresponding to the SOLP collection C **exhibit**
a greater sociality degree - since all of them choose the atom x **inside the social**
model M¯ - than in case (2), where at least one agent is required to choose x and thus we observe a more individual agent behaviour.

By combining the problems (a) and (b) with the traditional reasoning **tasks**
(1) and (2), we obtain the following four decision problems relevant to the social semantics:
1. **PROBLEM** SS-SOSn **(socially skeptical reasoning):**
Instance: A SOLP collection C = {P1, · · · ,Pn} **and an atom** x .

Question: Does it hold that, for each M¯ ∈ SOS(P1, **· · ·** ,Pn), {xP1
, · · · , xPn } ⊆ M¯ ,
i.e. ∀i (1 ≤ i ≤ n), xPi ∈ M¯ ?

In case the answer to such a problem is positive, then it holds that all **the agents**
always (i.e., in each social model) choose x , since xP occurs in M¯ **, for each social**
model M¯ and for each SOLP program P**. For instance, this kind of reasoning could**
be applied by the government of a given country in order to know if all **citizens,** modelled as a collection of SOLP programs, pay taxes.

2. **PROBLEM** IS-SOSn **(individually skeptical reasoning):**
Instance: A SOLP collection C = {P1, · · · ,Pn} **and an atom** x .

Question: Does it hold that, for each M¯ ∈ SOS(P1, **· · ·** ,Pn), ∃i | 1 ≤ i ≤ n
∧ xPi ∈ M¯ ?