by at least one positive example (otherwise, f would be equivalent to a single-rule decision committee, and we fall in the contradiction of Lemma 5), it contains at most one negative literal. If it contains exactly one negative literal, it is satisfied by exactly one positive example, and we can replace it by the monotonous monomial with [ S ] - 1 positive literals ( we leave empty the position of the initial negative literal). Consequently, similarly for t 1 , we can suppose that t 2 is monotonous. We distinguish two cases.

- If | Δ 1 | > | Δ 2 |, no positive example can satisfy t 1 . By fact 3, t 1 = Λ i = | S 1 x j, and

no negative example can satisfy it, a contradiction ( f cannot be consistent).

- If | Δ 1 | ≤ | Δ 2 |. t 2 cannot be empty; therefore it contains a certain number of positive literals. Each positive example satisfying t 2 must also satisfy t 1 , since otherwise f is not consistent; Since t 1 and t 2 are monotonous, t 2 is a generalization of t 1 , and any example satisfying t 1 (in particular, the negative examples) must satisfy t 2 , a contradiction.
Therefore β =" . This forces all positive examples to satisfy at least one monomial of f. Recall that f contains two monomials. Suppose that ∆ 1 > 0 and ∆ 2 < 0. It comes t 1 = 0 (Lemma 4). All negative examples must satisfy t 2 , and we also have | Δ 1 | ≤ | Δ 2 | .

No positive example can satisfy t 2 , and Lemma 3 gives either t 1 = N j = 1 x j (satisfied by no example, impossible) or t 2 contains at least two negative literals, whose corresponding elements of S are shared by all constraints, and we obtain again that the instance of "2- NM-Colorability" is trivial.

Therefore, A 1 > 0 and A 2 > 0, and each monomial is satisfied by at least one positive example. f is thus equivalent to a DNF with the same two monomials, and we can use a previous solution (Kearns et al., 1987) to build a valid 2-NM-Coloration. First, we can suppose that f is again monotonous (Kearns et al., 1987).  Then, since each positive example stisfies at least one monomial ( β = " " ), then for all variable, there exists a monomial which does not contain the corresponding positive literal. The 2-Coloration is then

$$\forall i\in\{1,2,...,|S|\},\chi(s_{i})\quad=\quad\operatorname*{min}_{j\in\{1,2\}}\;\{j:x_{i}\not\in t_{j}\}\;\;.$$
$$\left(20\right)$$

Could this be invalid ? That would mean that there exists a constraint c i such that Vs i E c i , X ( s i ) = K = cst . This would mean that the corresponding negative example sssees t K , a contradiction (Kearns et al., 1987). This ends the proof of Theorem 3.

## Proof Of Theorem 4

Define the function f : 2 { 0 , 1 ,...,c-1 } → IR such that

$$\forall A\subseteq\{0,1,...,c-1\},\,f[A]=\sum_{o,k,j}w((o,k,j))q_{A}(j,k)\,\,,\tag{21}$$

with

$q_{A}(j,k)=e^{\alpha}[j\in A\wedge k\not\in A]+e^{-\alpha}[j\not\in A\wedge k\in A]+[(j\in A\wedge k\in A)\vee(j\not\in A\wedge k\not\in A)]$