
Decision lists.
Every CNF formula \(\rho \)  can be turned in linear time into an equivalent decision list \(L\) 
(see Theorem 1 from [1]}). Accordingly, every reduction pointed out in the first part of the proof
can be turned into a reduction such that the targeted representation is a decision list, and this concludes the proof.

Random forests.
We exploit the same idea as in the proof for the decision lists case. To get the result, it is enough to show that every CNF formula \(\rho \)  can be
turned in linear time into an equivalent random forest \(F\) . The translation is as follows: given a CNF formula \(\rho = \bigwedge _{i=1}^k \delta _i\)  over \(X_n\) , we associate
with it in linear time the random forest
\(F = \lbrace T_1, \ldots , T_k, \underbrace{0, \ldots , 0}_{k-1}\rbrace \) 
over \(X_n\) , where each \(T_i\)  (\(i \in [k]\) ) is a decision tree over \(X_n\)  that
represents the clause \(\delta _i\) .
Each \(T_i\)  (\(i \in [k]\) ) is a comb-shaped tree that can easily be generated in time linear in the size of \(\delta _i\) :
if \(\delta _i\)  is the empty clause, then return \(T_i = 0\) , else considering the literals \(\ell \)  of \(\delta _i\)  in sequence,
generate a decision node of the form \(\mathit {ite}(x, 1, T_i^{\ell })\)  (resp. \(\mathit {ite}(x, T_i^{\ell }, 1)\)  if \(\ell \)  is a negative literal \(\overline{x}\)  (resp. a positive literal \(x\) ),
where \(T_i^{\ell }\)  is a decision tree for the clause \(\delta _i \setminus \lbrace \ell \rbrace \) .
Finally, by construction, the only subset of trees of \(F\)  that contains more that half of the trees and that can be consistent is \(\lbrace T_1, \ldots , T_k\rbrace \) 
(every other subset of \(F\)  containing at least \(k\)  trees contains a tree reduced to 0, and as such, is inconsistent). Accordingly, \(F\)  is
equivalent to the conjunction of all trees from \(\lbrace T_1, \ldots , T_k\rbrace \) . Since each \(T_i\)  (\(i \in [k]\) ) is equivalent to the clause
\(\delta _i\)  of \(\rho \) , we get that \(F\)  is equivalent to \(\rho \) , as expected.

Boosted trees.
Direct from the proof for the random forests case, given that a random forest \(F = \lbrace T_1, \ldots , T_m\rbrace \)  can be turned in linear time into
an equivalent boosted tree \(B = \lbrace \langle T_1, \frac{1}{m}\rangle , \ldots , \langle T_m, \frac{1}{m}\rangle \rbrace \)  where the weight of each tree is equal to \(\frac{1}{m}\) .

Boolean multilayer perceptrons.
It is not difficult to turn in polynomial time any CNF formula \(\rho = \bigwedge _{i=1}^k \delta _i\) 
over \(X_n = \lbrace x_1, \ldots , x_n\rbrace \) , such that \(\rho \)  does not contain any valid clause (this can be ensured efficiently), into a Boolean multilayer perceptron \(P\)  over \(X_n\) , that
is logically equivalent to \(\rho \) . One uses only three layers: as expected, the first one \(V_1\)  contains \(n\)  vertices (on per variable \(x_i \in X_n\) ),
the last one \(V_3\)  contains a single vertex \(v_{3,1}\) , and the second layer \(V_2\)  contains \(k\)  vertices, one per clause in \(\rho \) .
The output of \(v_{3,1}\)  is the output of \(P\) .
Let \(\delta _i\)  be any clause of \(\rho \)  and let \(v_{2,i}\)  be the corresponding vertex.
For every vertex \(v_{1,j}\)  (\(j \in [n]\) ) from the first layer \(V_1\)  that is associated with a variable \(x_j \in X_n\) ,
the edge \((v_{1,j}, v_{2,i}) \in E\)  that connects \(v_{1,j}\)  to \(v_{2,i}\)  is labelled by \(w(v_{1,j}, v_{2,i}) = 0\)  if \(x_j\)  does not occur in \(\delta _i\) ,
by \(w(v_{1,j}, v_{2,i}) = 1\)  if \(x_j\)  is a positive literal of \(\delta _i\) , and by \(w(v_{1,j}, v_{2,i}) = -1\)  if \(\lnot x_j\)  is a negative
literal of \(\delta _i\) . The value of the bias \(b_{2,i}\)  is the number of negative literals in \(\delta \) , minus 1.
By construction, we have \(o_{v_{2,i}}(\mathbf {x}) = 1\)  if and only if \(\mathbf {x}\)  satisfies the clause \(\delta _i\)  associated with \(v_{2,i}\) .
Now, for every vertex \(v_{2,i}\)  (\(i \in [k]\) ) of the second layer \(V_2\) , the edge \((v_{2,i}, v_{3,1}) \in E\) 
that connects \(v_{2,i}\)  to \(v_{3,1}\)  is labelled by \(w(v_{2,i}, v_{3,1}) = 1\) , and the bias \(b_{3,1}\)  is set to \(-k\) 
Accordingly, the output of \(o_{v_{3,1}}\)  of \(P\)  is 1 if and only if every
clause \(\delta _i\)  of \(\rho \)  is satisfied by \(\mathbf {x}\) , or stated otherwise, if and only if \(\mathbf {x}\)  is a model of \(\rho \) .

Binarized neural nets.
With a CNF formula \(\rho = \bigwedge _{i=1}^k \delta _i\) 
over \(X_n = \lbrace x_1, \ldots , x_n\rbrace \) , such that \(\rho \)  does not contain any valid clause, we associate in polynomial time a BNN \(N\) 
with \(2n\)  inputs in \(\lbrace -1, 1\rbrace \)  and an output value in \(\lbrace 1, 2\rbrace \)  such that for any \(\mathbf {x} \in \mathbb {B}^n\) , \(\mathbf {x}\)  is a model of \(\rho \) 
if and only if its translation \(\mathit {transl}(\mathbf {x}) \in \lbrace -1, 1\rbrace ^{2n}\)  is classified as a positive instance by \(N\)  (i.e., the output value of \(N\)  is 2).
The translation mapping \(\mathit {transl}: \mathbb {B}^n \rightarrow \lbrace -1, 1\rbrace ^{2n}\)  can be computed in linear time and is defined as follows:
<TABLE>i.e., for \(i \in \lbrace 0, \ldots , n-1\rbrace \) ,
the \((2i+1)^{th}\)  coordinate and the \(2(i+1)^{th}\)  coordinate of \(\mathit {transl}(x_1, \ldots , x_n)\)  are equal to \(2x_{i+1}-1\) .
\(N\)  consists of a single intermediate block, i.e., \(m=1\) , so that the total number of blocks is \(d = 2\) .
The number of inputs of the first block is \(2n\)  and the number of outputs
of this block is \(k\) , the number of clauses of \(\rho \) .
The key idea of our translation from CNF to BNN is to consider each of the \(k\)  clauses \(\delta \)  of \(\rho \)  individually
and compute the difference between the number of literals of \(\delta \)  falsified by \(\mathbf {x}\)  and the number of literals of \(\delta \)  satisfied by \(\mathbf {x}\) ,
which is noted as follows:
\(\mathit {diff}(\delta , \mathbf {x}) = |\lbrace \ell \in \delta : \mathbf {x} \models \overline{\ell }\rbrace | - |\lbrace \ell \in \delta : \mathbf {x} \models \ell \rbrace |.\) 
Obviously enough, \(\mathbf {x}\)  does not satisfy \(\delta \)  precisely when \(\mathit {diff}(\delta , \mathbf {x})\)  is the number of literals occurring in \(\delta \) .
The first operation realized by the BNN is a linear transformation. Thus one must define \(\mathbf {A}_1\)  and \(\mathbf {b}_1\) .
Basically, one wants to use this transformation to store in the output \(\mathbf {y} = \mathbf {A}_1 \mathit {transl}(\mathbf {x}) + \mathbf {b}_1\)  some information about the satisfaction of the clauses of \(\rho \)  by \(\mathbf {x}\) ,
so that \(y_i\)  (\(i \in [k]\) ) corresponds to the clause \(\delta _i\)  of \(\rho \) .
Because clauses are in general not built upon all variables, we need to add a mechanism to avoid considering
the variables that do not appear in a clause. This is achieved within \(\mathit {transl}\)  by duplicating the coordinates
of the input vector \(\mathbf {x}\)  (in addition to translating them from \(\mathbb {B}\)  to \(\lbrace -1, 1\rbrace \) ).
Indeed, if a literal \(\ell \)  over \(x \in X_n\)  is not present in a clause \(\delta _i\) , its contribution to \(y_i\)  is expected to be 0,
which is achieved by multiplying the two coordinates associated with \(x\)  in \(\mathit {transl}(\mathbf {x})\)  by \(-1\)  and 1, respectively.
If a literal \(\ell \)  over \(x \in X_n\)  occurs in \(\delta _i\) , we want its contribution to \(y_i\)  to be set to 1 if the
literal falsifies the clause and to \(-1\)  if it satisfies the clause.
By summing up the contribution of each literal in that way, we obtain the expected result.
Formally, the matrix \(\mathbf {A}_1[i]\)  for \(i \in [k]\)  is defined as:
\(\mathbf {A}_1[i] = (\tau _{x_1}^1, \tau _{x_1}^2,\tau _{x_2}^1, \tau _{x_2}^2, \ldots ,\tau _{x_n}^1, \tau _{x_n}^2) \text{, where}\) 
\(\text{for each } j \in [n] \left\lbrace \begin{array}{ll}\tau _{x_j}^1 = -\tau _{x_j}^2 & \text{if } x_j \notin \mathit {Var}(\delta _i) \\\tau _{x_j}^1 = \tau _{x_j}^2 = 1 & \text{if } \overline{x_j} \in \delta _i\\ \tau _{x_j}^1 = \tau _{x_j}^2 = -1 & \text{if } x_j \in \delta _i\\ \end{array}\right.\) 
Then one sets \(\mathbf {b}_1[i]\)  (\(i \in [k]\) ) to \(-2 \times |\delta _i| + 1\) .
Overall, we get that for every \(i \in [k]\) , \(y_i = 1\)  if the clause \(\delta _i\)  is falsified by \(\mathbf {x}\)  and \(y_i < 0\)  if \(\delta _i\)  is satisfied by \(\mathbf {x}\) .
As to batch normalization, for every \(i \in [k]\) , we set the parameters \(\alpha _{1_i} = \nu _{1_i}\)  to 1, and \(\mu _{1_i} = \gamma _{1_i}\)  to 0,
so that the output of the transformation coincides with its input. Finally, the binarization transformation takes place. Clearly enough, the output
of the internal block of \(N\)  is a vector \({\mathbf {x}^{\prime }} = (x^{\prime }_1, \ldots x^{\prime }_k) \in \lbrace -1, 1\rbrace ^k\)  such that
for every \(i \in [k]\) , \(x^{\prime }_i = 1\)  if \(\mathbf {x}\)  falsifies \(\delta _i\)  and \(x^{\prime }_i = -1\)  if \(\mathbf {x}\)  satisfies \(\delta _i\) .
By construction, this vector \({\mathbf {x}^{\prime }}\)  is the input of the output block \(O\)  of \(N\) .
Let us recall that the output value \(o\)  of \(O\)  is the output of \(N\) , it is a value in \(\lbrace 1, 2\rbrace \)  indicating whether or not the input \(\mathit {transl}(\mathbf {x})\)  is
classified positively by \(N\) . The linear transformation used in \(O\)  is given by \(\mathbf {A}_d \in \lbrace -1, 1\rbrace ^{2 \times k}\)  and \(\mathbf {b}_d \in \mathbb {R}^2\)  such that
\(\mathbf {A}_d[1] = (\underbrace{1, \ldots , 1}_k)\)  and \(\mathbf {A}_d[2] = \underbrace{(-1, \ldots , -1)}_k\) , while \(\mathbf {b}_d[1] = 2k\)  and \(\mathbf {b}_d[2] = 1\) .
As such, when the instance \(\mathbf {x}\)  satisfies \(\rho \) , it satisfies every clause of it and the coordinate \(w_2\)  of the output \(\mathbf {w}\)  of the linear transformation
\({\bf w} = \mathbf {A}_d {\mathbf {x}^{\prime }} + \mathbf {b}_d\)  is equal to \(k+1\) , while its coordinate \(w_1\)  is equal to \(k\) . Contrariwise, when the instance \(\mathbf {x}\) 
does not satisfy \(\rho \) , we have \(w_2 \le k\)  and \(w_1 \ge k+1\) . As a consequence, the last transformation of \(O\)  (the ARGMAX layer)
will return \(o = 2\)  when \(\mathbf {x}\)  satisfies \(\rho \)  and \(o = 1\)  otherwise.
Thus, \(N\)  can be viewed as a representation of the CNF formula \(\rho \)  modulo the translation mapping \(\mathit {transl}\) , in the sense \(\forall \mathbf {x} \in \mathbb {B}^n\) ,
\(\rho (\mathbf {x}) = c\)  if only if \(N(\mathit {transl}(\mathbf {x})) = c+1\) .

