Lit-equivalent given L V . Hence, M is a polynomial many-one reduction from VAR- EQUIVALENCE to LIT- EQUIVALENCE. Since VAR- EQUIVALENCE is Π 2 -hard, this is also the case for LIT-EQUIVALENCE.

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 . Proof: Proposition 4 from (Boutilier, 1994) states that Σ is influenceable from V if and only if there exists a prime implicant of Σ that contains a variable from V t where V is the set of controllable variables. Proposition 9 completes the proof.

Proposition 26    Let E  be a formula from PROP 5 and V  a subset of P S.  E is relevant to V if and only if E is Var-dependent on V.

Proof: The proof is trivial from Proposition 9.

Proposition 27    Let Σ be a formula from PROPps and V a subset of PS. Σ is strictly relevant to V if and only if Σ is Var-dependent on V and Var-independent from Var(Σ)\V. Proof: Easy from the definition of strict relevance, plus Proposition 9 (Σ is Var-dependent from every variable occurring in a prime implicate of Σ and Var-independent from all the remaining variables).

## Proposition 28

(1) STRICT RELEVANCE OF A FORMULA TO A SUBJECT MATTER (Lakemeyer, 1995) is nfcomplete.

(2) STRICT RELEVANCE OF A FORMULA TO A SUBJECT MATTER (Lakemeyer, 1997) is BH 2 -
complete.

## Proof: - Strict Relevance (Lakemeyer, 1995)

- Membership. Let us consider the complementary problem. Guess a clause γ, check that it does not contain any variable from V (this can be achieved in time polynomial in | γ | + | V |, hence in time polynomial in | Σ | + | V | since no prime implicate of Σ can include a variable that does not occur in Σ ). Then check that it is an implicate of Σ (one call to an NP oracle) and check that every subclause of γ obtained by removing from it one of its k literals is not an implicate of Σ
(k calls to an NP oracle). Since only k + 1 calls to such an oracle are required to check that γ is a prime implicate of Σ, the complementary problem of STRICT
RELEVANCE belongs to Σ 2 . Hence, STRICT RELEVANCE belongs to Π 2 .

Hardness. Let {A,B} be a partition of Var(E) (for any formula E). VA3BE is valid if and only if every prime implicate of Σ that contains a variable from A