Pablo Barceló
email: pbarcelo@ing.puc.cl

Mikaël Monet
email: mikael.monet@inria.fr

Jorge Pérez

Bernardo Subercaseaux

Model Interpretability through the Lens of Computational Complexity

In spite of several claims stating that some models are more interpretable than others -e.g., "linear models are more interpretable than deep neural networks" -we still lack a principled notion of interpretability to formally compare among different classes of models. We make a step towards such a notion by studying whether folklore interpretability claims have a correlate in terms of computational complexity theory. We focus on local post-hoc explainability queries that, intuitively, attempt to answer why individual inputs are classified in a certain way by a given model. In a nutshell, we say that a class C 1 of models is more interpretable than another class C 2 , if the computational complexity of answering post-hoc queries for models in C 2 is higher than for those in C 1 . We prove that this notion provides a good theoretical counterpart to current beliefs on the interpretability of models; in particular, we show that under our definition and assuming standard complexity-theoretical assumptions (such as P = NP), both linear and tree-based models are strictly more interpretable than neural networks. Our complexity analysis, however, does not provide a clear-cut difference between linear and tree-based models, as we obtain different results depending on the particular post-hoc explanations considered. Finally, by applying a finer complexity analysis based on parameterized complexity, we are able to prove a theoretical result suggesting that shallow neural networks are more interpretable than deeper ones.

Introduction

Assume a dystopian future in which the increasing number of submissions has forced journal editors to use machine-learning systems for automatically accepting or rejecting papers. Someone sends his/her work to the journal and the answer is a reject, so the person demands an explanation for the decision. The following are examples of three alternative ways in which the editor could provide an explanation for the rejection given by the system:

1. In order to accept the submitted paper it would be enough to include a better motivation and to delete at least two mathematical formulas.

2. Regardless of the content and the other features of this paper, it was rejected because it has more than 10 pages and a font size of less than 11pt.

3. We only accept 1 out of 20 papers that do not cite any other paper from our own journal. In order to increase your chances next time, please add more references.

These are examples of so called local post-hoc explanations [START_REF] Arrieta | Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI[END_REF][START_REF] Guidotti | A survey of methods for explaining black box models[END_REF][START_REF] Lipton | The mythos of model interpretability[END_REF][START_REF] Molnar | Interpretable machine learning[END_REF][START_REF] Murdoch | Definitions, methods, and applications in interpretable machine learning[END_REF]. Here, the term "local" refers to explaining the verdict of the system for a particular input [START_REF] Guidotti | A survey of methods for explaining black box models[END_REF][START_REF] Murdoch | Definitions, methods, and applications in interpretable machine learning[END_REF], and the term "post-hoc" refers to interpreting the system after it has been trained [START_REF] Lipton | The mythos of model interpretability[END_REF][START_REF] Molnar | Interpretable machine learning[END_REF]. Each one of the above explanations can be seen as a query asked about a system and an input for it. We call them explainability queries.

The first query is related with the minimum change required to obtain a desired outcome ("what is the minimum change we must make to the article for it to be accepted by the system?"). The second one is known as a sufficient reason [START_REF] Shih | A symbolic approach to explaining Bayesian network classifiers[END_REF], and intuitively asks for a subset of the features of the given input that suffices to obtain the current verdict. The third one, that we call counting completions, relates to the probability of obtaining a particular output given the values in a subset of the features of the input.

In this paper we use explainability queries to formally compare the interpretability of machinelearning models. We do this by relating the interpretability of a class of models (e.g., decision trees) to the computational complexity of answering queries for models in that class. Intuitively the lower the complexity of such queries is, the more interpretable the class is. We study whether this intuition provides an appropriate correlate to folklore wisdom on the interpretability of models [START_REF] Gunning | DARPA's explainable artificial intelligence (XAI) program[END_REF][START_REF] Lipton | The mythos of model interpretability[END_REF][START_REF] Nguyen | Towards interpretable deep neural networks: An exact transformation to multi-class multivariate decision trees[END_REF].

Our contributions. We formalize the framework described above (Section 2) and use it to perform a theoretical study of the computational complexity of three important types of explainability queries over three classes of models. We focus on models often mentioned in the literature as extreme points in the interpretability spectrum: decision trees, linear models, and deep neural networks. In particular, we consider the class of free binary decision diagrams (FBDDs), that generalize decision trees, the class of perceptrons, and the class of multilayer perceptrons (MLPs) with ReLU activation functions. The instantiation of our framework for these classes is presented in Section 3.

We show that, under standard complexity assumptions, the computational problems associated to our interpretability queries are strictly less complex for FBDDs than they are for MLPs. For instance, we show that for FBDDs, the queries minimum-change-required and counting-completions can be solved in polynomial time, while for MLPs these queries are, respectively, NP-complete and #P-complete (where #P is the prototypical intractable complexity class for counting problems). These results, together with results for other explainability queries, show that under our definition for comparing the interpretability of classes of models, FBDDs are indeed more interpretable than MLPs. This correlates with the folklore statement that tree-based models are more interpretable than deep neural networks. We prove similar results for perceptrons: most explainability queries that we consider are strictly less complex to answer for perceptrons than they are for MLPs. Since perceptrons are a realization of a linear model, our results give theoretical evidence for another folklore claim stating that linear models are more interpretable than deep neural networks. On the other hand, the comparison between perceptrons and FBDDs is not definitive and depends on the particular explainability query. We establish all our computational complexity results in Section 4.

Then, we observe that standard complexity classes are not enough to differentiate the interpretability of shallow and deep MLPs. To present a meaningful comparison, we then use the machinery of parameterized complexity [START_REF] Downey | Fundamentals of parameterized complexity[END_REF][START_REF] Flum | Parameterized complexity theory[END_REF], a theory that allows the classification of hard computational problems on a finer scale. Using this theory, we are able to prove that there are explainability queries that are more difficult to solve for deeper MLPs compared to shallow ones, thus giving theoretical evidence that shallow MLPs are more interpretable. This is the most technically involved result of the paper, that we think provides new insights on the complexity of interpreting deep neural networks. We present the necessary concepts and assumptions as well as a precise statement of this result in Section 5.

Most definitions of interpretability in the literature are directly related to humans in a subjective manner [START_REF] Biran | Explanation and Justification in Machine Learning : A Survey[END_REF][START_REF] Doshi-Velez | A Roadmap for a Rigorous Science of Interpretability[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF]. In this respect we do not claim that our complexity-based notion of interpretability is the right notion of interpretability, and thus our results should be taken as a study of the correlation between a formal notion and the folklore wisdom regarding a subjective concept. We discuss this and other limitations of our results in Section 6. We only present a few sketches for proofs in the body of the paper and refer the reader to the appendix for detailed proofs of all our claims.

A framework to compare interpretability

In this section we explain the key abstract components of our framework. The idea is to introduce the necessary terminology to formalize our notion of being more interpretable in terms of complexity.

Models and instances.

We consider an abstract definition of a model M simply as a Boolean function M : {0, 1} n → {0, 1}. That is, we focus on binary classifiers with Boolean input features.

Restricting inputs and outputs to be Booleans makes our setting cleaner while still covering several relevant practical scenarios. A class of models is just a way of grouping models together. An instance is a vector in {0, 1} n and represents a possible input for a model. A partial instance is a vector in {0, 1, ⊥} n , with ⊥ intuitively representing "undefined" components. A partial instance x ∈ {0, 1, ⊥} n represents, in a compact way, the set of all instances in {0, 1} n that can be obtained by replacing undefined components in x with values in {0, 1}. We call these the completions of x.

Explainability queries. An explainability query is a question that we ask about a model M and a (possibly partial) instance x, and refers to what the model M does on instance x. We assume all queries to be stated either as decision problems (that is, YES/NO queries) or as counting problems (queries that ask, for example, how many completions of a partial instance satisfy a given property).

Thus, for now we can think of queries simply as functions having models and instances as inputs. We will formally define some specific queries in the next section, when we instantiate our framework.

Complexity classes. We assume some familiarity with the most common computational complexity classes of polynomial time (PTIME) and nondeterministic polynomial time (NP), and with the notion of hardness and completeness for complexity classes under polynomial time reductions. In the paper we also consider the class Σ p 2 , consisting of those problems that can be solved in NP if we further grant access to an oracle that solves NP queries in constant time. It is strongly believed that PTIME NP Σ p 2 [START_REF] Arora | Computational complexity: a modern approach[END_REF], where for complexity classes K 1 and K 2 we have that K 1 K 2 means the following: problems in K 1 can be solved in K 2 , but complete problems for K 2 cannot be solved in K 1 .

While for studying the complexity of our decision problems the above classes suffice, for counting problems we will need another one. This will be the class #P, which corresponds to problems that can be defined as counting the number of accepting paths of a polynomial-time nondeterministic Turing machine [START_REF] Arora | Computational complexity: a modern approach[END_REF]. Intuitively, #P is the counting class associated to NP: while the prototypical NP-complete problem is checking if a propositional formula is satisfiable (SAT), the prototypical #Pcomplete problem is counting how many truth assignments satisfy a propositional formula (#SAT). It is widely believed that #P is "harder" than Σ p 2 , which we write as Σ p 2 #P. 1Complexity-based interpretability of models. Given an explainability query Q and a class C of models, we denote by Q(C) the computational problem defined by Q restricted to models in C. We define next the most important notion for our framework: that of being more interpretable in terms of complexity (c-interpretable for short). We will use this notion to compare among classes of models. Definition 1. Let Q be an explainability query, and C 1 and C 2 be two classes of models. We say that C 1 is strictly more c-interpretable than

C 2 with respect to Q, if the problem Q(C 1 ) is in the complexity class K 1 , the problem Q(C 2 ) is hard for complexity class K 2 , and K 1 K 2 .
For instance, in the above definition one could take K 1 to be the PTIME class and K 2 to be the NP class, or

K 1 = NP and K 2 = Σ p 2 .

Instantiating the framework and main results

Here we instantiate our framework on three important classes of Boolean models and explainability queries, and then present our main theorems comparing such models in terms of c-interpretability.

Specific models

Binary decision diagrams. A binary decision diagram (BDD [START_REF] Wegener | BDDs-design, analysis, complexity, and applications[END_REF]) is a rooted directed acyclic graph M with labels on edges and nodes, verifying: (i) each leaf is labeled with true or with false;

(ii) each internal node (a node that is not a leaf) is labeled with an element of {1, . . . , n}; and

(iii) each internal node has an outgoing edge labeled 1 and another one labeled 0. Every instance x = (x 1 , . . . , x n ) ∈ {0, 1} n defines a unique path π x from the root to a leaf in M, which satisfies the following condition: for every non-leaf node u in π x , if i is the label of u, then the path π x goes through the edge that is labeled with x i . The instance x is positive, i.e., M(x) := 1, if the label of the leaf in the path π x is true, and negative otherwise. The size |M| of M is its number of edges. A binary decision diagram M is free (FBDD) if for every path from the root to a leaf, no two nodes on that path have the same label. A decision tree is simply an FBDD whose underlying graph is a tree.

Multilayer perceptron (MLP).

A multilayer perceptron M with k layers is defined by a sequence of weight matrices W (1) , . . . , W (k) , bias vectors b (1) , . . . , b (k) , and activation functions f (1) , . . . , f (k) . Given an instance x, we inductively define

h (i) := f (i) (h (i-1) W (i) + b (i) ) (i ∈ {1, . . . , k}), (1)
assuming that h (0) := x. The output of M on x is defined as M(x) := h (k) . In this paper we assume all weights and biases to be rational numbers. That is, we assume that there exists a sequence of positive integers

d 0 , d 1 , . . . , d k such that W (i) ∈ Q di-1×di and b (i) ∈ Q di .
The integer d 0 is called the input size of M, and d k the output size. Given that we are interested in binary classifiers, we assume that d k = 1. We say that an MLP as defined above has (k -1) hidden layers. The size of an MLP M, denoted by |M|, is the total size of its weights and biases, in which the size of a rational number p /q is log 2 (p) + log 2 (q) (with the convention that log 2 (0) = 1).

We focus on MLPs in which all internal functions f (1) , . . . , f (k-1) are the ReLU function relu(x) := max(0, x). Usually, MLP binary classifiers are trained using the sigmoid as the output function f (k) . Nevertheless, when an MLP classifies an input (after training), it takes decisions by simply using the pre activations, also called logits. Based on this and on the fact that we only consider already trained MLPs, we can assume without loss of generality that the output function f (k) is the binary step function, defined as step(x) := 0 if x < 0, and step(x) := 1 if x ≥ 0.

Perceptron. A perceptron is an MLP with no hidden layers (i.e., k = 1). That is, a perceptron M is defined by a pair (W , b) such that W ∈ Q d×1 and b ∈ Q, and the output is M(x) = step(xW +b).

Because of its particular structure, a perceptron is usually defined as a pair (w, b) with w a rational vector and b a rational number. The output of M(x) is then 1 if and only if x, w + b ≥ 0, where x, w denotes the dot product between x and w.

Specific queries

Given instances x and y, we define d(x, y) := n i=1 |x i -y i | as the number of components in which x and y differ. We now formalize the minimum-change-required problem, which checks if the output of the model can be changed by flipping the value of at most k components in the input.

Problem: MINIMUMCHANGEREQUIRED (MCR)

Input: Model M, instance x, and k ∈ N Output: YES, if there exists an instance y with d(x, y) ≤ k and M(x) = M(y), and NO otherwise Notice that, in the above definition, instead of "finding" the minimum change we state the problem as a YES/NO query (a decision problem) by adding an additional input k ∈ N and then asking for a change of size at most k. This is a standard way of stating a problem to analyze its complexity [START_REF] Arora | Computational complexity: a modern approach[END_REF]. Moreover, in our results, when we are able to solve the problem in PTIME then we can also output a minimum change, and it is clear that if the decision problem is hard then the optimization problem is also hard. Hence, we can indeed state our problems as decision problems without loss of generality.

To introduce our next query, recall that a partial instance is a vector y = (y 1 , . . . , y n ) ∈ {0, 1, ⊥} n , and a completion of it is an instance x = (x 1 , . . . , x n ) ∈ {0, 1} n such that for every i where y i ∈ {0, 1} it holds that x i = y i . That is, x coincides with y on all the components of y that are not ⊥. Given an instance x and a model M, a sufficient reason for x with respect to M [START_REF] Shih | A symbolic approach to explaining Bayesian network classifiers[END_REF] is a partial instance y, such that x is a completion of y and every possible completion x of y satisfies M(x ) = M(x). That is, knowing the value of the components that are defined in y is enough to determine the output M(x). Observe that an instance x is always a sufficient reason for itself, and that x could have multiple (other) sufficient reasons. However, given an instance x, the sufficient reasons of x that are most interesting are those having the least possible number of defined components; indeed, it is clear that the less defined components a sufficient reason has, the more information it provides about the decision of M on x. For a partial instance y, let us write y for its number of components that are not ⊥. The previous observations then motivate our next interpretability query.

