Let c j denote the j th element of C j and s j the j th element of S . We define a set of [ S ] Boolean variables in one to one correspondence with the elements of S, which we use to describe the examples of LS. The corresponding set of literals is denoted
{x1,x1,x2,x2, ...,x1,x1,x1,x1}.  Our reduction is made in the two-classes framework.  The sample LS contains two disjoint subsets : the set of positive examples LS+, and the set of negative ones LS-. LS+ contains | S | examples, denoted by e + , e + , ..., e + 1 . . . We construct each positive example so that it represents an element of S. More precisely,

$$\forall1\leq i\leq|S|,e_{i}^{+}\quad=\quad\overline{{{x}}}_{i}\wedge\bigwedge_{j=1,j\neq i}^{j=|S|}\overline{{{x}}}_{j}\ .$$
$$(1\,3)$$

LS- contains | C | examples, denoted by e t , e t , …, e t c i ,
We construct each negative example so that it encodes each of the constraints of C. More precisely:

$$\forall1\leq i\leq|C|,e_{i}^{-}\quad=\quad\left(\bigwedge_{j:s_{j}\in e_{i}}\overline{{{x}}}_{j}\right)\land\left(\bigwedge_{j:s_{j}\not\in e_{i}}x_{j}\right)\ .$$
$$(\,14\,)$$

Without loss of generality, we make four assumptions on the instance of "2-NM-Colorability" due to the fact that it is not trivial:

1. There does not exist some element of S present in all constraints. In this case indeed, the trivial coloration consists in giving to one of such elements one color, and the other color to all other elements of S .
2. $\forall(i,j,k,l)\in\{1,2,...,|S|\}^{4}$ with $i\neq j$ and $k\neq l$, $$\exists o\in\{1,2,...,|C|\},\,\{s_{i},s_{j}\}\not\subseteq c_{o}\quad\wedge\quad\{s_{k},s_{l}\}\not\subseteq c_{o}\enspace.$$ (15) Otherwise indeed, there would exist $(i,j,k,l)\in\{1,2,...,|S|\}^{4}$ with $i\neq j$ and $k\neq l$ such that 
$$(\,15\,)$$ $$\,\colon\,\neq\,l$$
$$\forall o\in\{1,2,...,|C|\},\,\{s_{i},s_{j}\}\subseteq c_{o}\quad\vee\quad\{s_{k},\,s_{l}\}\subseteq c_{o}\,\,\,,$$  $\forall o\in\{1,2,...,|C|\},\,\{s_{i},s_{j}\}\subseteq c_{o}\quad\vee\quad\{s_{k},\,s_{l}\}\subseteq c_{o}\,\,\,,$  \(\forall o\in\{1,2,...,|C|\},\,\{s_{i},s_{j}\}\subseteq c_{o}\quad\vee\quad\{s_{k},\,s_{l}\}\subseteq c_{o}\,\,\,,\]
$$(1\,6)$$
and in that case, a trivial solution to "2-NM-Colorability" would consist in giving to s i one color and to s i the other one, and to sk one color and to sk the other one.

3. Each element of S belongs to at least one constraint in C. Otherwise, it can be removed.

4. Each constraint contains at least two elements from S. Otherwise it can be removed.
- Suppose there exists a solution to "2-NM-Colorability". We build the DNF with two monomials of (Kearns et al., 1987) consistent with the examples. Then, we build two rules by associating the two monomials to some (arbitrary) positive value. The default class is
"." This leads to a decision committee with two rules consistent with LS .

- Suppose that there exists a decision committee f with at most two rules consistent with LS. We now show that there exists a valid 2-NM-Coloration of the elements of S. We first show three lemmas which shall be used later on. Then, we show that the decision committee is actually equivalent to a DNF with two monomials consistent with LS . We conclude by using previous results (Kearns et al., 1987) on how to transform this DNF into a valid 2-NM-Coloration of the elements of S.