the size of Φ is polynomially bounded in |Σ| + | L |, unless NP ∩ coNP ⊆ P/poly (which is considered unlikely in complexity theory).

This result shows that computing an explicit representation of ForgetLit(E, L) under the form of a propositional formula is hard, even in a compilation-based approach where the time needed to derive such a formula is neglected.

Finally, we have also derived:
Proposition 24 (complexity of Lit/Var-equivalence) LIT-EQUIVALENCE and VAR-EQUIVALENCE are Π 2 -complete.

## 5. Influenceability, Relevance, And Strict Relevance

In this section, we show that several notions of dependence introduced in the literature are equivalent to, or can be expressed in terms of, semantical independence. In particular, we show that Boutilier's definition of influenceability (Boutilier, 1994) is in fact equivalent to (semantical) FV-dependence. The definition of relevance as given by Lakemeyer (1997) can also be proved to be equivalent to FV-dependence.  One of the two definitions given by Lakemeyer (1997) for strict relevance can also be expressed in terms of FV-dependence. These results allow for finding the complexity of all these forms of dependence as a direct corollary to the complexity results reported in the previous section. For the sake of completeness, we also give the complexity of the original definition of strict relevance (Lakemeyer, 1995) (which is not directly related to FV-dependence), which turns out to be computationally simpler than the subsequent definition given by Lakemeyer (1997).

## 5.1 Influenceability

Boutilier (1994) introduces a notion of influenceability. Roughly speaking, a formula Σ is influenceable from a set of variables V if there exists a scenario in which the truth value of E depends on the value of the variables in V . This idea can be formalized as follows. Definition 10 (influenceability) Let Σ be a formula from PROP P 5 and V a subset of PS.  E is influenceable from V if and only if there exists a PS \ V-world ω, and two V-worlds ω 1 and ω 2 s.t. ω Λ ω 1 |= Σ and ω Λ ω 2 |= ¬Σ hold.

In other words, there is a scenario ω in which the formula Σ can be true or false, depending on the value of the variables in V . While influenceability looks different from the definitions given in this paper, it can be shown that in fact influenceability coincides with FV-dependence.

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

As a consequence, a model-theoretic characterization of influenceability can be easily derived from the one for FV-independence. The complexity of influenceability is an easy corollary to this property: INFLUENCEABILITY is NP-complete.