Problem: MINIMUMSUFFICIENTREASON (MSR) Input: Model M, instance x, and k ∈ N Output: YES, if there exists a sufficient reason y for x wrt. M with y ≤ k, and NO otherwise

As for the case of MCR, notice that we have formalized this interpretability query as a decision problem. The last query that we will consider refers to counting the number of positive completions for a given partial instance.

Problem: COUNTCOMPLETIONS (CC) Input: Model M, partial instance y Output: The number of completions x of y such that M(x) = 1

Intuitively, this query informs us on the proportion of inputs that are accepted by the model, given that some particular features have been fixed; or, equivalently, on the probability that such an instance is accepted, assuming the other features to be uniformly and independently distributed.

Main interpretability theorems

We can now state our main theorems, which are illustrated in Figure 1. In all these theorems we use C MLP to denote the class of all models (functions from {0, 1} n to {0, 1}) that are defined by MLPs, and similarly for C FBDD and C Perceptron . The proofs for all these results will follow as corollaries from the detailed complexity analysis that we present in Section 4. We start by stating a strong separation between FBDDs and MLPs, which holds for all the queries presented above. Theorem 2. C FBDD is strictly more c-interpretable than C MLP with respect to MCR, MSR, and CC.

For the comparison between perceptrons and MLPs, we can establish a strict separation for MCR and MSR , but not for CC. In fact, CC has the same complexity for both classes of models, which means that none of these classes strictly "dominates" the other in terms of c-interpretability for CC. Theorem 3. C Perceptron is strictly more c-interpretable than C MLP with respect to MCR and MSR. In turn, the problems CC(C Perceptron ) and CC(C MLP ) are both complete for the same complexity class.

The next result shows that, in terms of c-interpretability, the relationship between FBDDs and perceptrons is not clear, as each one of them is strictly more c-interpretable than the other for some explainability query.

Theorem 4. The problems MCR(C FBDD ) and MCR(C Perceptrons ) are both in PTIME. However, C Perceptron is strictly more c-interpretable than C FBDD with respect to MSR, while C FBDD is strictly more c-interpretable than C Perceptron with respect to CC.

We prove these results in the next section, where for each query Q and class of models C we pinpoint the exact complexity of the problem Q(C).

MLPs FBDDs Perceptrons

MCR, MSR MCR, MSR, CC CC MSR Figure 1: Illustration of the main interpretability results. Arrows depict that the pointed class of models is harder with respect to the query that labels the edge. We omit labels (or arrows) when a problem is complete for the same complexity class for two classes of models. In this section we present our technical complexity results proving Theorems 2, 3, and 4. We divide our results in terms of the queries that we consider. We also present a few other complexity results that we find interesting on their own. A summary of the results is shown in Table 1. With the exception of Proposition 6, items (1) and ( 3), the proofs for this section are relatively routine, were already known or follow from known techniques. As mentioned in the introduction, we only present the main ideas of some of the proofs in the body of the paper, and a detailed exposition of each result can be found in the appendix.

The complexity of MINIMUMCHANGEREQUIRED

In what follows we determine the complexity of the MINIMUMCHANGEREQUIRED problem for the three classes of models that we consider. Proposition 5. The MINIMUMCHANGEREQUIRED query is (1) in PTIME for FBDDs, (2) in PTIME for perceptrons, and (3) NP-complete for MLPs.

Proof sketch. This query has been shown to be solvable in PTIME for ordered binary decision diagrams (OBDDs, a restricted form of FBDDs) by Shih et al. [START_REF] Shih | Formal verification of Bayesian network classifiers[END_REF]Theorem 6] (the query is called robusteness in the work of Shih et al. [START_REF] Shih | Formal verification of Bayesian network classifiers[END_REF]). We show that the same proof applies to FBDDs. Recall that in an FBDD every internal node is labeled with a feature index in {1, . . . , n}. The main idea is to compute a quantity mcr u (x) ∈ N ∪ {∞} for every node u of the FBDD M. This quantity represents the minimum number of features that we need to flip in x to modify the classification M(x) if we are only allowed to change features associated with the paths from u to some leaf in the FBDD. One can easily compute these values by processing the FBDD bottom-up. Then the minimum change required for x is the value mcr r (x) where r is the root of M, and thus we simply return YES if mcr r (x) ≤ k, and NO otherwise.

For the case of a perceptron M = (w, b) and of an instance x, let us assume without loss of generality that M(x) = 1. We first define the importance s(i) ∈ Q of every input feature at position i as follows: if x i = 1 then s(i) := w i , and if x i = 0 then s(i) := -w i . Consider now the set S that contains the top k most important input features for which s(i) > 0. We can easily show that it is enough to check whether flipping every feature in S changes the classification of x, in which case we return YES, and return NO otherwise.

Finally, NP membership of MCR for MLPs is clear: guess a partial instance y with d(x, y) ≤ k and check in polynomial time that M(x) = M(y). We prove hardness with a simple reduction from the VERTEXCOVER problem for graphs, which is known to be NP-complete.

Notice that this result immediately yields Theorems 2, 3, and 4 for the case of MCR.

The complexity of MINIMUMSUFFICIENTREASON

We now study the complexity of MINIMUMSUFFICIENTREASON. The following result yields Theorems 2, 3, and 4 for the case of MSR. Proposition 6. The MINIMUMSUFFICIENTREASON query is (1) NP-complete for FBDDs (and hardness holds already for decision trees), [START_REF] Arora | Computational complexity: a modern approach[END_REF] in PTIME for perceptrons, and (3) Σ p 2 -complete for MLPs.

Proof sketch. Membership of the problem in the respective classes is easy. We show NP-completeness of the problem for FBDDs by a nontrivial reduction from the NP-complete problem of determining whether a directed acyclic graph has a dominating set of size at most k [START_REF] King | Approximation algorithms for guarding 1.5 dimensional terrains[END_REF]. For a perceptron M = (w, b) and an instance x, assume without loss of generality that M(x) = 1. As in the proof of Proposition 5, we consider the importance of every component of x, and prove that it is enough to check whether the k most important features of x are a sufficient reason for it, in which case we return YES, and simply return NO otherwise. Finally, the Σ p 2 -completeness for MLPs is obtained again using a technical reduction from the problem called SHORTEST IMPLICANT CORE, defined and shown to be Σ p 2 -complete by Umans [START_REF] Umans | The minimum equivalent DNF problem and shortest implicants[END_REF].

To refine our analysis, we also consider the natural problem of checking if a given partial instance is a sufficient reason for an instance.

Problem: CHECKSUFFICIENTREASON (CSR) Input: Model M, instance x and a partial instance y Output: YES, if y is a sufficient reason for x wrt. M, and NO otherwise We obtain the following (easy) result. Proposition 7. The query CHECKSUFFICIENTREASON is (1) in PTIME for FBDDs, (2) in PTIME for perceptrons, and (3) co-NP-complete for MLPs.

We note that this result for FBDDs already appears in [START_REF] Darwiche | A knowledge compilation map[END_REF] (under the name of implicant check). Interestingly, we observe that this new query maintains the comparisons in terms of c-interpretability, in the sense that C FBDD and C Perceptron are strictly more c-interpretable than C MLP with respect to CSR.

The complexity of COUNTCOMPLETIONS

What follows is our main complexity result regarding the query COUNTCOMPLETIONS, which yields Theorems 2, 3, and 4 for the case of CC. Proposition 8. The query COUNTCOMPLETIONS is (1) in PTIME for FBDDs, (2) #P-complete for perceptrons, and (3) #P-complete for MLPs.

Proof sketch. Claim (1) is a a well-known fact that is a direct consequence of the definition of FBDDs; indeed, we can easily compute by bottom-up induction of the FBDD a quantity representing for each node the number of positive completions of the sub-FBDD rooted at that node (e.g., see [START_REF] Darwiche | A knowledge compilation map[END_REF][START_REF] Wegener | BDDs-design, analysis, complexity, and applications[END_REF]). We prove (2) by showing a reduction from the #P-complete problem #KNAPSACK, i.e., counting the number of solutions to a 0/1 knapsack input. 2 For the last claim, we show that MLPs with ReLU activations can simulate arbitrary Boolean formulas, which allows us to directly conclude (3) since counting the number of satisfying assignments of a Boolean formula is #P-complete.

Comparing perceptrons and MLPs. Although the query COUNTCOMPLETIONS is #P-complete for perceptrons, we can still show that the complexity goes down to PTIME if we assume the weights and biases to be integers given in unary; this is commonly called pseudo-polynomial time. Proposition 9. The query COUNTCOMPLETIONS can be solved in pseudo-polynomial time for perceptrons (assuming the weights and biases to be integers given in unary).

Proof sketch. This is proved by first reducing the problem to #KNAPSACK, and then using a classical dynamic programming algorithm to solve #KNAPSACK in pseudo-polynomial time.

This result establishes a difference between perceptrons and MLPs in terms of CC, as this query remains #P-complete for the latter even if weights and biases are given as integers in unary. Another difference is established by the fact that COUNTCOMPLETIONS for perceptrons can be efficiently approximated, while this is not the case for MLPs. To present this idea, we briefly recall the notion of fully polynomial randomized approximation scheme (FPRAS [START_REF] Jerrum | Random generation of combinatorial structures from a uniform distribution[END_REF]), which is heavily used to refine the analysis of the complexity of #P-hard problems. Intuitively, an FPRAS is a polynomial time algorithm that computes with high probability a (1 -)-multiplicative approximation of the exact solution, for > 0, in polynomial time in the size of the input and in the parameter 1/ . We show: Proposition 10. The problem COUNTCOMPLETIONS restricted to perceptrons admits an FPRAS (and the use of randomness is not even needed in this case). This is not the case for MLPs, on the other hand, at least under standard complexity assumptions.

Parameterized results for MLPs in terms of number of layers

In Section 4.1 we proved that the query MINIMUMCHANGEREQUIRED is NP-complete for MLPs. Moreover, a careful inspection of the proof reveals that MCR is already NP-hard for MLPs with only a few layers. This is not something specific to MCR: in fact, all lower bounds for the queries studied in the paper in terms of MLPs hold for a small, fixed number of layers. Hence, we cannot differentiate the interpretability of shallow and deep MLPs with the complexity classes that we have used so far.

In this section, we show how to construct a gap between the (complexity-based) interpretability of shallow and deep MLPs by considering refined complexity classes in our c-interpretability framework. In particular, we use parameterized complexity [START_REF] Downey | Fundamentals of parameterized complexity[END_REF][START_REF] Flum | Parameterized complexity theory[END_REF], a branch of complexity theory that studies the difficulty of a problem in terms of multiple input parameters. To the best of our knowledge, the idea of using parameterized complexity theory to establish a gap in the complexity of interpreting shallow and deep networks is new.

We first introduce the main underlying idea of parameterized complexity in terms of two classical graph problems: VERTEXCOVER and CLIQUE. In both problems the input is a pair (G, k) with G a graph and k an integer. In VERTEXCOVER we verify if there exists a set of nodes of size at most k that includes at least one endpoint for every edge in G. In CLIQUE we check if there exists a set of nodes of size at most k such that all nodes in the set are adjacent to each other. Both problems are known to be NP-complete. However, this analysis treats G and k at the same level, which might not be fair in some practical situations in which k is much smaller than the size of G. Parameterized complexity then studies how the complexity of the problems behaves when the input is only G, and k is regarded as a small parameter.

It happens to be the case that VERTEXCOVER and CLIQUE, while both NP-complete, have a different status in terms of parameterized complexity. Indeed, VERTEXCOVER can be solved in time O(2 k • |G|), which is polynomial in the size of the input G -with the exponent not depending on k -and, thus, it is called fixed-parameter tractable [START_REF] Downey | Fundamentals of parameterized complexity[END_REF]. In turn, it is widely believed that there is no algorithm for CLIQUE with time complexity O(f (k) • poly(G)) -with f being any computable function, that depends only on k -and thus it is fixed-parameter intractable [START_REF] Downey | Fundamentals of parameterized complexity[END_REF]. To study the notion of fixed-parameter intractability, researchers on parameterized complexity have introduced the W[t] complexity classes (with t ≥ 1), which form the so called W-hierarchy. For instance CLIQUE is W[1]-complete [START_REF] Downey | Fundamentals of parameterized complexity[END_REF]. A core assumption in parameterized complexity is that

