which, in combination with (38), gives us that

$$B\cap(Y\setminus Z)\neq\varnothing\ .$$
$\left(43\right)$. 
B ∩ (Y \ Z) 6= ∅ . **(43)**
In view of (39) and (42), we have that the rule (12) is contained in ΠX,Y **. From (37),**
(38), (41), and (43), we further conclude that Z is outbound in Y for ΠX,Y . Consequently, Y is an elementary loop of ΠX,Y **and elementarily unfounded by Π w.r.t.** X.

Theorem 1 (e) and (e′**) can now be extended to disjunctive programs as follows.**
Theoremd 1 (e
′)
The following conditions are equivalent to each of conditions (a)–(c) **in Theorem**d 1:
(e) X satisfies LF Π(Y ) for every set Y **of atoms such that** Y is
- maximal among all sets Z of atoms that are elementary loops of ΠX,Z
or
- **a singleton whose atom occurs in Π;**
(e′) X **contains no elementarily unfounded sets for Π w.r.t.** X.

Proof. We first show the equivalence between (b′) and (e′): from (b′) to (e′**) is**
clear, and from (e′) to (b′) follows immediately from Theoremd **2. Moreover, the** equivalence between (e′) and (e) holds in view of Propositiond **5, which tells us that**
an elementarily unfounded set Y for Π w.r.t. X **cannot be a proper subset of any**
set Z of atoms that is an elementary loop of ΠX,Z.

## 3.4 Recognizing Elementary Loops Of Disjunctive Programs

Although deciding whether a given set of atoms is an elementary loop of a nondisjunctive program can be done efficiently, it turns out that the corresponding problem in the case of arbitrary disjunctive programs is intractable.

Theorem 4 For any disjunctive program Π and any set Y of atoms, deciding whether Y **is an**
elementary loop of Π is coNP**-complete.**
Proof**. Containment in** coNP is clear, since it is easy to check that a given nonempty proper subset of Y is not outbound in Y **for Π.**
For coNP**-hardness, we reduce the** coNP**-hard problem of deciding whether a finite**
set X of atoms is "unfounded-free" for a disjunctive program Π (Leone **et al. 1997),** i.e., X contains no nonempty unfounded sets for Π w.r.t. X**. Using a new atom** e that does not occur in Π or X, we construct a program Π′ **as follows: for every**
rule (12) of ΠX, include a rule A ← e, B, F in Π′, and, for every a ∈ X ∪ {e},
include a rule e ← a in Π′**. Given the rules of the latter type, it is clear that any** proper subset Z of Y = X ∪ {e} that is not outbound in Y for Π′**cannot contain** e.

For every rule (12) of Π′such that A 6= {e}, since e ∈ B**, we then have that**
B ∩ (Y \ Z) 6= ∅ .