the closest to ω . For instance, provided that PS = { a, b } and ω( a ) = ω( b ) = 1, we have Force(ω, ¬b)(α) = 1 and Force(ω, ¬b)(b) = 0.  Clearly, if ω |= l then Force(ω, l) = ω.  If L = { l 1 , . . , l n } is a consistent set of literals, then Force ( w, L ) is defined as Force( . . . ( Force( ω, l 1 ), . . . ), l n ).

Lastly, given an interpretation ω and a variable x, we let Switch ( ω,x ) denote the interpretation that gives the same truth value as ω to all variables except x, and that gives to x the value opposite to that given by w.

Two formulas Ψ and Φ are said to be equivalent modulo a formula Σ if and only if ΣΛΨΞΛΦ
In this paper we use the concepts of prime implicates and prime implicants. The set of prime implicates of a formula Σ , denoted by IP (Σ), is defined as:
IP(Σ) = {δ clause  | Σ |= δ and   Δδ ′ clause s.t. Σ |= δ ′ and δ ′ |= δ and δ | = δ ′ } .

Among all the implicates of Σ (i.e., the clauses entailed by Σ ), the prime implicates of Σ are the minimal ones w.r.t. |= (i.e., the logically strongest ones). The set of prime implicants of a formula Σ , denoted by PI (Σ), is defined dually as:
PI(Σ) = {γ term  | γ |= Σ and  ∂γ ′ term s.t. γ ′ |= Σ and γ |= γ ′ and γ ′ | ̸= γ }.

Among all the implicants of Σ (i.e., the terms implying Σ ), the prime implicants of Σ
are the maximal ones w.r.t. |= (i.e., the logically weakest ones).

Of course, the set of prime implicants/ates may contain equivalent terms/clauses. We can restrict our attemption to one term/clause for each set of equivalent terms/clauses.

Stated otherwise, in PI(Σ) and IP(Σ), only one representative per equivalence class is kept. Example 1 Let Σ = { a V b, ¬a Λ c ⇒ e, d ⇒ e}. The set of prime implicates of Σ is, by definition, I P(Σ) = { α V b, α V ¬c V e, ¬d V e, d V ¬e, α V ¬c V d}.

## 2.2 Computational Complexity

The complexity results we give in this paper refer to some complexity classes which deserve some recalls. More details can be found in Papadimitriou's (1994) textbook. Given a problem A, we denote by A the complementary problem of A. We assume that the classes P, NP and coNP are known to the reader. The following classes will also be considered:

- BH 2 (also known as DP) is the class of all languages L such that L = L 1 N L 2 , where L is in NP and L 2 in coNP. The canonical BH 2 -complete problem is SAT–UNSAT: a pair of formulas (ϕ,ψ) is in SAT—UNSAT if and only if ϕ is satisfiable and ψ is not.

The complementary class coBH 2 is the class of all languages L such that L = L 1 UL 2 , where L 1 is in NP and L 2 in coNP. The canonical coBH 2 -complete problem is SAT-
OR- UNSAT: a pair of formulas (ϕ, ψ) is in SAT- OR- UNSAT if and only if ϕ is satisfiable or ψ is not.