W[t] W[t + 1], for every t ≥ 1.
In this paper we will use a related hierarchy, called the W(Maj)-hierarchy [START_REF] Fellows | A purely democratic characterization of W[1[END_REF]. We defer the formal definitions of these two hierachies to the appendix. We simply mention here that both classes, W[t] and W(Maj)[t], are closely related to logical circuits of depth t. The circuits that define the Whierarchy use gates AND, OR and NOT, while circuits for W(Maj) use only the MAJORITY gate (which outputs a 1 if more than half of its inputs are 1). Our result below applies to a special class of MLPs that we call restricted-MLPs (rMLPs for short), where we assume that the number of digits of each weight and bias in the MLP is at most logarithmic in the number of neurons in the MLP (a detailed exposition of this restriction can be found in the appendix). We can now formally state the main result of this section. Proposition 11. For every t ≥ 1 the MINIMUMCHANGEREQUIRED query over rMLPs with 3t + 3 layers is W(Maj)[t]-hard and is contained in W(Maj)[3t + 7].

By assuming that the W(Maj)-hierarchy is strict, we can use Proposition 11 to provide separations for rMLPs with different numbers of layers. For instance, instantiating the above result with t = 1 we obtain that for rMLPs with 6 layers, the MCR problem is in W(Maj)[3t + 7] = W(Maj) [START_REF] Doshi-Velez | A Roadmap for a Rigorous Science of Interpretability[END_REF]. Moreover, instantiating it with t = 11 we obtain that for rMLPs with 36 layers, the MCR problem is W(Maj) [START_REF] Downey | Fixed-Parameter Tractability and Completeness I: Basic Results[END_REF]-hard. Thus, assuming that W(Maj) [START_REF] Doshi-Velez | A Roadmap for a Rigorous Science of Interpretability[END_REF] W(Maj) [START_REF] Downey | Fixed-Parameter Tractability and Completeness I: Basic Results[END_REF] we obtain that rMLPs with 6 layers are strictly more c-interpretable than rMLPs with 36 layers. We generalize this observation in the following result.

Proposition 12. Assume that the W(Maj)-hierarchy is strict. Then for every t ≥ 1 we have that rMLPs with 3t + 3 layers are strictly more c-interpretable than rMLPs with 9t + 27 layers wrt. MCR.

6 Discussion and concluding remarks Related work. The need for model interpretability in machine learning has been heavily advocated during the last few years, with works covering theoretical and practical issues [START_REF] Arrieta | Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI[END_REF][START_REF] Guidotti | A survey of methods for explaining black box models[END_REF][START_REF] Lipton | The mythos of model interpretability[END_REF][START_REF] Molnar | Interpretable machine learning[END_REF][START_REF] Murdoch | Definitions, methods, and applications in interpretable machine learning[END_REF]. Nevertheless, a formal definition of interpretability has remained elusive [START_REF] Lipton | The mythos of model interpretability[END_REF]. In parallel, a related notion of interpretability has emerged from the field of knowledge compilation [START_REF] Darwiche | A knowledge compilation map[END_REF][START_REF] Shi | On tractable representations of binary neural networks[END_REF][START_REF] Shih | Formal verification of Bayesian network classifiers[END_REF][START_REF] Shih | A symbolic approach to explaining Bayesian network classifiers[END_REF][START_REF] Shih | Verifying binarized neural networks by Angluin-style learning[END_REF]. The intuition here is to construct a simpler and more interpretable model from a complex one. One can then study the simpler model to understand how the initial one makes predictions. Motivated by this, Darwiche and Hirth [START_REF] Darwiche | On the reasons behind decisions[END_REF] use variations of the notion of sufficient reason to explore the interpretability of Ordered BDDs (OBDDs). The FBDDs that we consider in our work generalize OBDDs, and thus, our results for sufficient reasons over FBDDs can be seen as generalizations of the results in [START_REF] Darwiche | On the reasons behind decisions[END_REF]. We consider FBDDs instead of OBDDs as FBDDs subsume decision trees, while OBDDs do not. We point out here that the notion of sufficient reason for a Boolean classifier is the same as the notion of implicant for a Boolean function, and that minimal sufficient reasons (with minimailty refering to subset-inclusion of the defined components) correspond to prime implicants [START_REF] Darwiche | A knowledge compilation map[END_REF]. We did not incorporate a study of minimal sufficient reasons (also called PI-explanations) to our work due to space constraints. In a contemporaneous work [START_REF] Marques-Silva | Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay[END_REF], Marques-Silva et al. study the task of enumerating the minimal sufficient reasons of naïve Bayes and linear classifiers. The queries COUNTCOMPLETIONS and CHECKSUFFICIENTREASON have already been studied for FBDDs in [START_REF] Darwiche | A knowledge compilation map[END_REF] (CHECKSUFFICIENTREASON under the name of implicant check). The query MINIMUMCHANGEREQUIRED is studied in [START_REF] Shih | Formal verification of Bayesian network classifiers[END_REF] for OBDDs, where it is called robustness. Finally, there are papers exploring queries beyond the ones presented here [START_REF] Shi | On tractable representations of binary neural networks[END_REF][START_REF] Shih | Formal verification of Bayesian network classifiers[END_REF][START_REF] Shih | A symbolic approach to explaining Bayesian network classifiers[END_REF], such as monotonicity, unateness, bias detection, minimum cardinality explanations, etc.

Limitations. Our framework provides a formal way of studying interpretability for classes of models, but still can be improved in several respects. One of them is the use of a more sophisticated complexity analysis that is not so much focused on the worst case complexity study propose here, but on identifying relevant parameters that characterize more precisely how difficult it is to interpret a particular class of models in practice. Also, in this paper we have focused on studying the local interpretability of models (why did the model make a certain prediction on a given input?), but one could also study their global interpretability, that is, making sense of the general relationships that a model has learned from the training data [START_REF] Murdoch | Definitions, methods, and applications in interpretable machine learning[END_REF]. Our framework can easily be extended to the global setting by considering queries about models, independent of the input it receives. In order to avoid the difficulties of defining a general notion of interpretability [START_REF] Lipton | The mythos of model interpretability[END_REF], we have used explainability queries and their complexity as a formal proxy. Nonetheless, we do not claim that our notion of complexity-based interpretability is the definitive notion of interpretability. Indeed, most definitions of interpretability are directly related to humans in a subjective manner [START_REF] Biran | Explanation and Justification in Machine Learning : A Survey[END_REF][START_REF] Doshi-Velez | A Roadmap for a Rigorous Science of Interpretability[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF]. Our work is thus to be taken as a study of the correlation between a formal notion of interpretability and the folk wisdom regarding a subjective concept. Finally, even though the notion of complexity-based interpretability gives a precise way to compare models, our results show that it is still dependent on the particular set of queries that one picks. To achieve a more robust formalization of interpretability, one would then need to propose a more general approach that prescinds of specific queries. This is a challenging problem for future research.

Broader impact

Although interpretability as a subject may have a broad practical impact, our results in this paper are mostly theoretic, so we think that this work does not present any foreseeable societal consequences. assigns to every gate of C a level such that (i) every variable gate is assigned level 0, and (ii) for any wire g → g (meaning that g is an input to g ) in C we have that l(g ) = l(g) + 1. To this end, let us call a relu gate that has a single input and weight 1 and bias 0 an identity gate, and observe then that the value of an identity gate is the same as the value of its only input, when this input is in {0, 1}. We will obtain C from C by inserting identity gates in between the gates of C , which clearly does not change the Boolean function being computed. We can do so naïvely as follows. First, we initialize l(g) to 0 for all the variable gates g of C . We then iterate the following process: select a gate g such that l(g) is undefined and such that l(g ) is defined for every input g of g. Let g 1 , . . . , g m be the inputs of g, and assume that l(g 1 ) ≤ . . . ≤ l(g m ). For every 1 ≤ i ≤ m, we insert a line of l(g m ) -l(g i ) identity gates in between g i and g, and we set l(g) := l(g m ) + 1, and we set the levels of the identity gates that we have inserted appropriately. It is clear that this construction can be done in polynomial time and that the resulting circuit C is layerized.

Finally, the last step is to transform C into an MLP M C using only relu for the internal activation functions and the step function for the output layer (i.e., what we simply call "an MLP" in the paper), and that respects the structure given by our definition in Section 3.1 (i.e., where all neurons of a given layer are connected to all the neurons of the preceding layer). We first deal with having a step gate instead of a relu gate for the output. To achieve this, we create a fresh identity gate g 0 , we set the output of C to be an input of g 0 , and we set g 0 to be the new output gate of C (this does not change the Boolean function computed). We then replace g 0 by a step gate (which, we recall, on input x ∈ R outputs 0 if x < 0 and 1 otherwise) with a weight of 2 and bias of -1, which again does not change the Boolean function computed; indeed, for x ∈ {0, 1}, we have that step(2x

-1) = 1 if x = 1 0 if x = 0 .
The level of g 0 is one plus the level of the previous output gate of C . Therefore, to make C become a valid MLP, it is enough to do the following: for every gate g of level i and gate g of level i + 1, if g and g are not connected in C , we make g be an input of g and we set the corresponding weight to 0. This clearly does not change the function computed, and the obtained circuit can directly be regarded as an equivalent MLP M C . Since the whole construction can be performed in polynomial time, this concludes the proof.

By definition, if u is a leaf labeled with true we have that M u (y) = 1 for every y, and thus if M(x) = 0 we get mcr u (x) = 0, while if M(x) = 1 we get that mcr u (x) = ∞. Analogously, if u is a leaf labeled with false, then mcr u (x) is equal to 0 if M(x) = 1 and to ∞ otherwise.

For the recursive case, we consider a non-leaf node u. Let u 1 be the node going along the edge labeled with 1 from u, and u 0 analogously. Using the notation [x u = a] to mean 1 if the feature of x indexed by the label of node u has value a ∈ {0, 1}, and 0 otherwise, and the convention that ∞ + 1 = ∞, we claim that:

mcr u (x) = min [x u = 1] + mcr u0 (x), [x u = 0] + mcr u1 (x)
Indeed, consider by inductive hypothesis that mcr u0 (x) and mcr u1 (x) have been properly calculated, and let us show that this equality holds. We prove both inequalities in turn:

• We show that mcr u (x) ≤ min [x u = 1] + mcr u0 (x), [x u = 0] + mcr u1 (x) . It is enough to show that both mcr u (x) ≤ [x u = 1] + mcr u0 (x) and mcr u (x) ≤ [x u = 0] + mcr u1 (x)
hold. We only show the first inequality, as the other one is similar. If mcr u0 (x) = ∞ then clearly the inequality holds, hence let us assume that mcr u0 (x) = k ∈ N. This means that there is an instance y such that d(x, y ) = k and such that M u0 (y ) = M(x). Furthermore, by the observation ( †) we have that for any node u from the root of M to u (included), we have y u = x u . Therefore, the instance y that is equal to y but has value

y u = 0 differs from x in exactly k = [x u = 1] + k , which implies that mcr u (x) ≤ [x u = 1] + mcr u0 (x).
Hence, the first inequality is proven.

• We show that mcr u (x) ≥ min [x u = 1] + mcr u0 (x), [x u = 0] + mcr u1 (x) . First, assume that both mcr u0 (x) and mcr u1 (x) are equal to ∞. This means that every path in both M u0 and M u1 leads to a leaf with the same classification as M(x). Then, as every path from u goes either through u 0 or through u 1 , it must be that every path from u leads to a leaf with the same classification as M(x), and thus mcr u (x) = ∞, and so the inequality holds. Therefore, we can assume that one of mcr u0 (x) or mcr u1 (x) is finite. Let us assume without loss of generality that ( ) min [x u = 1] + mcr u0 (x), [x u = 0] + mcr u1 (x) = [x u = 1] + mcr u0 (x) ∈ N (the other case being similar). Let us now assume, by way of contradiction, that the inequality does not hold, that is, we have that ( † †) mcr u (x) < [x u = 1] + mcr u0 (x), and let y be an instance such that M u (y) = M u (x) and d(x, y) = mcr u (x). Thanks to ( ), we can assume wlog that y u = 0. But then we would have that mcr u0 (x) ≤ mcr u (x) -[x u = 1], which contradicts ( † †). Hence, the second inequality is proven.

It is clear that the recursive function mcr can be computed bottom-up in linear time, thus concluding the proof.

Lemma 15. The MINIMUMCHANGEREQUIRED query can be solved in linear time for perceptrons.

Proof. Let (M = (w, b), x, k) be an instance of the problem, and let us assume without loss of generality that M(x) = 1, as the other case is analogous. For each feature i of x we define its importance s(i) as w i if x i = 1 and -w i otherwise. Intuitively, s represents how good it is to keep a certain feature in order to maintain the verdict of the model. We now assume that x and w have been sorted in decreasing order of score s (paying the cost of a sorting procedure) . For example, if originally w = (3, -5, -2) and x = (1, 0, 1), then after the sorting procedure we have w = (-5, 3, -2) and x = (0, 1, 1). This sorting procedure has cost O(|M|) as it is a classical problem of sorting strings whose total length add up to M and can be carried with a variant of Bucketsort [START_REF] Cormen | Introduction to Algorithms[END_REF]. As a result, for every pair 1 ≤ i < j ≤ n we have that s(i) ≥ s(j). Let k be the largest integer no greater than k such that s(k ) > 0 and then define x as the instance that differs from x exactly on the first k features. We claim that M(x ) = M(x) if and only if (M, x, k) is a positive instance of MINIMUMCHANGEREQUIRED. The forward direction follows from the fact that k ≤ k. For the backward direction, assume that (M, x, k) is a positive instance of MINIMUMCHANGEREQUIRED. This implies that there is an instance y that differs from x in at most k features, and for which M(y) = 0. If y = x , then we are immediately done, so we can safely assume this is not the case.

We then define, for any instance y of M the function v(y) = w, y . Note that an instance y of M is positive if and only if v(y) ≥ -b. Then, since we have that M(y) = 0, it holds that v(y) < -b.

We now claim that v(x ) ≤ v(y):

Claim 16. For every instance y such that d(y, x) ≤ k and M(y) = M(x), it must hold that v(x ) ≤ v(y).

Proof. For an instance z, let us write C z for the set of features for which z differs from x. We then have on the one hand

v(x ) = i∈C x \Cy (1 -x i )w i + i∈Cy∩C x (1 -x i )w i + i ∈C x ∪Cy x i w i + i∈Cy\C x x i w i
and on the other hand

v(y) = i∈Cy\C x (1 -x i )w i + i∈Cy∩C x (1 -x i )w i + i ∈C x ∪Cy x i w i + i∈C x \Cy x i w i
As the two middle terms are shared, we only need to prove that

i∈C x \Cy (1 -x i )w i + i∈Cy\C x x i w i ≤ i∈Cy\C x (1 -x i )w i + i∈C x \Cy x i w i
which is equivalent to proving that i∈C x \Cy,xi=0

w i + i∈Cy\C x ,xi=1 w i ≤ i∈Cy\C x ,xi=0 w i + i∈C x \Cy,xi=1
w i and by using the definition of importance, equivalent to

i∈C x \Cy,xi=0 -s(i) + i∈Cy\C x ,xi=1 s(i) ≤ i∈Cy\C x ,xi=0
-s(i)

+ i∈C x \Cy,xi=1 s(i)
which can be rearranged into

i∈Cy\C x s(i) ≤ i∈C x \Cy s(i)
But this inequality must hold as C x is by definition the set C of features of size at most k that maximizes i∈C s(i).

Because of the claim, and the fact that v(y) < -b we conclude that v(x ) < -b, and thus M(x ) = M(x). This concludes the backward direction, and thus, the fact that checking whether M(x ) = M(x) is enough to solve the entire problem. Since checking this can be done in linear time, constructing x is the most expensive part of the process, which can effectively be done in time O(|M|). This concludes the proof of the lemma.

Lemma 17. The MINIMUMCHANGEREQUIRED query is NP-complete for MLPs.

Proof. Membership is easy to see, it is enough to non-deterministically guess an instance y and check that d(x, y) ≤ k and M(x) = M(y).

In order to prove hardness, we reduce from VERTEX COVER. Given an undirected graph G = (V, E) and an integer k, the VERTEX COVER problem consists in deciding whether there is a subset S ⊆ V of at most k vertices such that every edge of G touches a vertex in S. Let (G = (V, E), k) be an instance of VERTEX COVER, and let n denote |V |. Based on G, we build a formula ϕ G , where propositional variables correspond to vertices of G.

ϕ G = (u,v)∈E (x u ∨ x v )
It is clear that the satisfying assignments of ϕ G correspond to the vertex covers of G, and furthermore, that a satisfying assignment of Hamming weight k (number of variables assigned to 1) corresponds to a vertex cover of size k.

Moreover, we can safely assume that there is at least 1 edge in G, as otherwise the instance would be trivial, and a constant size positive instance of MCR would finish the reduction. This implies in turn, that we can assume that assigning every variable to 0 does not satisfy ϕ G .

We now build an MLP M ϕ from ϕ G , using Lemma 13. We claim that the instance (M ϕ , 0 n , k) is a positive instance of MINIMUMCHANGEREQUIRED if and only if (G, k) is a positive instance of VERTEX COVER.

Indeed, 0 n is a negative instance of M ϕ , as assigning every variable to 0 does not satisfy ϕ G . Moreover a positive instance of weight k for M ϕ corresponds to a satisfying assignment of weight k for ϕ G , which in turn corresponds to a vertex cover of size k for G. This is enough to conclude conclude the proof, recalling that both the construction of ϕ G and M ϕ take polynomial time.

Appendix C. Proof of Proposition 6

In this section we prove Proposition 6, whose statement we recall here: Proposition 6. The MINIMUMSUFFICIENTREASON query is (1) NP-complete for FBDDs (and hardness holds already for decision trees), (2) in PTIME for perceptrons, and (3) Σ p 2 -complete for MLPs.

Again, we prove each claim separately. Lemma 18. The MINIMUMSUFFICIENTREASON query is NP-complete for FBDDs, and hardness holds already for decision trees.

Proof. Membership in NP is clear, it suffices to guess the instance y and check both that it has less than k defined components and that is a sufficient reason for x, which can be done thanks to Lemma 23. We will prove that hardness holds already for the particular case of decision trees, and when the input instance x is positive. Hardness of this particular setting implies of course the hardness of the general problem. In order to do so, we will reduce from the problem of determining whether a directed acyclic graph has a dominating set of size at most k, which we abbreviate as DOM-DAG. Recall that in a directed graph G = (V, E), a subset of vertices D ⊆ V is said to be dominating if every vertex in V \ D has an incoming edge from a vertex in D. The problem of DOM-DAG is shown to be NP-complete in [START_REF] King | Approximation algorithms for guarding 1.5 dimensional terrains[END_REF].

An illustration of the reduction is presented in Figure 2. Let (G = (V, E), k) be an instance of DOM-DAG, and let us define n := |V |. We start by computing in polynomial time a topological ordering ϕ = ϕ 1 , . . . , ϕ n of G. Next, we will create an instance (T , x, k) of k-SUFFICIENTREASON such that there is a sufficient reason of size at most k for x under the decision tree T if and only if G has a dominating set of size at most k. We create the decision tree T , of dimension n, in 2 steps.

1. Create nodes v 1 , . . . , v n , where node v i is labeled with ϕ i The node v n will be the root of T , and for 2 ≤ i ≤ n, connect v i to v i-1 with an edge labeled with 1. Node v 1 is connected to a leaf labeled true through an edge labeled with 1. We will denote the path created in this step as π.

2. For every vertex ϕ i create a decision tree T i equivalent to the boolean formula

F i = (ϕj ,ϕi)∈E ϕ j
and create an edge from v i to the root of T i labeled with 0. If F i happens to be the empty formula, T i is defined as false. Note that the nodes introduced by this step are all naturally associated with vertices of G.

Step 2 takes polynomial time because boolean formulas in 1-DNF can easily be transformed into a decision tree in linear time. We now check that T is a decision tree. Since T has a tree structure, it is enough to check that for every path from the root to a leaf there are no two nodes on the path that have the same label (i.e., to check that T is a valid FBDD). Note that any path from the root v n to a leaf goes first to a certain node v i in π, from where it either takes an edge labeled with 0, in case i = 1 or it simply goes to a leaf otherwise. In case i = 1, the path from the root goes exactly through v n , v n-1 , . . . , v 1 , which all have different labels. In case i = 1, the path includes (i) nodes with labels ϕ n , ϕ n-1 , . . . , ϕ i , and (ii) a subpath inside T i . It is clear that all the labels in (i) are different. And as by construction T i is a decision tree, no two nodes inside (ii) can have the same label. It remains to check that no node in (i) can have the same label of a node in (ii). To see this, consider that all the vertices of G associated to the nodes in (ii) have edges to ϕ i in G, and thus come before ϕ i in the topological order. But (i) is composed precisely by ϕ i and the nodes who come after it in the topological ordering, so (i) and (ii) have empty intersection.

Let x = 1 n be the vector of n ones. We claim that (T , x, k) is a yes-instance of k-SUFFICIENTREASON if and only if (G, k) is a yes-instance of DOM-DAG.

Forward direction. Consider that there is a sufficient reason y for x under T of size at most k. As x contains only 1s, y must contain only 1s and ⊥s. Consider the set S of components i where y i = 1.

Recalling that every vertex of G is canonically associated with a feature of T , we will denote D S to the set of vertices of G that are associated with the features in S. It is clear that |D S | ≤ k. We now prove that D S is a dominating set of G. First, in case D S = V , we are trivially done. We know assume D S = V . Consider a vertex v ∈ V \ D S , corresponding to ϕ i in the topological ordering, and define z as the completion of y where the features ϕ j such that j > i, are set to 1, and all other features that are undefined by y are set to 0. By hypothesis, z must be a positive instance, and so its path on T must end in a leaf labeled with true. Note that the path of z in T necessarily takes the path π created in Step 1 of the construction, up to the node v i , and then enters its subtree T i . Let t be the node of T i whose leaf labeled with true ends the path of z in T , and ϕ k its label and associated vertex in G. As feature t is set to 1, we must have either ϕ k ∈ D S (in case t is 1 because of y) or k > i (in case t is 1 by the construction of completion z). However, the second case is not actually possible, as if k > i, that means v k comes before v i in path π, and thus the path of z in T passes through v k , which has label ϕ k before passing through v i . But the path of z in T passes through t before ending, which also has label ϕ k . This contradicts the already proven fact that T is a decision tree. We can therefore assume that ϕ k belongs to D S . Then, as t is a node of T i , there must be an edge (ϕ k , ϕ i ) in E because of the way T i is constructed. But this means that vertex v ∈ V \ D S has an edge coming from ϕ k ∈ D S , and so v is effectively dominated by the set D S . As this holds for every v ∈ V \ D S , we conclude that D S is indeed a dominating set of G.

Backward Direction. Consider that there is a dominating set D ⊆ V of size at most k. Let S D be the set of features associated with D. We claim that the partial instance y that has 1 in the features that belong to S D , and is undefined elsewhere, is a sufficient reason for x, and by construction its size is at most k. Consider an arbitrary completion z of y, we need to show that z is a positive instance of T . For z not to be a positive instance, its path on T would have to reach a leaf labeled with false. This can only happen by either taking the edge labeled with 0 from v 1 (the last node in path π built in the construction), or inside a subtree T i , corresponding to a node v i whose associated feature in z is set to 0. We show that neither can happen. For the first case, every dominating set must include ϕ 1 , the vertex in G associated with v 1 , as it is the first element in the topological ordering of G, and thus it must has in-degree 0, which implies ϕ 1 ∈ D. Therefore, it is not possible to take the edge labeled with 0 from v 1 . On the other hand, suppose the path of z in T i ends in a leaf labeled with false. Then, by construction of T i , there is no vertex ϕ j such that (ϕ j , ϕ i ) ∈ E whose associated feature is set to 1 in z. But as D is a dominating set, either there is indeed a ϕ j ∈ D such that (ϕ j , ϕ i ) ∈ E or ϕ i ∈ D. The first case is in direct contradiction with the previous statement, as ϕ j ∈ D implies, by our construction of y that the feature associated with ϕ j is set to 1. The second case also creates a contradiction, as if ϕ i ∈ D, then by construction y would have a 1 in the feature v i associated to ϕ i , which contradicts the assumption of the path of z entering T i .

Lemma 19. The MINIMUMSUFFICIENTREASON query is in PTIME for perceptrons.

Proof. Let (M = (w, b), x, k) be an instance of the problem, and let d be the dimension of the perceptron. We will assume without loss of generality that M(x) = 1. In this proof, what we call a minimum sufficient reason for x is a sufficient reason for x that has the least number of components being defined. We show a greedy algorithm that computes a minimum sufficient reason for x under M in time O(|M|). For each feature i of x we define its importance s(i) as w i if x i = 1 and -w i otherwise (just as we did in the proof of Lemma 15), and its penalty p(i) as min(0, w i ).

Intuitively, s represents how good it is for a partial instance to be defined in a given feature, and p represents the penalty or cost that a partial instance incurs by not being defined in a given feature. We now assume that x and w have been sorted in decreasing order of score s. For example, if originally w = (3, -5, -2) and x = (1, 0, 1), then after the sorting procedure we have w = (-5, 3, -2) and x = (0, 1, 1). We now define a function ψ that takes any partial instance y as input and outputs the worst possible value for a completion of y:

ψ(y) := min z: z is a completion of y w, z = yi =⊥ w i y i + yi=⊥ p(i).
The second equality is easy to see based on the definition of the function p, and the definition of ψ implies that ψ(y) ≥ -b exactly when y is a sufficient reason. For 1 ≤ l ≤ d, we define y l as the partial instance of x such that y l i is equal to x i if i ≤ l and to ⊥ otherwise. In simple terms, y l is the partial instance obtained by taking the first l features of x; continuing our example with x = (0, 1, 1), we have for instance y 2 = (0, 1, ⊥). Let j be the minimum index such that ψ(y j ) ≥ -b. Such an index always exists, because, since x is a positive instance, taking j = d is always a valid index. Note that j can be computed in linear time.

We now prove that ( †) the partial instance y j is a minimum sufficient reason for x. By definition we have that ψ(y j ) ≥ -b, so y j is indeed a sufficient reason for x. We now need to show that y j is minimum. Assume, seeking for a contradiction, that there is a sufficient reason y of x with strictly less components defined than y j ; clearly we can assume without loss of generality that y has exactly j -1 components defined. We will now show that ( ) y j-1 is a also a sufficient reason for x, which is a contradiction since j was assumed to be the minimal index such that y j is a sufficient reason of x, hence proving ( †). If y = y j-1 , we have that ( ) is trivially true. Otherwise, and considering that y and y j-1 have the same size, and that y j-1 is defined exactly on the first j -1 features, there must be at least a pair of features (m, n), with m ≤ j -1 < n, such that y j-1 is defined at feature m and y is not, and on the other hand y is defined at feature n whereas y j-1 is not. In order to finish the proof of ( ), we will prove a simpler claim that will help us conclude.

Claim 20. Assume that there is a pair of features (m, n) with m ≤ j -1 < n such that y m = ⊥, y j-1 m = ⊥ and y n = ⊥, y j-1 n = ⊥, and let y * be the resulting partial instance that is equal to y except that y * m := y j-1 m and y * n := ⊥. Then we have that ψ(y * ) ≥ ψ(y ).

Proof of Claim 20. By definition, ψ(y * ) -ψ(y ) = p(n) -p(m) + w m y j-1 m -w n y n = p(n)p(m) + w m x m -w n x n . But because the features in y j-1 are sorted in decreasing order of score, it must hold that s(m) ≥ s(n). Using this last inequality and reasoning by cases on the values x m , x n and on the signs of w m , w n , one can tediously check that ψ(y * ) -ψ(y ) ≥ 0 and thus ψ(y * ) ≥ ψ(y ).

We now continue with the proof of ( ). As a result of Claim 20, one can iteratively modify y until it becomes equal to y j-1 in such a way that the value of ψ is never decreased along the process, implying therefore that ψ(y j-1 ) ≥ ψ(y ). But ψ(y ) ≥ -b, because y is assumed to be a sufficient reason, hence we have that ψ(y j-1 ) ≥ -b, implying that y j-1 is a sufficient reason for x, and thus concluding the proof of ( ). Therefore, ( †) is proven, and since y j can clearly be computed in polynomial time (in fact, the runtime of the whole procedure is dominated by the sorting subroutine, which again has cost O(|M|) as it is a classical problem of sorting strings whose total length add up to |M| and can be carried with a variant of Bucketsort [START_REF] Cormen | Introduction to Algorithms[END_REF]), this finishes the proof of the lemma; indeed, we can output YES if j ≤ k and NO otherwise.

Lemma 21. The MINIMUMSUFFICIENTREASON query is Σ p 2 -complete for MLPs.

Proof. Membership in Σ p 2 is clear, as one can non-deterministically guess the value of the k features that would make for a sufficient reason, and then use an oracle in co-NP to verify that no completion of that guess has a different classification. To show hardness, we will reduce from the problem SHORTEST IMPLICANT CORE, defined and proven to be Σ p 2 -hard by Umans [34, Theorem 1]. First, we need a few definitions in order to present this problem. A formula in disjunctive normal form (DNF) is a Boolean formula of the form ϕ = t 1 ∨ t 2 ∨ . . . ∨ t n , where each term t i is a conjunction of literals (a literal being a variable of the negation thereof). An implicant for φ is a partial assignment of the variables of φ such that any extension to a full assignment makes the formula evaluate to true; note that we can equivalently see an implicant of φ as what we call a sufficient reason of φ. For a partial assigment C of the variables and for a set of literals t (or conjunction of literals t), we write C ⊆ t when for every variable x, if x ∈ t then C(x) = 1 and if ¬x ∈ t then C(x) = 0 and C(x) is undefined otherwise. An instance of SHORTEST IMPLICANT CORE then consists of a DNF formula ϕ = t 1 ∨ t 2 ∨ . . . ∨ t n , together with an integer k. Such an instance is positive for SHORTEST IMPLICANT CORE when there is an implicant C for ϕ such that C ⊆ t n . 4 Note that the SHORTEST IMPLICANT CORE is closer to the problem at hand than the general SHORTEST IMPLICANT problem, as (minimum) sufficient reasons of an instance x can only induce literals according to x, in a similar fashion of implicants that can only induce literals according to the core t n .

A reduction that does not work, and how to fix it on an example. In order to convey the main intuition, we start by presenting a first tentative of a reduction that does not work. Thanks to Lemma 13 we know that it is possible to build an MLP M ϕ equivalent to ϕ. However, doing so directly creates a problem: we would need to find a convenient instance x such that (ϕ, k) ∈ SHORTEST IMPLICANT CORE if and only if (M ϕ , x, k) ∈ k-SUFFICIENTREASON. A natural idea is to consider t n as a candidate for x, but the issue is that t n does not necessarily include every variable. The next natural idea is to try with x being an arbitrary completion of t n (interpreting t n as the partial instance that is uniquely defined by its satisfying assignment). This approach fails because there could be a sufficient reason of size at most k for such an x that relies on features (variables) that are not in t n . We illustrate this with an example for n = 4.

ϕ := x 1 x 5 ∨ x 2 x 6 ∨ x 3 x 6 ∨ x 1 x 2 x 4 ∨ x 1 x 3 x 5 t4
While it can be checked that (ϕ, 2) ∈ SHORTEST IMPLICANT CORE, we have that (M ϕ , (1, 0, 1, 0, 1, 1), 2) is in fact a positive instance of k-SUFFICIENTREASON, as the partial instance that assigns 1 to x 3 and x 6 and is undefined for the rest of the features, is a sufficient reason of size 2 for x. The issue is that we are allowing x 6 to be part of the sufficient reason for x even though x 6 ∈ t 4 . We can avoid this from happening by splitting each variable that is not in t n , such as x 6 , into k + 1 variables, in such a way that defining the value of x 6 would force us to define the value of all the k + 1 variables, which is of course unaffordable. Continuing with the example, we build the formula ϕ as follows:

ϕ := 3 i=1 x 1 x 5 ∨ x i 2 x i 6 ∨ x 3 x i 6 ∨ x 1 x i 2 x i 4 ∨ x 1 x 3 x 5
Now we can simply take (M ϕ , x, 1) where x is an arbitrary completion of t 4 over the new set of variables, for example, one that assigns 1 to the features 1, 3 and 5, and 0 to all other features (variables). Note that ϕ is not a DNF anymore, but this is not a problem, since we only need to compute M ϕ . It is then easy to check that this instance is equivalent to the original input instance.

The reduction. We now present the correct reduction and prove that it works. Let (ϕ, k) be an instance of SHORTEST IMPLICANT CORE. Let X c be the set of variables that are not mentioned in t n . We split every variable x j ∈ X c into k + 1 variables x 1 j , . . . x k+1 j and for each i ∈ {1, . . . , k + 1} we build ϕ (i) by replacing every occurrence of a variable x j , that belongs to X c , by x i j . Finally we define ϕ as the conjunction of all the ϕ (i) . That is,

ϕ (i) := ϕ[x j → x i j , for all x j ∈ X c ] (2)
ϕ := k+1 i=1 ϕ (i) (3)
Observe that any meaningful instance of SHORTEST IMPLICANT CORE has k < |t n |, so we can safely assume that k is given in unary, making this construction polynomial.

We then use Lemma 13 to build an MLP M ϕ from ϕ , in polynomial time. The features of this model correspond naturally to the variables of ϕ , and thus we refer to both features and variables without distinction. Let y be the instance that assigns 1 to every variable that appears as a positive literal in t n , and 0 to all other variables. We claim that (ϕ, k) ∈ SHORTEST IMPLICANT CORE if and only if (M ϕ , x, k) ∈ k-SUFFICIENTREASON. For the forward direction, if there is an implicant C ⊆ t n of ϕ, of size at most k, then we claim that C is also an implicant of each ϕ (i) . This follows from the fact that every assignment σ that is consistent with C and satisfies ϕ, has a related assignment σ i , that for every variable x j ∈ X c assigns σ i (x i j ) = σ(x j ), and that is equal to σ for every x j ∈ X c . It is clear that σ i (ϕ (i) ) = σ(ϕ), which concludes the claim. As C is an implicant of each ϕ (i) , it must also be an implicant of ϕ . Then, as M ϕ is equivalent to ϕ (as Boolean functions) by construction, and x is consistent with C because it is consistent with t n , it follows that the partial instance that is induced by C is a sufficient reason for x under M ϕ . For the backward direction, assume there is a sufficient reason y for x under M ϕ , whose size is at most k, and let C be its associated implicant for ϕ . We cannot say yet that C is a proper candidate for being an implicant core of ϕ, as C could contain variables not mentioned by t n . Let us define X c to be the set of variables of ϕ that are not present in t n . Intuitively, as there are k + 1 copies of each variable of X c in ϕ , no valuation of a variable in X c , for the formula ϕ, can be forced by a sufficient reason of size at most k. We will prove this idea in the following claim, allowing us to build an implicant C for which we can assure C ⊆ t n .

Claim 22. Assume that there is an implicant C of size at most k for ϕ , and let C be the partial valuation that sets every variable x that appear in t n and that is defined by C to C (x), and that leaves every other variable undefined. Then C is an implicant of size at most k for ϕ.

Proof. The set X c can be expressed as the union of k + 1 disjoint sets of variables, namely X 1 c , . . . , X k+1 c

, where X i c contains all variables of the form x i j . Since C contains at most k literals, and there are k + 1 disjoint sets X i c , there must exist an index l such that X l c ∩ C = ∅. But then this implies that C is an implicant of ϕ (l) . But ϕ (l) is equivalent to ϕ up to renaming of the variables that are not present in C, therefore, the fact that C is an implicant of ϕ (l) implies that C must be an implicant of ϕ as well.

By using Claim 22 we get that C is an implicant of ϕ. But we have that C ⊆ t n , which is enough to conclude that (ϕ, k) ∈ SHORTEST IMPLICANT CORE and finishes the proof of Lemma 21. and let M be the perceptron (w , b ). Notice that the dimension of M is equal to the number of undefined components of x; let us write m this number. It is then clear that COUNTPOSITIVECOMPLETIONS(M, x) is equal to the number of positive instances of M , that is, of instances x ∈ {0, 1} m that satisfy

w , x + b ≥ 0 (4)
Now, let J be the maximum possible value of w , x ; J can clearly be computed in linear time by setting x i = 1 if w i ≥ 0 and x i = 0 otherwise. We then claim that the number of solutions to Equation 4 is equal to the number of solutions of

s, x ≤ k, (5)
where

s i := |w i | for 1 ≤ i ≤ m and k := J + b . Indeed, consider the function h : {0, 1} m → {0, 1} m defined componentwise by h(x i ) := x i if w i < 0 and h(x i ) := 1 -x i otherwise.
Then h is a bijection, and we will show that for any x ∈ {0, 1} m , we have that x satisfies Equation 4if and only if h(x ) satisfies Equation 5, from which our claim follows. In order to see this, consider that

(3) ⇐⇒ i w i x i ≥ -b ⇐⇒ wi≥0 w i x i + wi<0 w i x i ≥ -b (6) ⇐⇒ wi≥0 |w i |x i - wi<0 |w i |x i ≥ -b (7) ⇐⇒ wi<0 |w i |x i - wi≥0 |w i |x i ≤ b (8) (9)
On the other hand, we have

h(x ) satisfies (4) ⇐⇒ i |w i |h(x i ) ≤ J + b (10) ⇐⇒ wi<0 |w i |x i + wi≥0 |w i |(1 -x i ) ≤ wi≥0 |w i | + b (11) ⇐⇒ (7) (12)
Last, let us observe that we have k ≥ 0, as otherwise M would not have any positive instance. Therefore (s 1 , . . . , s m , k) is a valid input of #Knapsack, which concludes the proof.

We can now easily combine Lemma 29 together with a well-known dynamic programming algorithm solving #Knaspsack in pseudo-polynomial time.

Proof of Proposition 9. Let M = (w, b) be a perceptron, with the weights and bias being integers given in unary, and let x be a partial instance. First, we check that the maximal value of x, w is greater than -b, as otherwise M has no positive instance and we can simply return 0. We then use Lemma 29 to build in polynomial time an instance (s 1 , . . . , s m , k) ∈ N m+1 of #Knapsack such that COUNTPOSITIVECOMPLETIONS(M, x) = #Knapsack(s 1 , . . . , s m , k), and with s 1 , . . . , s m , k being written in unary (i.e., their value is polynomial in the input size). We can then compute #Knapsack(s 1 , . . . , s m , k) by dynamic programming as follows.

Appendix G. Proof of Proposition 10

We prove in this section Proposition 10, whose statement we recall here:

Proposition 10. The problem COUNTCOMPLETIONS restricted to perceptrons admits an FPRAS (and the use of randomness is not even needed in this case). This is not the case for MLPs, on the other hand, at least under standard complexity assumptions.

The fact that the query has no FPRAS for MLPs is because MLPs can efficiently simulate Boolean formulas (Lemma 13), and it is well known that the problem #SAT (of counting the number of satisfying assignments of a Boolean formula) has no FPRAS unless NP = RP. Hence we only need to prove our claim concerning perceptrons.

Proof of Proposition 10 for perceptrons. We can assume without loss of generality that the weights and bias are integers, as we can simply multiply every rational by the lowest common denominator (note that the bit lenght of the lowest common denominator is polynomial, and that it can be computed in polynomial time 5 ). We then transform the perceptron and partial instance to an input of #Knapsack with the right number of solutions using Lemma 29, by observing that the construction also takes polynomial time when the input weights are given in binary (and by considering that the s 1 , . . . , s m , k are also computed in binary). We can then apply an FPTAS to this #Knapsack instance, as shown in [START_REF] Gopalan | An FPTAS for #knapsack and related counting problems[END_REF][START_REF] Rizzi | Faster FPTASes for counting and random generation of Knapsack solutions[END_REF].

loose normalization theorem for the W(Maj)-hierarchy in Lemma 30; namely, we prove that the problem W CS(M 3t+2,3t+3 ) is W(Maj)[t]-hard. The main difficulty here is to reduce the depth d of the majority circuits, for any fixed d ∈ N, to a depth of at most 3t + 3. We then show in Lemma 31 that rMLPs can simulate majority circuits, without increasing the depth of the circuit. In Theorem 32 we use this construction to show an fpt-reduction from W CS(M 3t+2,3t+3 ) to (3t + 3)-MCR. This is enough to conclude hardness for W(Maj)[t].

Membership. We prove membership in Section I.2. Presented in Theorem 34, the proof consists of 4 steps. We first show in Lemma 35 how to transform a given rMLP M that into an MLP M that uses only step activation functions and that has the same number of layers. Then, as a second step, we build an MLP M , with 3t + 4 layers and again using only the step activation function, such that M has a satisfying assignment of weight k if and only if (M, x, k) is a positive instance of the t-MCR problem. The third step is to use a result of circuit complexity [START_REF] Goldmann | Simulating threshold circuits by majority circuits[END_REF] stating that circuits with weighted thresholds gates (which are equivalent to biased step functions), can be transformed into circuits using only majority gates, increasing the depth by no more than 1. This yields a circuit C M with 3t + 5 layers. However, the circuit C M , resulting from the construction of Goldmann et al. [START_REF] Goldmann | Simulating threshold circuits by majority circuits[END_REF], has both positive variables and negated variables as inputs, as their model needs to be able to represent non-monotone functions. For the fourth and last step, we build a circuit C * M based on C M , that fits the description of majority circuits as defined by [START_REF] Fellows | A purely democratic characterization of W[1[END_REF][START_REF] Fellows | Combinatorial circuits and the W-hierarchy[END_REF] (i.e., the one that we use). This circuit C * M has weft 3t + 7, and we prove that (C * M , k + 1) is a positive instance of the Weighted Circuit Satisfiability problem that characterizes the class W(Maj)[t] if and only if (M, x, k) is a positive instance of the (3t + 3)-MCR problem. The whole construction being an fpt-reduction, this will be enough to conclude membership in W(MAJ)[3t + 7].

Observe that (r)MLPs can be interpreted as well as rooted directed acyclic graphs, with weighted edges and where each node is associated a layer according to its (unweighted) distance from the root. Every node in a certain layer is connected to every node in layers -1 and + 1. We will sometimes use this equivalent interpretation, which turns out to be more handy for some of the proofs in this section.

I.1 Hardness

As explained in the proof sketch, we start by establishing a normalization theorem for the W(Maj)hierarchy. Lemma 30. The problem W CS(M 3t+2,3t+3 ) is W(Maj)[t]-hard.

Proof. A significant part of this proof is based on techniques due to Fellows et al. [START_REF] Fellows | A purely democratic characterization of W[1[END_REF] and to Buss et al. [START_REF] Buss | Simplifying the weft hierarchy[END_REF]. Let C be an arbitrary majority circuit of weft at most t and depth at most d ≥ t for some constant d, and let k be the parameter of the input instance. We define a small sub-circuit as a maximally connected sub-circuit comprising only small gates. Now, consider a path π from an arbitrary input node of C to its output gate. We claim that π intersects at most t + 1 small sub-circuits. Indeed, there must be at least one large gate separating every pair of small sub-circuits intersected by π, as otherwise the maximality assumption would be broken. But in π, as in any path, there are at most t large gates, because of the weft restriction, from where we conclude the claim. Now, for each small sub-circuit S, consider the set I S of its inputs (that may be either large gates or input nodes of C). As small gates have fan-in at most 3, and the depth of each small sub-circuit is at most d, we have that |I S | ≤ 3 d . We can thus enumerate in constant time all the satisfying assignments of S. We identify each assignment with the set of variables to which it assigns the value 1. We keep a set Γ with the satisfying assignments among I S that are minimal with respect to ⊆. Then, because of the fact that majority circuits are monotone, S can be written in monotone DNF as

S ≡ γ∈Γ x∈γ
x Note that the size of Γ is trivially bounded by the constant 2 3 d . We then build a circuit C , based on C, by following these steps:

1. Add 3 d (k + 1) extra input nodes. We distinguish the first, that we denote as u, from the 3 d (k + 1) -1 remaining, that we refer to by N .

2. Add a new output gate that is a binary majority between the old output gate and the node u.

3. Replace every small sub-circuit S by its equivalent monotone DNF formula, consisting of one large OR-gate and many large AND-gates.

4. Relabel every large OR-gate, of fan-in ≤ 2 3 d created in the previous step to be a majority gate with the same inputs, but to which one wires as well parallel edges from the input node u.

5.

Relabel every large AND-gate g, of fan-in ≤ 3 d , to be a majority gate. If g had edges from gates g 1 , . . . , g , then replace each edge coming from a g i by k + 1 parallel edges, and finally, wire (k + 1) -1 nodes in N to g.

An illustration of the transformation ins presented in Figure 3. We now check that C is a (majority) circuit in M 3t+2,3t+3 . To bound the depth and weft of C we need to account for all the sub-circuits of depth 2 that we introduced in steps 3-5 to replace each small sub-circuit of C. Note that two small sub-circuits that were parallel in C (meaning no input-output path could intersect both) have corresponding sub-circuits that are parallel in C . Consider now an arbitrary path π from a variable to the root of C, and let π be the corresponding path in C (that goes to the new root of C ). The path π contains one variable gate, at most t large gates, and intersects at most t + 1 small sub-circuits.

The corresponding path π in C still contains the variable gate, the (at most t) large gates that were in π, and for each of the at most t + 1 small-subcircuits that π intersected, π now contains exactly 2 large gate (and π also contains the new output gate of C ). Therefore, the length of π is at most 1 + t + 2(t + 1) + 1 -1 = 3t + 3, and it contains at most t + 2(t + 1) = 3t + 2 large gates. Since every path π in C from a variable to the root of C corresponds to such a path π in C, we obtain that the depth of C is at most 3t + 3 and its weft is at most 3t + 2. Hence, C is indeed a majority circuit in M 3t+2,3t+3 .

We now prove that ( ) there is a satisfying assignment of weight k + 1 for C if and only if there is a satisfying assignment of weight k for C, which would conclude our fpt-reduction. The proof for this claim is based on how the constructions in step 4 and 5 actually simulate large OR-gates and AND-gates, respectively. 7 We prove each direction in turn.

Forward direction. Let us assume that there exists a satisfying assignment of weight k + 1 for C . First, because input node u is directly connected to the output gate through a binary majority, it must be assigned to 1 in order to satisfy C . Let C be the sub-circuit of C formed by all the nodes that descend from the old output-gate in C . Then C needs to be satisfied in order to satisfy C . Since u is not present in C , an assignment of weight k + 1 that satisfies C is made by assigning 1 to u and to exactly k other input gates. In order to prove the claim, we will show that ( †) an assignment of weight k for the inputs of C satisfies C if and only if its restriction to the inputs of C satisfies C, assuming u is assigned to 1. As C only differs from C because of the replacement of each small sub-circuit S by its equivalent DNF, and the additional inputs in N , we only need to prove that steps 4 and 5 actually compute large OR and AND gates. Consider a gate g introduced in step 4, having edges from gates g 1 , . . . , g and edges from node u. Therefore, g has fan-in 2 , and as u always contributes with a value of to g, we have that g is satisfied exactly when at least one of the gates g 1 , . . . , g is satisfied. Consider now a gate g introduced in step 5. By construction, g has fan-in equal to 2 (k + 1) -1, from which we deduce that if all gates g 1 , . . . , g are satisfied, then g is indeed satisfied in C . On the other hand, if an assignment of weight k does not satisfy every gate g i , then g receives at most ( -1)(k + 1) units from the gates g i , and as the assignment has weight k, it receives at most k from the nodes in N . Thus, g receives at most (k + 1) -1 units, which is less than half of its fan-in, and thus, g is not satisfied. Thus, we have proved ( †). However, notice that the restriction of the assignment might have a weight of strictly less than k in C. But it is clear that, since the circuit is monotone, we can increase the weight by setting some variables of C to 1, until the weight becomes equal to k. This proves the forward direction.

Backward direction. Let us now assume an assignment of weight k for C. We then we extend such an assignment to C by assigning 0 to the inputs in N and 1 to u. Thanks to ( †), this is a (a) A majority circuit where small sub-circuits are represented with blue blobs, and black nodes correspond to large majority gates. The path determining the weft is colored red. The longest path, determining the depth of the circuit, is drawn with a dashed orange line.

(b) The majority circuit where small sub-circuits have been replaced by depth-2 majority circuits, corresponding to their equivalent DNF. The equivalent DNF depth-2 sub-circuits are represented by rectangles. Once again, the path determining the weft is colored red. The longest path, determining the depth of the circuit, is drawn with a dashed orange line.

Figure 3: Illustration of the Normalization Lemma [START_REF] Shi | On tractable representations of binary neural networks[END_REF]. In a nutshell, by paying a controlled increase in weft, the depth of the circuit can be substantially reduced.

satisfying assignment of weight k + 1 for C , which proves the backward direction of ( ) and thus concludes the proof of Lemma 30.

Then, we show that rMLPs can simulate majority circuits, without increasing the depth of the circuit. Lemma 31. Given a circuit C containing only majority gates, we can build in polynomial time an rMLP that is equivalent to C (as a Boolean function) and whose number of layers is equal to the depth of C.

Proof. First, note that we can assume that circuit C does not contain parallel edges by replacing each gate g having p edges to a gate g by p copies g 1 , . . . , g p with single edges to g . We then build a layerized circuit (remember the definition of a layerized circuit from Appendix A) C from C, by applying the same construction that we used in Lemma 13 to layerize a circuit, but using unary majority gates as identity gates instead. Note that the depth of C is the same as that of C.

Next, we show how each non-output majority gate can be simulated by using two relu-gates (again, remember the definition of a relu gate from Appendix A). First, note that ( †) for any non-negative integers x, n ∈ N, the function

f n (x) := relu x - n 2 -relu x - n 2 -1 is equal to Maj n (x) = 1 if x > n 2 0 otherwise .
We will use ( †) to transform the majority circuit C into a circuit C that has only relu gates for the non-output gates, and that is equivalent to C in a sense that we will explain next. For every non-output majority gate g of C , we create two relu gates g 1 , g 2 of C . The idea is that ( ) for any valuation of the input gates (we identify the input gates of C with those of C ), the Boolean value of any non-output gate g in C will be equal to the (not necessarily Boolean) value of gate g 1 (in C ) minus the value of the gate g 1 (in C ). We now explain what the biases of these new gates g 1 , g 2 for every majority gate g of C are. Letting n be the in-degree of a majority gate g in C , the bias of g 1 is -n 2 , and that of g 2 is -n 2 -1. Next, we explain what the weights of these new gates g 1 , g 2 are and how we connect them to the other relu gates. We do this by a bottom-up induction on C , that is, on the level of the gates of C (since C is layerized), and we will at the same time show that ( ) is satisfied. To connect the gates g 1 , g 2 to the gates of the preceding layer, we differentiate two cases:

Base case. The inputs of the gate g are variable gates; in other words, the level of g in C is 1 (remember that variable gates have level 0). We then set these variable gates to be an input of both g 2 and g 2 , and set all the weights to 1. It is clear that ( ) is satisfied for the gates g, g 1 , g 2 , thanks to ( †).

Inductive case. The inputs of the gate g are other majority gates; in other words, the level of g in C is > 1. Then, let 1 g, . . . , m g be the inputs8 (majority gates) of the gate g in C , and consider their associated pairs of relu gates ( 1 g 1 , 1 g 2 ), . . . , ( m g 1 , m g 2 ) in C . We then set all the gates 1 g 1 , . . . , m g 1 to be input gates of both gates g 1 and g 2 , with a weight of 1, and set all the gates 1 g 2 , . . . , m g 2 to be input gates of both gates g 1 and g 2 , with a weight of -1. By induction hypothesis, and using again ( †), it is clear that ( ) is satisfied.

Finally, based on the output gate r of C , we create a step gate r in C in the following way. Let 1 g, . . . , m g be the inputs of r, and ( 1 g 1 , 1 g 2 ), . . . , ( m g 1 , m g 2 ) their associated pairs in C . Then wire each gate i g 1 to r with weight 1, and also wire each gate i g 2 to r with weight -1. Let -n 2 -1 be the bias of r .

We have constructed a circuit C whose output gate is a step gate, and all other gates are relu gates. Consider now a valuation x of the input gates of C , which we identify as well as a valuation x of the input gates of C . We claim that C (x) = 1 if and only if C (x ) = 1. But this simply comes from the fact that for x, n ∈ N, we have x > n 2 ⇐⇒ x ≥ n 2 + 1, and from the fact that ( ) is satisfied for the input gates of r and of r .

The last thing that we have to do is to transform the circuit C , that uses only relu gates except for its output step gate, into a valid MLP. This can be done easily as in the proof of Lemma 13 by adding dummy connections with weights zero, because C is layerized. The resulting MLP M C is then equivalent to C, it is clearly an rMLP, its number of layers is exactly the depth of C, and, since we have constructed it in polynomial time, this concludes the proof.

Finally, we use this construction to show an fpt-reduction from W CS(M 3t+2,3t+3 ) to (3t + 3)-MCR. This is enough to conclude hardness for W(Maj)[t], thanks to Lemma 30.

Theorem 32. There is an fpt-reduction from the problem W CS(M 3t+2,3t+3 ) to the (3t + 3)-MCR problem.

Proof. We will in fact show an fpt-reduction from W CS(M t,t ) to t-MCR, which gives the claim when applied to 3t + 3, noting of course that W CS(M 3t+3,3t+3 ) is trivially at least as hard as W CS(M 3t+2,3t+3 ). Let (C, k) be an instance of W CS(M t,t ). We first build an MLP M C equivalent to C (as Boolean functions) by using Lemma 31. The MLP M C has t layers. Then, we build an MLP M C , that is based on M C , by following the steps described below:

1. Initialize M C to be an exact copy of M C .

2. Add an extra input, that we call v 1 , to M C . This means that if M C had dimension n, then M C has dimension n + 1.

3. Create nodes v 2 , . . . , v t , all having a bias of 0, and for each 1 ≤ i < t, connect node v i to node v i+1 with an edge of weight 1.

4. Let r be the root of M C , and let m be its fan-in. We connect node v t to r with an edge of weight m. Moreover, if the bias of r in M C was b, we set it to be b -m in M C .

5.

Observe that M C is layerized. To make it a valid MLP (where all the neurons of a layer are connected to all the neurons of the adjacent layers), we do as in the proof of Lemma 13 by adding dummy null weights.

It is clear that the construction of M C takes polynomial time, and that its number of layers is again t.

We now prove a claim describing the behavior of M C .

Claim 33. For any instance x of M C , expressed as the concatenation of a feature x 1 (for the extra input node v 1 ) and an instance x of M C , we have that x is a positive instance of M C if and only if x 1 = 1 and x is a positive instance of M C

Proof. Consider that, by construction, an instance x is positive for M C if and only if

n+1 i=1 h (t-1) i W (t) i = mh (t-1) 1 + n+1 i=2 h (t-1) i W (t) i ≥ -b + m But by construction h (t-1) 1 = x 1 , and m+1 i=2 h (t-1) i W (t) i = m i=1 h (t-1) i W (t)
i . This means that x is a positive instance of M C if and only if

mx 1 + m i=1 h (t-1) i W (t) i ≥ -b + m
Note that if x 1 = 1 and x is a positive instance of M C , this inequality is achieved, making x a positive instance. For the other direction, it is clear that it holds if x 1 = 1. We show that in fact x 1 = 0 is not possible. Indeed, by the construction of M C , we have that 0

≤ m i=1 h (t-1) i W (t) i
≤ m, and also that -b ≥ 1, which makes the inequality unfeasible. This concludes the proof of the claim. This claim has two important consequences:

1. As satisfying assignments of C correspond to positive instance of M C , we have that there is a satisfying assignment of weight exactly k for C if and only if there is a positive instance of weight exactly k + 1 for M C .

2. The instance 0 n+1 is negative for M C This consequences will allow us to finish the reduction. Consider the instance (M C , 0 n+1 , k + 1) of t-MCR. We claim that this is a positive instance for the problem if and only if (C, k) is a positive instance of W CS(M t ).

For the forward direction, consider (M C , 0 n+1 , k + 1) to be a positive instance of t-MCR. This means there is an instance x * that has the opposite classification as 0 n+1 under M C , and differs from it in at most k + 1 features. By the second consequence of the claim, x * must be a positive instance. Also, differing in at most k + 1 features from 0 n+1 means that x * has weight at most k + 1. But as majority gates are monotone connectives, majority circuits are monotones as well, so the existence of a positive instance x * of weight at most k + 1 implies the existence of a positive instance x * of weight exactly k + 1. Therefore, by the first consequence of the claim, there is a satisfying assignment of weight exactly k for C, which implies (C, k) is a positive instance of W CS(M t,t )

For the backward direction, consider (C, k) to be a positive instance of W CS(M t,t ). This means, by the first consequence of the claim, that there is a positive instance x * of weight exactly k + 1 for M C . But based on the second consequence of the claim, 0 n+1 is a negative instance for M C .

As x * differs from 0 n+1 in no more than k + 1 features, and they have opposite classifications, we have that (M C , 0 n+1 , k + 1) is a positive instance of t-MCR.

As the whole construction takes polynomial time, and the reduction changes the parameter in a computable way, from k to k + 1, it is an fpt-reduction. This concludes the proof.

I.2 Membership

In this section we prove membership in W(Maj)[3t + 7]. This will be enough to prove: Theorem 34. There is an fpt-reduction from t-MCR to W CS(M t+4,t+4 ), implying (3t + 3)-MCR belongs to W(Maj)[3t + 7].

As explained in the proof sketch, we first show how to transform a given rMLP M that into an MLP M that uses only step activation functions and that has the same number of layers. More formally, we prove that rMLPs using only step activation functions are powerful enough to simulate MLPs that use relu activation functions in the internal layers (and a step function for the output neuron). The construction is polynomial in the width (maximal number of neurons in a layer) of the given relu-rMLP, but exponential on its depth (number of layers). We show: Lemma 35. Given an rMLP M with relu activation functions, there is an equivalent MLP M that uses only step activation functions and has the same number of layers. Moreover, if the number of layers of M is bounded by a constant, then M can be computed in polynomial time.

Proof. Let (W (1) , . . . , W ( ) ), (b (1) , . . . , b ( ) ) and (f (1) , . . . , f ( ) ) be the sequences of weights, biases, and activation functions of the rMLP M. Note that f (i) for 1 ≤ i ≤ -1 is relu and that f ( ) is the step activation function. The first step of the proof is to transform every weight and bias into an integer. To this end, let L ∈ N, L > 0 be the lowest common denominator of all the weights and biases, and let M be the MLP that is exactly equal to M except that all the weights have been multiplied by L, and all the biases of layer i have been multiplied by L i . Observe that M has only integer weights and biases. When w (resp., b) is a weight (resp., bias) of M, we write w (resp., b ) the corresponding value in M . We claim that M and M are equivalent, in the sense that for every x ∈ {0, 1} n , it holds that M(x) = M (x). Indeed, for 0 ≤ i ≤ , let h (i) and h (i) be the vectors of values for the layers of M and M , respectively, as defined by Equation 1. We will show that ( ) for all 1 ≤ i ≤ -1 we have h (i) = L i × h (i) . The base case of i = 0 (i.e., the inputs) is trivially true. For the inductive case, assume that ( ) holds up to i and let us show that it holds for i + 1. We have:

h (i+1) = relu(h (i) W (i+1) + b (i+1) ) = relu(L × h (i) W (i+1) + L i+1 × b (i+1) ) by the definition of M = relu(L i+1 × h (i) W (i+1) + L i+1 × b (i+1) ) by inductive hypothesis = L i+1 × relu(h (i) W (i+1) + b (i+1) ) by the linearity of relu = L i+1 × h (i+1) ,
and ( ) is proven. Since the step function (used for the output neuron) satisfies step(cx) = c step(x) for c > 0, we indeed have that M(x) = M (x).

We now show how to build a model M that uses only step activation functions and that is equivalent to M . The first step is to prove an upper bound for the values in h . We start by bounding the values in h. Let D be width of M, that is, the maximal dimension of a layer of M, and let C be the maximal absolute value of a weight or bias in M; note that the value of C is asymptotically bounded by |M| O(1) because M is an rMLP. For every instance x, we have that

0 ≤ h (i) j = relu k h (i-1) k W (i) k,j + b (i) j ≤ DC max k h (i-1) k +C ≤ (D+1)C max(1, max k h (i-1) k )
Using this inequality, and the fact that max k h As all values (weights, biases and the h vectors) in M consist only of integers, and are all bounded by the integer S := ((D + 1)CL) , then each relu in M with bias b becomes equivalent to the following function f * :

(0) k ≤ 1, we obtain inductively that 0 ≤ h (i) j ≤ ((D + 1)C) i . By ( ), this implies that 0 ≤ h (i) j ≤ ((D + 1)CL) i . ≥ 1 ≥ 2 ≥ 3
f * (x + b) := [x + b ≥ 1] + [x + b ≥ 2] + . . . + [x + b ≥ S] (13)
Where [y ≥ j] := 1 if y ≥ j and 0 otherwise. Hence, in order to finish the proof, it is enough to show how activation functions of the form f * can be simulated with step activation functions. Namely, we show how to build M , that uses only step activation functions, from M , in such a way that both models are equivalent. In order to do so, we replace each f (i) , W (i) , b (i) for 1 ≤ i ≤ in the following way. If i = , then nothing needs to be done, as f ( ) is already assumed to be a step activation function. When 1 ≤ i < , we replace the weights, activations and biases in a way that is better described in terms of the underlying graph of the MLP. We split every internal node, with bias b into S copies, all of which will have the same incoming and outgoing edges as the original nodes, with the same weights. The j-th copy will have a bias equal to b -j. We illustrated this step in Figure 4. This construction is an exact simulation of the function f * defined in Equation 13.

The computationally expensive part of the algorithm is the replacement of each node in M by S nodes, which takes time at most S = ((D + 1)CL) ∈ O(|M| (CL) ) per node and thus at most O(|M| +1 (CL) ) in total. Since is a constant, and C is bounded by a polynomial on M, we only need to argue that L is bounded as well. Indeed, as M is an rMLP, each weight and bias can be assumed to be represented as a fraction whose denominator is a power of 10 of value polynomial in the graph size N of M. But the lowest common multiple of a set of powers of 10 is exactly the largest power of 10 in the set. Therefore L ≤ 10 p , where p ∈ O(log N ), and thus

L ∈ O(N c ) ⊆ O(|M| c )
for some constant c. We conclude from this that the construction takes polynomial time.

We are now ready to prove Theorem 34.

Proof of Theorem 34. Let (M, x, k) be an instance of t-MCR. During this reduction we assume that n > 2k, as otherwise the result can be achieved trivially; if n ≤ 2k then trying all instances that differ by at most k from x takes only O(k k ), and thus we can solve the entire problem in fpt-time and return a constant-size instance of W CS(M t+2 ), completing the reduction.

We start by applying Lemma 35 to build an equivalent MLP M that uses only step activation functions. As t is constant, this construction takes polynomial time, and its resulting MLP M has t layers as well. If x is a negative instance of M (and thus of M) we do nothing. This can trivially be checked in polynomial time, evaluating x in M . But if x happens to be a positive instance of M , then we change the definition of M negating its root perceptron 9 , and thus making x a negative instance. As a result, we can safely assume x to be a negative instance of M . We can also, in the same fashion that we assumed n > 2k, discard the case where the instance 0 n is a positive instance of M that differs by at most k from x, as in such scenario we could also solve the problem in fpt-time. The same can be done for 1 n .

We now build an MLP M , that still uses only step activation functions, such that M has a positive instance of weight exactly k if and only if (M, x, k) is a positive instance of t-MCR.

Let M be a copy of M to which we add one extra layer at the bottom. For each 1 ≤ i ≤ n, we connect the i-th input node of M to what was the i-th input node of M , but is now an internal node in M . If x i = 0 then the node in M corresponding to the i-th input node of M has a bias of 1, and the weight of the edge coming from the i-th input node of M is also 1. On the other hand, if x i = 1, then the node in M corresponding to the i-th input node of M has a bias of 0, and the weight of the connection added to it is -1. After doing this, we add k -1 more input nodes to M , a new node p in the t-th layer and a new root node r , that is placed in the layer t + 1. We connect r , the previous root node, to r of M with weight 1, and all input nodes to node p with weights of 1. In case p is more than one layer above the new input nodes, we connect them through paths of identity gates, as shown in Lemma 13. We set the bias of r to -2, and the bias of p to -k. All non-input nodes added in the construction use step activation functions.

We now prove a claim stating that M has exactly the intended behavior.

Claim 36. The MLP M has a positive instance of weight exactly k if and only if (M, x, k) is a positive instance of t-MCR.

Proof. For the forward direction, assume M has a positive instance x of weight exactly k. As the root r has a bias of -2, and two incoming edges with weight 1, and given that the output of any node is bounded by 1, as only step activation functions are used, we conclude that both p and r , the children of r , must have a value of 1 on x . The fact that r has a value of 1 on x implies that x s , the restriction of x that considers only nodes that descend from r , must be a positive instance for the submodel M s induced by considering only nodes that descend from r . But one can easily check that by construction, we have that M s (x s ) = M (x s ⊕ x), where ⊕ represents the bitwise-xor. Thus, x s ⊕ x is a positive instance for M, and consequently for M. As x s ⊕ x differs from x by exactly the weight of x s , as 0 is the neutral element of ⊕, and the weight of x s is by definition no more than the weight of x , which is in turn no more than k by hypothesis, we conclude that (M, x, k) is a positive instance of t-MCR.

For the backward direction, assume there is a positive instance x of M that differs from x in at most k positions. This means that x = x ⊕ x has weight at most k. By the same argument used in the forward direction, M s (x ) = M (x ⊕ x) = M (x ), as x ⊕ x ⊕ x = x ⊕ x ⊕ x = x , because ⊕ is both commutative and its own inverse. But the fact that x is a positive instance of M implies that it is also a positive instance for M . As we are assuming x | = 0 n , we have that k -|x | ≤ k -1. Thus, we can create an instance x for M that is equal to x on its corresponding features, and that sets k -|x | arbitrary extra input nodes to 1, among those created in the construction of M . As the instance x has weight exactly k, it satisfies the submodel descending from p, and as x its equal to x on the submodel descending from r , and x is a positive instance of M , we have that this submodel must be satisfied as well. Both submodels being satisfied, the whole model M is satisfied, hence we conclude the proof.

We thus have a model M with step activation functions, and t + 2 layers, such that if that model has a satisfying assignment of weight exactly k, then (M, x, k) is a positive instance of t-MCR.

Note that step activation functions with bias are equivalent to weighted threshold gates. We then use a result by Goldmann and Karpinski [START_REF] Goldmann | Simulating threshold circuits by majority circuits[END_REF]Corollary 12] to build a circuit C M that is equivalent (as Boolean functions) to M but uses only majority gates. The construction of Goldmann et al. can be carried in polynomial time, and guarantees that C M will have at most t + 3 layers.

There is however a caveat to surpass: although not explicitly stated in the work of Goldmann et al. [START_REF] Goldmann | Simulating threshold circuits by majority circuits[END_REF], their definition of majority circuit must assume that for representing a Boolean function from {0, 1} n to {0, 1}, the circuit is granted access to 2n input variables x 1 , . . . , x n , x 1 , . . . , x n , as it is usual in the field, and described for example in the work of Allender [START_REF] Allender | A note on the power of threshold circuits[END_REF]. We thus assume that the circuit C M resulting from the construction of Goldmann et al. has this structure, which does not match the required structure of the majority circuits defining the W(Maj)-hierarchy as defined by Fellows et al [START_REF] Fellows | A purely democratic characterization of W[1[END_REF][START_REF] Fellows | Combinatorial circuits and the W-hierarchy[END_REF]. In order to solve this, we adapt a technique from Fellows et al. [15, p. 17].

We build a circuit C * M that does fit the required structure. Let n be the dimension of M (which exceeds by k -1 that of M). We now describe the steps one needs to apply to C M in order to obtain C * M .

1. Add a new layer with n + 1 input nodes x 1 , . . . , x n+1 , below what previously was the layer of 2n input nodes x 1 , . . . , x n , x 1 , . . . , x n .

2. For every 1 ≤ i ≤ n, connect input node x i with its corresponding node x i in the second layer, making x i a unary majority, with the same outgoing edges it had as an input node. This enforces x i = x i .

3. Create a new root r for the circuit, and let r be a binary majority between the input node x n+1 and the previous root r.

4.

Replace each previous input node x i by a majority gates m i that has n + 1 -2k incoming edges from x n+1 , and one incoming edge from each x j with j ∈ {i, n + 1}. The outgoing edges are preserved.

It is clear that the circuit C * M is a valid majority circuit in the sense defining the W(Maj)-hierarchy. And it has 2 layers more than C M , yielding a total of t + 5 layers, where the last one has a small gate. However, it is not evident what this new circuit does. We now prove a tight relationship between the circuit C * M and M . Claim 37. The circuit C * M has a satisfying assignment of weight exactly k + 1 if and only if M has a positive instance of weight exactly k.

Proof. Forward Direction. Assume C * M has a satisfying assignment of weight k + 1. By step 3 of the construction, in order to satisfy C * M , the assignment must set x n+1 to 1. As we assume that node x n+1 is set to 1, the assignment must set to 1 exactly k input nodes among x 1 , . . . , x n and thus the sum of inputs set to 1 of each majority gate m i constructed in step 4, is exactly equal to n + 1 -2k + j ∈{i,n+1}

x j = n + 1 -2k + (k -x i ) = n + 1 -k -x i and its fan-in is exactly equal to 2n -2k. Therefore m i is activated when n + 1 -k -x i > n -k, which happens precisely when x i = 0. This way, each gate m i corresponds to the negation of x i . This way, the subcircuit induced by considering only the nodes that descend from r computes the same Boolean function that C M computes, under the natural mapping of their variables. Therefore, a satisfying assignment of weight k + 1 for C * M implies the existence of a satisfying assignment for C M that chooses exactly k positive variables, and thus a positive instance of weight k for M . Backward Direction. Assume M has a positive instance of weight exactly k. That implies that C M has a satisfying assignment σ that sets at most k positive variables to 1. Let us consider the assignment σ for C * M that sets to 1 the same variables that σ does, and additionally sets x n+1 to 1. The assignment σ has weight exactly k+1. By the same argument used in the forward direction, under assignment σ the gates m i behave like negations. Thus, the assignment σ induces an assignment over the second layer of C * M that corresponds precisely to a satisfying assignment of C M , and thus makes the value of r equal to 1. As both r and x n+1 have value 1 under assignment σ , it follows that the value of r , and thus of circuit C * M , are 1 under σ as well. This means that assignment σ , which by construction has weight k + 1, is a satisfying assignment for C * M , and thus concludes the proof.

  Example of an input DAG. Nodes 2 and 5, corresponding to the minimum dominating set of G are em-

1 .

 1 Resulting decision tree T . Edges to the left of a node are always labeled with 0, and edges to the right with The leaves are not depicted for clarity, but: if a node has no right child in the picture, then its right child is true, and if it has no left child then its left child is false. Note that in every diagonal there is an emphasized node, which is either 2 or 5, implying the partial instance (⊥, 1, ⊥, ⊥, 1, ⊥) is a sufficient reason for the instance x = (1, 1, 1, 1, 1, 1).

Figure 2 :

 2 Figure 2: Illustration of the reduction from DOM-DAG to k-SUFFICIENTREASON over decision trees, for an example graph of 6 nodes.

  For i ∈ {1, . . . , m} and C ∈ N, define the quantity DP[i][C] := |{S ⊆ {1, .., i}| j∈S s j ≤ C}|. We wish to compute DP[m][k]. We can do so by computing DP[i][C] for i ∈ {1, . . . , m} and C ∈ {0, . . . , k}, using the relation DP[i + 1][C] = DP[i][C] + DP[i][C -s i+1 ], and starting with the convention that DP[0][a] = 0 for all a < 0 and that DP[0][a] = 1 for all a ≥ 0. It is clear that the whole procedure can be done in polynomial time.

Figure 4 :

 4 Figure 4: Illustration of the conversion from a relu activation function to step activation functions, for S = 3. The weights are unchanged, and if the bias of the original neuron was b then the bias in the j-th copy of that neuron becomes b -j.

Table 1 :

 1 Summary of our complexity results.

	4 The complexity of explainability queries
		FBDDs	Perceptrons	MLPs
	MINIMUMCHANGEREQUIRED MINIMUMSUFFICIENTREASON NP-complete PTIME	PTIME PTIME	NP-complete Σ p 2 -complete
	CHECKSUFFICIENTREASON	PTIME	PTIME	coNP-complete
	COUNTCOMPLETIONS	PTIME	#P-complete	#P-complete

One has to be careful with this notation, however, as Σ p

and #P are complexity classes for problems of different sort: the former being for decision problems, and the latter for counting problems. Although this issue can be solved by considering the class PP, we skip these technical details as they are not fundamental for the paper and can be found in most complexity theory textbooks, such as that of Arora and Barak[START_REF] Arora | Computational complexity: a modern approach[END_REF].

Recall that such an input consists of natural numbers (given in binary) s1, . . . , sn, k ∈ N, and a solution to it is a set S ⊆ {1, . . . , n} with i∈S si ≤ k.

Note that, in order to keep our notation consistent, we use the symbol ⊆ where Umans uses ⊇.

We need to compute the least common multiple (lcm) of a set of integers a1, . . . , an. Indeed, it is easy to check that lcm(a1, . . . , an) = lcm(lcm(a1, . . . , an-1), an), which reduces inductively the problem to computing the lcm of two numbers in polynomial time. It is also easy to check that lcm(a1, a2) = a 1 a 2 gcd(a 1 ,a 2 ) , where gcd(a1, a2) is the greatest common divisor of a1 and a2. As multiplication can clearly be carried in polynomial time, and Euclid's algorithm allows computing the gcd function in polynomial time, we are done.

Useful normalization theorems for the W-hierarchy are proved in the work of Downey, Fellows and Regan[START_REF] Downey | Fixed-Parameter Tractability and Completeness I: Basic Results[END_REF][START_REF] Downey | Parameterized circuit complexity and the W hierarchy[END_REF], or Buss and Islam.[START_REF] Buss | Simplifying the weft hierarchy[END_REF]. Our normalization theorem for the W(Maj)-hierarchy is inspired from those.

Although this technique can already be found in the work of Fellows et al.[START_REF] Fellows | A purely democratic characterization of W[1[END_REF], we include it here for completeness.

Please excuse us for using left superscripts.

Let P = (w, b) be the perceptron at the root of M , which contains only integer values by construction. Then, the negation of P is simply P = (-w, -b + 1), as -wx ≥ -b + 1 precisely when wx ≤ b -1, which occurs over the integers exactly when it is not true that wx ≥ b.

Acknowledgments and Disclosure of Funding

Barceló and Pérez are funded by Fondecyt grant 1200967.

Appendix

The appendix contains the proofs for all the results presented in the main document. It is organized as follows:

Appendix A shows how MLPs can simulate Boolean circuits, which will be used in order to prove several propositions. Appendix B contains a proof of Proposition 5. Appendix C contains a proof of Proposition 6. Appendix D contains a proof of Proposition 7. Appendix E contains a proof of Proposition 8. Appendix F contains a proof of Proposition 9. Appendix G contains a proof of Proposition 10. Appendix H contains a more detailed description of the parameterized complexity framework. Appendix I contains a proof of Proposition 11. Appendix J contains a proof of Proposition 12.

Appendix A. Simulating Boolean formulas/circuits with MLPs

In this section we show that multilayer perceptrons can efficiently simulate arbitrary Boolean formulas. We will often use this result throughout the appendix to prove the hardness of our explainability queries over MLPs. In fact, and this will make the proof cleaner, we will show a slightly more general result: that MLPs can simulate arbitrary Boolean circuits. Formally, we show: Lemma 13. Given as input a Boolean circuit C, we can build in polynomial time an MLP M C that is equivalent to C as a Boolean function.

Proof. We will proceed in three steps. The first step is to build from C another equivalent circuit C that uses only what we call relu gates. A relu gate is a gate that, on input x = (x 1 , . . . , x m ) ∈ R m , outputs relu( w, x + b), for some rationals w 1 , . . . , w m , b. Observe that these gates do not necessarily output 0 or 1, and so the circuit C might not be Boolean. However, we will ensure in the construction that the output of every relu gate in C , when given Boolean inputs (i.e., x ∈ {0, 1} m ), is Boolean. This will imply that the circuit C is Boolean as well. To this end, it is enough to show how to simulate each original type of internal gate (NOT, OR, AND) by relu gates. We do so as follows:

• NOT-gate: simulated with a relu gate with only one weight of value -1 and a bias of 1.

• AND-gate of in-degree n: simulated with a relu gate with n weights, each of value 1, and a bias of value -(n -1). Indeed, it is clear that for x ∈ {0, 1} n , we have that

• OR-gate of in-degree n: we first rewrite the OR-gate with NOT-and AND-gates using De Morgan's laws, and then we use the last two items.

The second step is to build a circuit C , again using only relu gates, that is equivalent to C and that is what we call layerized. This means that there exists a leveling function l : C → N that Appendix B. Proof of Proposition 5

In this section we prove Proposition 5. We recall its statement for the reader's convenience:

Proposition 5. The MINIMUMCHANGEREQUIRED query is (1) in PTIME for FBDDs, (2) in PTIME for perceptrons, and (3) NP-complete for MLPs.

We prove each item separately.

Lemma 14. The MINIMUMCHANGEREQUIRED query can be solved in linear time for FBDDs.

Proof. Let (M, x, k) be an instance of MINIMUMCHANGEREQUIRED, where M is an FBDD. For every node u in M we define M u to be the FBDD obtained by restricting M to the nodes that are (forward-)reachable from u; in other words, M u is the sub-FBDD rooted at u. Then, we define mcr u (x) to be the minimum change required on x to obtain a classification under M u that differs from M(x). More formally, mcr u (x) = min{k | there exists an instance y such that d(x, y) = k and M u (y) = M(x)}, with the convention that min ∅ = ∞. Observe that, ( †) for an instance y minimizing k in this equality, since the FBDD M u does not depend on the features associated to any node u from the root of M to u excluded, we have that for any such node y u = x u holds (otherwise k would not be minimized). 3 Let r be the root of M. Then, by definition we have that (M, x, k) is a positive instance of MINIMUMCHANGEREQUIRED if and only mcr r (x) ≤ k. We now explain how we can compute all the values mcr u (x) for every node u of M in linear time. 3 We slightly abuse notation and write xu for the value of the feature of x that is indexed by the label of u.

Appendix D. Proof of Proposition 7

We now prove Proposition 7, whose statement we recall here: Proposition 7. The query CHECKSUFFICIENTREASON is (1) in PTIME for FBDDs, (2) in PTIME for perceptrons, and (3) co-NP-complete for MLPs.

We prove each claim separately. Lemma 23. The query CHECKSUFFICIENTREASON can be solved in linear time for FBDDs.

Proof. Let (M, x, y) be an instance of the problem, with M being an FBDD. We first check that x is a completion of y, which can clearly be done in linear time. We the define M as the resulting FBDD from the following procedure: (i) For every internal node in M with label i, delete its outgoing edge with label 0 if y i = 1 and its outgoing edge with label 1 if y i = 0. We note here that M is not a well defined FBDDs, since some internal nodes may have only one outgoing edge: more precisely, the value M(x ) ∈ {0, 1} is well defined for every instance x that is a completion of y, and is not defined for an instance x that is not a completion of y. To check whether y is a sufficient reason, we can then simply check that every leaf that is reachable from the root in M is labeled the same (either true or false). This can clearly be done in linear time by standard graph algorithms.

Lemma 24. The query CHECKSUFFICIENTREASON can be solved in linear time for perceptrons.

Proof. Let (M = (w, b), x, y) be an instance of the problem. We first check in linear time that x is a completion of y. We then get rid of the components that are defined by y, as follows. We define:

and let M be the perceptron (w , b ). Notice that the dimension of M is equal to the number of undefined components of y; we denote this number by m. It is then clear that y is a sufficient reason of x under M if and only if every instance of M is labeled the same. We can check this as follows.

Let J 1 be the minimum possible value of w , x (for x ∈ {0, 1} m ); J 1 can clearly be computed in linear time by setting x i = 0 if w i ≥ 0 and x i = 1 otherwise. Similarly we can compute the maximal possible value J 2 of w , x . Then, every instance of M is labeled the same if and only if it is not the case that J 1 < -b and J 2 ≥ -b , thus concluding the proof.

Lemma 25. The query CHECKSUFFICIENTREASON is co-NP-complete for MLPs.

Proof. We first show membership in co-NP. Let (M, x, y) be an instance of the problem. Then y is a sufficient reason of x under M if and only if all the completions of y are labeled the same as x. This can clearly be checked in co-NP.

In order to prove hardness we reduce from TAUT, the problem of checking whether an arbitrary boolean formula is a satisfied by all possible assignments of its variables. This problem is known to be complete for co-NP. Let F be an arbitrary boolean formula. We use Lemma 13 to build an equivalent MLP M in polynomial time (with the features of M corresponding to the variables of F).

Then F is a tautology if and only if all completions of the partial instance y = ⊥ n are positive instances of M. First, we construct an arbitrary instance x (for instance, the one with all the features being 0), and we reject if M(x) = 0. Then, we accept if y is a sufficient reason of x under M, and we reject otherwise. This concludes the reduction.

Appendix E. Proof of Proposition 8

We prove Proposition 8, whose statement we recall here: Proposition 8. The query COUNTCOMPLETIONS is (1) in PTIME for FBDDs, (2) #P-complete for perceptrons, and (3) #P-complete for MLPs.

As we said in the main text, the first claim follows almost directly from the definition of FBDDs; see [START_REF] Wegener | BDDs-design, analysis, complexity, and applications[END_REF] for instance. For the second claim, we will rely on the #P-hardness of the counting problem #Knapsack, as defined next: Definition 26. An input of the problem #Knapsack consists of natural numbers s 1 , . . . , s n , k ∈ N (given in binary). The output is the number of subsets S ⊆ {1, . . . , n} such that i∈S s i ≤ k.

The problem #Knapsack is well known to be #P-complete. Since we were not able to find a proper reference for this fact, we prove it here by using the #P-hardness of the problem #SubsetSum. An input of the problem #SubsetSum consists of natural numbers s 1 , . . . , s n , k ∈ N, and the output is the number of subsets S ⊆ {1, . . . , n} such that i∈S s i = k. The problem #SubsetSum is shown to be #P-complete in [4, Theorem 4]. From this we can deduce: Lemma 27 (Folklore). The problem #Knapsack is #P-complete.

Proof. Membership in #P is trivial. We prove hardness by polynomial-time reduction from #SubsetSum. Let (s 1 , . . . , s n , k) ∈ N n+1 be an input to #SubsetSum. It is clear that #SubsetSum(s 1 , . . . , s n , 0) = #Knapsack(s 1 , . . . , s n , 0), and that for k ≥ 1 we have #SubsetSum(s 1 , . . . , s n , k) = #Knapsack(s 1 , . . . , s n , k) -#Knapsack(s 1 , . . . , s n , k -1), thus establishing the reduction.

We can now show the second claim of Proposition 8. Lemma 28. The query COUNTCOMPLETIONS is #P-complete for perceptrons.

Proof. Membership in #P is trivial. We show hardness by polynomial-time reduction from #Knapsack. Let (s 1 , . . . , s n , k) be an input of #Knapsack. Let M be the perceptron with weights s 1 , . . . , s n and bias -(k + 1). Remember that we consider only perceptrons that use the step activation function, so that an instance x ∈ {0, 1} n is positive for M if and only if

Finally, the third claim of Proposition 8 simply comes from the fact that MLPs can simulate arbitrary Boolean formulas (Lemma 13), and the fact that counting the number of satisfying assignments of a Boolean formula (#SAT) is #P-complete.

Appendix F. Proof of Proposition 9

We now prove Proposition 9, that is: Proposition 9. The query COUNTCOMPLETIONS can be solved in pseudo-polynomial time for perceptrons (assuming the weights and biases to be integers given in unary).

The first part of the proof is to show how to transform in polynomial time and arbitrary instance of COUNTPOSITIVECOMPLETIONS for perceptrons (with the weights and bias being integers given in unary) into an instance of #Knapsack that has the same number of solutions. Lemma 29. Let M = (w, b) be a perceptron having at least one positive instance, with the weights and bias being integers given in unary, and let x be a partial instance. We can build in polynomial time an input (s 1 , . . . , s m , k) ∈ N m+1 of #Knapsack such that COUNTPOSITIVECOMPLETIONS(M, x) = #Knapsack(s 1 , . . . , s m , k), with s 1 , . . . , s m , k written in unary (i.e., their value is polynomial in the input size).

Proof. The first step is to get rid of the components that are defined by x, like we did in Lemma 24. Define

Appendix H. Background in parameterized complexity

In this section we present the notions from parameterized complexity that we will need to prove Proposition 11.

A parameterized problem is a language L ⊆ Σ * × N, where Σ is a finite alphabet. For each element (x, k) of a parameterized problem, the second component is called the parameter of the problem. A parameterized problem is said to be fixed parameter tractable (FPT) if the question of whether (x, k) belongs to L can be decided in time f (k) • |x| O (1) , where f is a computable function.

The FPT class, as well as the other classes we will introduce in this paper, are closed under a particular kind of reductions. A mapping φ : Σ * × N → Σ * × N between instances of a parameterized problem A to instances of a parameterized problem B is said to be an fpt-reduction if and only if

• There exists a computable function g such that k ≤ g(k), where k is the parameter of φ(x, k).

We define the complexity classes that are relevant for this article in terms of circuits. Recall that a circuit is a rooted directed acyclic graph where nodes of in-degree 0 are called input gates, and that the root of the circuit is called the output gate. Internal gates can be either OR, AND, or NOT gates.

All NOT nodes have in-degree 1. Nodes of types AND and OR can either have in-degree at most 2, in which case they are said to be small gates, or in-degree bigger than 2, in which case they are said to be large gates. The depth of a circuit is defined as the length (number of edges) of the longest path from any input node to the output node. The weft of a circuit is defined as the maximum amount of large gates in any path from an input node to the output node. An assignment of a circuit C is a function from the set of input gates in C to {0, 1}. The weight of an assignment is defined as the number of input gates that are assigned 1. Assignments of a circuit naturally induce a value for each gate of the circuit, computed according to the label of the gate. We say an assignment satisfies a circuit if the value of the output gate is 1 under that assignment.

The main classes we deal with are those composing the W-hierarchy and the W(Maj)hierarchy, a variant proposed by Fellows et al. [START_REF] Fellows | A purely democratic characterization of W[1[END_REF]. These complexity classes can be defined upon the WEIGHTED CIRCUIT SATISFIABILITY problem, parameterized by specific classes C of circuits, as defined below.

Appendix I. Proof of Proposition 11

In this section we prove Proposition 11, that is: Proposition 11. For every t ≥ 1 the MINIMUMCHANGEREQUIRED query over rMLPs with 3t + 3

We first explain what are rMLPs, then sketch the proof, and then proceed with the proof.

Given an MLP M, with the dimension of the layers being d 0 , . . . , d k , we define its graph size as N := k i=0 d i . We say an MLP with graph size N is restricted (abbreviated as rMLP) if each of its weights and biases can be represented as a decimal number with at most O(log(N )) digits. More precisely, represented as K i=-K a i 10 i , for integers 0 ≤ a i ≤ 9 and K ∈ O(log N ). Note that all numbers expressible in this way are also expressible by fractions, where the numerator is an arbitrary integer bounded by a polynomial in N , and the denominator is a power of 10 whose value is bounded as well by a polynomial in N .

We now explicit a family of parameterized problems indexed by an integer t ≥ 1. As the proof of Proposition 11 is quite involved, we first present a proof sketch that summarizes the process.

Problem

Hardness. We prove hardness in Section I.