
## 5.2 Relevance

Lakemeyer (1995, 1997) introduces several forms of relevance. We show how these forms of relevance are strongly related to FV-independence. We also complete the results given in (Lakemeyer, 1997), by exhibiting the computational complexity of each form of relevance introduced in (Lakemeyer, 1997).

5.2.1 RELEVANCE OF A FORMULA TO A SUBJECT MATTER
Lakemeyer's notion of relevance of a formula to a subject matter can be defined in terms of prime implicates of the formula, as follows (see Definition 9 in Lakemeyer, 1997): Definition 11 (relevance to a subject matter) Let Σ be a formula from PROPps and V a subset of PS.  E is relevant to V if and only if there exists a prime implicate of E
mentioning a variable from V.

Example 15 Let E = (a Ac) and V = {a, b}. E is relevant to V.

As a consequence, Lakemeyer's notion of irrelevance of a formula to a subject matter coincides with FV-independence.

Proposition 26   Let Σ be a formula from PROPps and V a subset of PS. Σ is relevant to V if and only if E is Var-dependent on V .

Thus, the model-theoretic characterization of FV-independence also applies to irrelevance of a formula to a subject matter. We also have that the irrelevance of a formula to a subject matter coincides with Boutilier's definition of influenceability. Finally, the above proposition allows for an easy proof of complexity for relevance, namely, RELEVANCE OF A FORMULA TO A SUBJECT MATTER is NP-complete. 5.2.2 STRICT RELEVANCE OF A FORMULA TO A SUBJECT MATTER
Lakemeyer has introduced two forms of strict relevance. The (chronologically) first one has been given in (Lakemeyer, 1995), as follows.

Definition 12 (strict relevance to a subject matter, Lakemeyer, 1995) Let Σ be a formula from PROPps and V a subset of PS. E is strictly relevant to V if and only if every prime implicate of E contains a variable from V.

Lakemeyer has also introduced another notion of strict relevance (Lakemeyer, 1997),
more demanding than the original one. Here we consider an equivalent definition. Definition 13 (strict relevance to a subject matter, Lakemeyer, 1997) Let Σ be a formula from PROPps and V a subset of PS. E is strictly relevant to V if and only if there exists a prime implicate of Σ mentioning a variable from V, and every prime implicate of E mentions only variables from V.