Proof. Imagine that we start inflating a ball with the center at \(\bar x\). As the radius grows, some points of \(S^+\) and \(S^-\) fall inside the ball. We are waiting until either \((k+1)/2\) points of \(S^+\) or of \(S^-\) fall inside. If this first happens for \(S^+\), we set \(f^k_{S^+,S^-}(\bar x) = 1\), and we set \(f^k_{S^+,S^-}(\bar x) = 0\) if it first happens for \(S^-\). If this happens simultaneously, we set \(f^k_{S^+,S^-}(\bar x) = 1\), favoring positive classification. In other words, we classify \(\bar x\) positively if there is a ball that has at least \((k+1)/2\) points of \(S^+\) but its interior has at most \((k-1)/2\) points of \(S^-\). Likewise, \(\bar x\) is classified negatively if there is a ball with at least \((k+1)/2\) points of \(S^-\) but with at most \((k-1)/2\) points of \(S^+\) (in the interior and the boundary). ◻

Proof. If a set is a sufficient reason, then all its supersets are. Hence, to decide if \(X\subseteq \{1, \ldots, n\}\) is a minimal sufficient reason, it suffices to check if \(X\) is a sufficient reason, and then check, for each subset \(X \setminus \{i\}\) obtained by removing one element \(i \in X\), that \(X \setminus \{i \}\) is not a sufficient reason. ◻

Proof. We first consider the discrete case in item (1). We start by providing some intuition regarding our construction. Assume that \(k=1\). We reduce from the well-known NP-complete Vertex Cover problem: given an undirected graph \(G=(V,E)\), and an integer \(\ell\geqslant 0\), check whether there is a vertex cover \(C\) in \(G\) of size \(|C|\leqslant\ell\). Recall that a vertex cover is a subset of nodes \(C\subseteq V\) such that every edge in \(E\) has an endpoint in \(C\). Let \(G\) be a graph with vertex set \(V=\{1,\dots,n\}\) and edge set \(E=\{e_1,\dots,e_m\}\). Our encoding considers \(n\)-dimensional vectors (each component corresponds to a vertex). The vector \(\bar x\) is the zero vector, which will be classified positively. The negative example set \(S^-\) corresponds to the edges \(e_1,\dots,e_m\): each \(e_j\) is encoded in the natural way, a component is \(1\) iff it is an endpoint of \(e_j\). Hence, \(S^-\) is simply an encoding of the incidence matrix of \(G\). The positive example set \(S^+\) contains all the vectors resulting from vectors in \(S^-\) by flipping a \(1\) to a \(0\). Then each vector in \(S^-\) has two "guards" in \(S^+\) that are closer to \(\bar x\). Using these "guards", it follows that if \(C\) is a vertex cover, then \(C\) is a sufficient reason. On the other hand, if \(C\) is not a vertex cover, an edge/vector \(e_j\) not being covered directly provides a counterexample to \(C\) being a sufficient reason. We formalize this reduction below.

Given an instance of Vertex Cover, we construct an instance of \(1\)-Minimum Sufficient Reason\((\{0,1\},D_H)\) as follows. Assume that \(V=\{1,\dots,n\}\) and \(E=\{e_1,\dots,e_m\}\), for \(n,m\geqslant 1\). Suppose that \(n\) is the vector dimension, and take \(\bar x= (0,\dots,0) \in \{0,1\}^n\). For each \(j\in \{1,\dots,m\}\), we define the vector \(\bar{y}_{j}\in\{0,1\}^n\) such that \(\bar{y}_{j}[i] = 1\) if \(e_j\) is incident to the vertex \(i\), and \(\bar{y}_{j}[i] = 0\), otherwise. We define \(S^{-} = \{\bar{y}_{j}\mid j\in \{1,\dots,m\}\}\). For \(\bar{y}_{j}\), we denote by \(\bar{y}_{j}^1\) and \(\bar{y}_{j}^2\), the vectors obtained from \(\bar{y}_{j}\) by flipping the first and second component with value \(1\), respectively, to \(0\), and keeping the remaining vector components unchanged. We finally define \(S^+ = \bigcup_{j}\{\bar{y}_{j}^1, \bar{y}_{j}^2\}\). Note that \(f^{1}_{S^+,S^-}(\bar{x})=1\), as \(d_H(\bar{x},\bar{y})=1\) for every \(\bar{y}\in S^{+}\), while \(d_H(\bar{x},\bar{y})=2\) for every \(\bar{y}\in S^{-}\).

We claim that there is a vertex cover \(C\) with \(|C|\leqslant\ell\) if and only if there is a sufficient reason \(X\) for \(\bar{x}\) with respect to \(f^{1}_{S^+,S^-}\) such that \(|X|\leqslant\ell\). Suppose first there is such a vertex cover \(C\subseteq \{1,\dots,n\}\). We show that \(C\) is a sufficient reason. Let \(\bar{z}\in\{0,1\}^n\) be an arbitrary vector such that \(\bar{z}[i]=\bar{x}[i]=0\), for all \(i\in C\). We show that for every \(\bar{y}\in S^-\), there exists \(\bar{y}'\in S^+\), such that \(d_H(\bar z, \bar y) > d_H(\bar z, \bar{y}')\), and hence \(f^{1}_{S^+,S^-}(\bar{z})=1\) as required. Let \(\bar{y}_{j}\in S^-\). Since \(C\) is a vertex cover, one of the endpoints of \(e_j\) is in \(C\) and then there is \(i\in C\) such that \(\bar{y}_{j}[i]=1\). Pick one such \(i\), and define \(\bar{y}_j'\in S^+\) as the vector resulting from \(\bar{y}_{j}\) by flipping \(\bar{y}_{j}[i]\) to \(0\). Since \(\bar{y}_{j}\) and \(\bar{y}_{j}'\) only differ in one component \(i\in C\), we have \[d_H(\bar z,\bar{y}_{j}) > d_H(\bar z,\bar{y}_{j}') \;\;\iff\;\;|\bar{z}[i]-\bar{y}_{j}[i]| > \;|\bar{z}[i]-\bar{y}_{j}'[i]|\;\;\iff \;\;1>0\] and then the condition holds.

Assume now that \(X\subseteq\{1,\dots,n\}\) is a sufficient reason with \(|X|\leqslant\ell\). We show that \(X\) is a vertex cover of \(G\). By contradiction, suppose there is an edge \(e_j\in E\) whose endpoints are not in \(X\). Then the vector \(\bar{y}_{j}\) satisfies that \(\bar{y}_{j}[i]=\bar{x}[i]=0\) for all \(i\in X\). As \(\bar{y}_{j}\in S^-\), it follows that \(f^{1}_{S^+,S^-}(\bar{y}_{j})=0\), which is a contradiction.

The hardness of \(k\)-Minimum Sufficient Reason\((\{0,1\}, D_H)\), when \(k \geqslant 3\), is deferred to Section 8, where an even stronger result is proved (Theorem 8).

Now we turn to item (2). The construction for the continuous case with \(k\geqslant 1\) and \(\ell_p\)-norms is a direct adaptation of the previous idea. Now each of the vectors \(e_j\) in \(S^-\) must be represented by \((k+1)/2\) sufficiently close vectors: we increment the two components with value \(1\) by small quantities. In \(S^+\) we add suitable "guards" as before. Given an instance of Vertex Cover, we construct an instance of \(k\)-Minimum Sufficient Reason\((\mathbb{R},D_p)\) as follows. Assume that \(V=\{1,\dots,n\}\) and \(E=\{e_1,\dots,e_m\}\), for \(n,m\geqslant 1\). Suppose that \(n\) is the vector dimension, and take \(\bar x= (0,\dots,0) \in \mathbb{R}^n\). Choose \((k+1)/2\) numbers such that \(1/2 > \varepsilon_1 >\cdots>\varepsilon_{(k+1)/2} >0\). For each \(j\in \{1,\dots,m\}\), and \(h\in \{1,\dots,(k+1)/2\}\), we define the vector \(\bar{y}_{j,h}\in\mathbb{R}^n\) such that \(\bar{y}_{j,h}[i] = 1+\varepsilon_h\) if \(e_j\) is incident to the vertex \(i\), and \(\bar{y}_{j,h}[i] = 0\), otherwise. We also define: \[S^{-} \;= \;\{\bar{y}_{j,h}\mid j\in \{1,\dots,m\}, h\in \{1,\dots,(k+1)/2\}\}.\] For \(\bar{y}_{j,h}\), we define \(\bar{y}_{j,h}^1\) and \(\bar{y}_{j,h}^2\) as the vectors obtained from \(\bar{y}_{j,h}\) by changing the first and second components equal to \(1+\varepsilon_h\) to \(\varepsilon_h\), respectively, and keeping all other components unchanged. We finally define: \[S^+ \;=\;\bigcup_{j,h}\{\bar{y}_{j,h}^1, \bar{y}_{j,h}^2\}.\] Note that \(f^{k}_{S^+,S^-}(\bar{x})=1\), as for every \(\bar{y}^a_{j,(k+1)/2}\in S^{+}\) and \(\bar{y}_{j',h}\in S^{-}\): \[\lVert \bar{y}^a_{j,(k+1)/2} \rVert_p^p \;= \;\varepsilon_{(k+1)/2}^p + (1+\varepsilon_{(k+1)/2})^p \;< \;2(1+\varepsilon_{h})^p \;= \;\lVert \bar{y}_{j',h} \rVert_p^p.\]

Suppose first \(C\subseteq \{1,\dots,n\}\) is a vertex cover. We claim that \(C\) is a sufficient reason for \(\bar{x}\) with respect to \(f^{k}_{S^+,S^-}\). Let \(\bar{z}\in\mathbb{R}^n\) be an arbitrary vector such that \(\bar{z}[i]=\bar{x}[i]=0\), for all \(i\in C\). We show that there is an inyective function \(g:S^{-}\to S^{+}\) such that for every \(\bar{y}\in S^{-}\), we have \(\lVert \bar z - \bar y\rVert_p^p > \lVert \bar z - g(\bar y)\rVert_p^p\), and hence \(f^{k}_{S^+,S^-}(\bar{z})=1\) as required. Let \(\bar{y}_{j,h}\in S^-\). Since \(C\) is a vertex cover, one of the endpoints of \(e_j\) is in \(C\) and then there is \(i\in C\) such that \(\bar{y}_{j,h}[i]=1+\varepsilon_h\). Pick one such \(i\), and define \(g(\bar{y}_{j,h})\in S^+\) as the vector resulting from \(\bar{y}_{j,h}\) by changing \(\bar{y}_{j,h}[i]\) to \(\varepsilon_h\). Indeed, the function \(g\) is inyective:

• for \(\bar{y}_{j,h},\bar{y}_{j',h'}\in {S^-}\) with \(j\neq j'\), we have \(g(\bar{y}_{j,h})\neq g(\bar{y}_{j',h'})\) as their non-zero components differ; and

• for \(\bar{y}_{j,h},\bar{y}_{j,h'}\in {S^-}\) with \(h\neq h'\), we have \(g(\bar{y}_{j,h})\neq g(\bar{y}_{j,h'})\) as \(\varepsilon_{h}\neq \varepsilon_{h'}\).

Since \(\bar{y}_{j,h}\) and \(g(\bar{y}_{j,h})\) only differ in one component \(i\in C\), we have \[\lVert \bar z - \bar{y}_{j,h}\rVert_p^p \;> \;\lVert \bar z - g(\bar{y}_{j,h})\rVert_p^p \;\;\iff \;\;|\bar{z}[i]-(1+\varepsilon_h)|^p \;> \;|\bar{z}[i]-\varepsilon_h|^p \;\;\iff \;\;(1+\varepsilon_h)^p \;> \;\varepsilon_h^p,\] and then \(g\) satisfies the required conditions.

Assume now that \(X\subseteq\{1,\dots,n\}\) is a sufficient reason. We show that \(X\) is a vertex cover of \(G\). By contradiction, suppose there is an edge \(e_j\in E\) whose endpoints are not in \(X\). Then the vector \(\bar{y}_{j,1}\) satisfies that \(\bar{y}_{j,1}[i]=\bar{x}[i]=0\) for all \(i\in X\). We claim that \(f^{k}_{S^+,S^-}(\bar{y}_{j,1})=0\), which is a contradiction. This follows from the fact that \(\lVert \bar{y}_{j,1} - \bar{y}_{j,h} \rVert_p^p < \lVert \bar{y}_{j,1} - \bar{y}_{j',h'}^a \rVert_p^p\), for every \(h\in \{1,\dots,(k+1)/2\}\) and \(\bar{y}_{j',h'}^a\in S^+\). Indeed, since \(\bar{y}_{j',h'}^a\) has exactly one component with value \(1+\varepsilon_{h'}\), and \(\bar{y}_{j,1}\) has two components with value \(1+\varepsilon_1\), we have: \[\lVert \bar{y}_{j,1} - \bar{y}_{j',h'}^a \rVert_p^p \;\geqslant\;(1+\varepsilon_1 - \varepsilon_{h'})^p \;\geqslant\;1 \;\geqslant\;2\left(\frac{1}{2}\right)^p \;> \;2(\varepsilon_1 - \varepsilon_h)^p \;= \;\lVert \bar{y}_{j,1} - \bar{y}_{j,h} \rVert_p^p.\] This finishes the proof of the theorem. ◻

Proof. Assume first that \(f_{S^+,S^-}^k(\bar{x})=0\). Let \(X\subseteq \{1,\ldots,n\}\) and consider the affine subspace \[U(X,\bar{x}) := \{\bar{y} \in \mathbb{R}^n \mid \bar{x}[i] = \bar{y}[i], \text{for every i\in X}\}.\] Then \(X\) is not a sufficient reason for \(\bar{x}\) if and only if \(U(X,\bar{x})\) intersects the set \(\{\bar y\in\mathbb{R}^n \mid f_{S^+,S^-}(\bar{y})=1\}\). By Proposition 1, this set is a union of polynomially many polyhedra. It remains to check if our affine subspace intersects one of these polyhedra. The intersection of an affine subspace and a polyhedron is a polyhedron, and checking emptiness of a polyhedron is equivalent to linear programming which thus can be done in polynomial time [44].

In the case \(f_{S^+,S^-}^k(\bar{x})=1\), we have to check, whether our affine subspace intersects the set \(\{\bar y\in\mathbb{R}^n \mid f_{S^+,S^-}(\bar{y})=0\}\). This time, by Proposition 1, this set is a union of sets of solutions to systems of strict linear inequalities. The same argument as in the previous case reduces our problem to the emptiness problem for an intersection of an affine subspace with an open polyhedron. The latter is just the feasibility problem for systems of linear equalities and strict linear inequalities, which can be reduced to linear programming (with non-strict inequalities), solving our problem in polynomial time. Namely, let \(S\) be a system of linear equalities and strict linear inequalities. Consider a system \(\widehat{S}\) of non-strict linear inequalities over variables of \(S\) and a new variable \(\varepsilon\), obtained by turning every strict inequality \(l > 0\) of \(S\) into a non-strict inequality \(l \geqslant\varepsilon\). Feasibility of \(S\) is equivalent to existence of a feasible solution to \(\widehat{S}\) with positive \(\varepsilon\). To find out if the latter is true, it is enough to find the optimal solution to the problem of maximizing \(\varepsilon\) subject to \(\widehat{S}\). ◻

Proof. In the \(k\)-Counterfactual Explanation\((\mathbb{R},D_2)\) problem, given \(\bar{x} \in \mathbb{R}^n\) and \(\ell > 0\), the goal is to check if the ball \(B_\ell(\bar{x}) = \{\bar{y} \in \mathbb{R}^n \mid \|\bar{y} - \bar{x}\|_2 \leqslant\ell\}\) contains a vector with a different \(f^k_{S^+, S^-}\) value than \(\bar{x}\). If \(f^k_{S^+, S^-}(\bar{x}) = 0\), this reduces to checking whether \(B_\ell(\bar{x})\) intersects the set \(\{\bar{y} \in \mathbb{R}^n \mid f^k_{S^+, S^-}(\bar{y}) = 1\}\), which, by Proposition 1, is a union of polynomially many polyhedra. Thus, the problem reduces to determining whether \(B_\ell(\bar{x})\) intersects a given polyhedron \(P\). This can be solved via convex quadratic programming, which minimizes a positive definite quadratic form under a system of non-strict linear inequalities and is solvable in polynomial time due to Kozlov, Tarasov, and Khachiyan [45]. Specifically, we minimize \(q(\bar{y}) = \|\bar{x} - \bar{y}\|_2^2\) subject to constraints defining \(P\). The answer to \(k\)-Counterfactual Explanation\((\mathbb{R},D_2)\) is Yes if and only if the minimum value is at most \(\ell^2\), with the optimal solution providing the counterfactual explanation.

Similarly, when \(f^k_{S^+, S^-}(\bar{x}) = 1\), the problem reduces to checking whether the ball \(B_\ell(\bar{x})\) intersects a given open polyhedron, defined as the solution set to a system of strict linear inequalities. The argument from the previous paragraph requires modification because the algorithm in [45] assumes non-strict inequalities in the constraints. To address this, we first check whether \(P\) is empty, reducing the problem to linear programming as described in the proof of Proposition 3. If \(P\) is non-empty (since otherwise, there is nothing left to check), we construct a polyhedron \(\widehat{P}\) by converting all strict inequalities of \(P\) into non-strict ones. Note that \(P\) corresponds to the interior of \(\widehat{P}\). We claim that \(P\) intersects \(B_\ell(\bar x)\) if and only if \(\widehat{P}\) intersects the interior of \(B_\ell(\bar x)\). The latter can be reduced to a problem of minimizing a convex quadratic objective subject to (closed) polyhedron, which in turn can be solved in polynomial time with the techniques by Kozlov, Tarasov, and Khachiyan [45]. Indeed, consider the problem of minimizing \(q(\bar y) = \| \bar x - \bar y\|_2^2\) subject to \(\bar{y}\in \widehat{P}\) (which is a system of non-strict inequalities, as required in the algorithm). The answer is Yes if and only if the optimum is strictly less than \(\ell^2\).

We now establish the claim. First, assume that \(P\) intersects \(B_\ell(\bar{x})\). We show that \(P\) (and hence \(\widehat{P}\)) also intersects the interior of \(B_\ell(\bar{x})\). If \(P\) has a point on the boundary of the ball, it must also have a point inside, as \(P\) is open and any boundary point of the ball has interior points arbitrarily close to it. Now assume that \(\widehat{P}\) intersects the interior of \(B_\ell(\bar{x})\). Since \(P\) is the interior of \(\widehat{P}\), it is non-empty, and \(\widehat{P}\) is a full-dimensional polyhedron. By Proposition 2.1.8 in [46], every point in a full-dimensional polyhedron has interior points arbitrarily close to it. Thus, if \(\widehat{P}\) intersects the interior of the ball, \(P\), as the interior of \(\widehat{P}\), must also intersect the interior of the ball. ◻

Proof. This reduces to finding a point in the intersection of the ball \(B_\ell(\bar x)\) and an open polyhedron \(P\), if this intersection is non-empty. If it is non-empty, then \(\widehat{P}\) intersects the interior of \(B_\ell(\bar x)\). We can find a point \(\bar{y}\) in this intersection by minimizing the quadratic form \(q(\bar y) = \| \bar x - \bar y\|_{2}^{2}\) subject to \(\widehat{P}\). Suppose \(\bar y\) lies on the boundary of \(\widehat{P}\) (otherwise, we are done). That is, some inequalities, defining \(\widehat{P}\), turn into equalities on \(\bar y\). We now need to find a direction that points to the interior of \(\widehat{P}\) from this point. More precisely, our task is to find a vector \(\beta\) such that \(\langle \alpha, \beta\rangle > 0\) for every inequality \(\langle \alpha, \bar y\rangle \geqslant c\) which turns into equality on \(\bar y\). After such \(\beta\) is found, we just need to move from \(\bar y\) along \(\beta\) a little bit so that we still inside \(B_\ell(\bar x)\). Finding such \(\beta\) is reducible to finding a solution to a system of strict linear inequalities. In turn, the latter can be reduced in polynomial time to linear programming as explained in the proof of Proposition 3. ◻

Proof. Both results follow from the following lemma.

Indeed, \(k\)-RegClique is known to be both W\([1]\)-complete [47] when \(k\) is a parameter and NP-complete when \(k\) is a part of the input [48].

In the rest of the proof, we establish Lemma 1 (the fact that \(k\)-Counterfactual Explanation\((\mathbb{R},D_2)\) belongs to \({\rm NP}\) is immediate). For readability, throughout the proof we omit the bar notation and write vectors as \(x,x_i,y,0,\dots\). For our reduction, we first require the following lemma that provides an embedding of the nodes of our graph into an Euclidean space that respects the connections between the nodes. The resulting vectors are actually \(0,1\)-vectors so we formulate our lemma for the Hamming distance.

We now explain how we get from a \(d\)-regular graph \(G\) to an instance of the \((2k - 1)\)-Counterfactual Explanation\((\mathbb{R},D_2)\) problem. We first give an argument for the case when points in a dataset can have multiplicities. In the end we will explain how to get rid of this assumption.

Namely, we take \(0,1\)-vectors from Lemma 2, assigned to nodes of \(G\), all classified positively. We also add the all-0 vector to the dataset, classified negatively and with multiplicity \(k\). Due to conditions a), b), c), the all-0 point has the \(\ell_2\)-distance \(\alpha = \sqrt{2(n + d - 3)}\) from all the other points of the dataset. Any two positive points of the data set that correspond to two connected nodes of \(G\) also have the \(\ell_2\)-distance equal to \(\alpha\) between them. At the same time, points, corresponding to nodes, not connected by an edge, are all at distance \(\beta = \sqrt{2(n + d - 1)}\) from each other.

In our instance of the \((2k - 1)\)-Counterfactual Explanation\((\mathbb{R},D_2)\) problem, the question will be: is there a point at distance at most \(R\) (a number that will be defined later) from the all-0 vector \(x = (0, \ldots, 0)\) where \(f^{2k-1}_{S^+,S^-}\) takes the positive value? Observe that at \(x\), the \((2k-1)\)-NN takes the negative value – precisely at \(0\), there is a negative point with multiplicity \(k\), and positive points are at some positive distance from \(0\).

As the point \(0\) has multiplicity \(k\), in order for \(f^{2k-1}_{S^+,S^-}(y)\) to be positive for a point \(y\), there have to exist \(k\) positive points \(x_1, \ldots, x_k\) in the dataset such that \(y\) is closer or at the same distance to all these points as to \(0\). The minimal distance from \(0\) at which such \(y\) exists is formally defined in the following definition.

The answer to the counterfactual explanation problem is thus determined by whether there exist \(k\) positive points \(x_1, \ldots, x_k\) in the dataset with \(r(x_1, \ldots, x_k) \leqslant R\). We now relate this with the existence of the \(k\)-clique in the initial graph \(G\).

If a \(k\)-clique exists, the corresponding \(k\) points \(x_1, \ldots, x_k\) of the dataset will all be at distance \(\alpha\) from each other and from \(0\). As we will see later, \(r(x_1, \ldots, x_k) = \alpha\sqrt{\frac{k}{2(k + 1)}}\) in this case. Now, when no \(k\)-clique exists, we will argue that \(r(x_1, \ldots, x_k)\) is slightly bigger than \(\alpha\sqrt{\frac{k}{2(k + 1)}}\) for any \(k\) positive points \(x_1, \ldots, x_k\). This will happen because \(0\) is still at distance \(\alpha\) from \(x_1, \ldots, x_k\), and distances between \(x_1, \ldots, x_k\) are all at least \(\alpha\) with at least one distance being at least \(\beta > \alpha\) (for any \(k\) nodes there will be at least two nodes not connected by an edge, so their points will be at a larger distance). The following lemma justifies this reasoning.

The above reduction clearly takes polynomial time, but it remains to pick a rational number \(R\), satisfying: \[\label{eq95lambda} \lambda_1 = \alpha \sqrt{\frac{k}{2(k + 1)}} \leqslant R < \alpha \sqrt{\frac{k}{2(k + 1 - \delta)}} = \lambda_2, \qquad \delta = \frac{\beta^2 - \alpha^2}{k\alpha^2}.\tag{2}\] To avoid technicalities, we slightly modify the construction so that \(\lambda_1\) becomes a rational number and we can set \(R = \lambda_1\). Namely, just repeat every coordinate \(T\) times in all vectors of the dataset, for \(T\) to be defined later. All relative distances will be multiplied by \(\sqrt{T}\). After that, the value of \(\lambda_1\) will become: \[\lambda_1 =\sqrt{T\cdot 2(n + d - 3)} \sqrt{\frac{k}{2(k + 1)}} = \sqrt{(n + d - 3) T \frac{k}{k+1}}.\] Choosing \(T = (n + d - 3) k (k +1)\), we get \[\label{eq95rad} \lambda_1 = (n + d - 3) k\tag{3}\]

We now explain how to get rid of the multiplicities in our dataset. Instead of just point 0 with multiplicity \(k\), we will have 0 and \(k - 1\) other negative points \(y_1, \ldots, y_{k-1}\) with the following properties:

• every \(y_i\) is at the same distance \(\alpha\) from all positive points of the dataset.

• every \(y_i\) is \(\varepsilon\)-close to \(0\), for some \(\varepsilon > 0\) small enough that \(R + \varepsilon < \lambda_2\).

Assuming we have constructed such \(y_1, \ldots, y_{k - 1}\), we explain why the reduction still works after this modification. Indeed, in order to change the \((2k-1)\)-NN classification, we have to become closer (or at the same distance) to some \(k\) positive points as to some negative points. If a \(k\)-clique exists, we can take \(k\) corresponding positive points \(x_1, \ldots, x_k\), we can become as close to them as to 0 by moving at distance at most \(R = \alpha \sqrt{\frac{k}{2(k + 1)}}\) (as before, the points \(0, x_1, \ldots, x_k\) form a configuration as in the item a) of Lemma 3).

Now, assume that no \(k\)-clique exists. Pick arbitrary \(k\) positive points \(x_1, \ldots, x_k\). By the same argument as before, we require distance at least \(\lambda_2 > R\) to become at least as close to \(x_1, \ldots, x_k\) as to \(0\). However, we should also argue that we cannot become as close to \(x_1, \ldots, x_k\) as to \(y_i\) for some \(i\), by moving at distance at most \(R\). Indeed, \(x_1, \ldots, x_k\) correspond to a non-clique, and \(y_i\) has distance \(\alpha\) to all of them, so \(y_i, x_1, \ldots, x_k\) form the same configuration as described in item b) of Lemma 3 (after translation by \(-y_i\)). Hence, we have to move at least \(\lambda_2\) from \(y_i\), and hence, at least \(\lambda_2 - \varepsilon > R\) from \(0\) (because \(0\) and \(y_i\) are \(\varepsilon\)-close).

It remains to construct \(y_1, \ldots, y_{k - 1}\) with the required properties. Let us first calculate the value of \(\varepsilon\) that would work. Recall that \(\alpha = \sqrt{T\cdot 2(n + d - 3)}, \beta = \sqrt{T \cdot 2(n + d - 1)}\), so we get the following expression for \(\delta\) in 2 : \[\delta = \frac{2}{k \cdot (n + d - 3)}.\] Define \[\lambda_2' = \alpha \sqrt{\frac{k}{2(k + 1 - \delta')}}, \qquad \text{where } \delta' = \left(1 - \left(\frac{n^4 - 1}{n^4}\right)^2\right) (k + 1)\] Observe that \[0 < \delta' = \left(1 - \frac{n^4 - 1}{n^4}\right)\left(1 + \frac{n^4 - 1}{n^4}\right)(k + 1) \leqslant 2(k + 1)/n^4 < \frac{2}{k \cdot (n + d - 3)} = \delta,\] where the last inequality is due to the fact that \(k, d\leqslant n\), meaning that \(\lambda_1 < \lambda_2' < \lambda_2\). The value of \(\delta'\) is also chosen so that \(\lambda_2'\) is rational. Indeed, \(\lambda_1\) is rational, and the fraction \(\lambda_1/\lambda_2'\) is equal to: \[\sqrt{\frac{k + 1 - \delta'}{k + 1}} = \frac{n^4 - 1}{n^4}.\] Recalling 3 , we get that it suffices to set \(\varepsilon = \frac{1}{n^4} < \lambda_2' - \lambda_1 = \frac{k(n + d - 3)}{n^4 - 1}\).

We now construct \(y_1, \ldots, y_{k - 1}\). Recall also that all positive points were 0,1-vectors with the same number of 1s \(W\). Let \(m\) be the dimensionality of vectors in our dataset. It is equal to the dimensionality of vectors from Lemma 2 times \(T\). In the end of the argument, we will require a simple bound \(m \geqslant n\). Define \[\tau = \frac{1}{m^{100}}, \qquad S = 2W m^{100} - m.\] We add \(S(k - 1)\) new coordinates where all previous points of the dataset have \(0\)s. Each point \(y_1, \ldots, y_{k - 1}\) will have value \(\tau\) in all \(m\) old coordinates. Now, we split new coordinates into \(k - 1\) blocks of size \(S\). Each \(y_i\) for \(i = 1, \ldots, k -1\) will additionally have \(S\) coordinates of the \(i\)th block equal to \(\tau\), with the rest of the new coordinates equal to \(0\).

We need to show two things: (a) all the points \(y_1, \ldots, y_{k -1}\) are \(\varepsilon\)-close to \(0\); (b) all of them have the same distance to all positive points of the dataset as \(0\). We start with (a). Each \(y_1, \ldots, y_{k - 1}\) has \(m + S\) coordinates, equal to \(\tau\), so the square of its distance to \(0\) is: \[(m + S) \tau^2 = \frac{2Wm^{100}}{m^{200}} \leqslant\frac{2}{m^{99}} < \frac{1}{n^8} = \varepsilon^2,\] because \(m \geqslant n\).

We now show (b). As we have mentioned, every positive point \(x_j\) of the dataset has \(W\) 1s in the old \(m\) coordinates, and just 0s in the new coordinates. Hence, square of the distance from 0 to it is \(W\). The following calculation shows that the square of the distance from each \(y_i\) to \(x_j\) is also \(W\), thus finishing the proof of the theorem: \[\begin{align} \|y_i - x_j\|^2 &= (m - W) \tau^2 + W (1 - \tau)^2 + S \tau^2 = m \tau^2 + W - 2W\tau + S \tau^2 = W + (m + S) \tau^2 - 2W \tau \\ &= W + \frac{2W m^{100}}{m^{200}} - \frac{2W}{m^{100}} = W.\qedhere \end{align}\] ◻

Proof. The NPupper bound is straightforward: if a counter-factual explanation exists, it can be found as a solution to a linear program, constructable in polynomial time from the input. We now show the \({\rm NP}\) lower bound. Let us start with the case \(k = 1\) (we reduce from \(k = 1\) to the general case in the end of the proof). We reduce from a variation of the knapsack problem, where the goal is to determine whether at least half the total value of all items can fit into a given knapsack. Specifically, we are given \(n\) items, each with a weight \(w_i\) and value \(v_i\) (positive integers for \(i = 1, \ldots, n\)), and a positive integer \(W > 0\), representing the knapsack’s maximum weight capacity. The question is whether there exists a subset \(T \subseteq \{1, \ldots, n\}\) such that \(\sum_{i \in T} w_i \leqslant W\) and \(\sum_{i \in T} v_i \geqslant(v_1 + \ldots + v_n)/2\). The hardness of this problem arises from a reduction from the partition problem [49].

We reduce to the \(1\)-Counterfactual Explanation\((\mathbb{R}, D_1)\) problem with \(|S^+| = |S^-| = 1\) as follows. The dimension \(n\) corresponds to the number of items in the knapsack instance. We set \(\bar{x} = \bar{0} \in \mathbb{R}^n\) and the radius \(\ell = W\). The sets \(S^+ = \{\bar{g}\}\) and \(S^- = \{\bar{h}\}\) are defined as: \[\bar{g}_i = w_i, \qquad \bar{h}_i = w_i - \gamma \cdot v_i, \qquad i = 1, \ldots, n,\] where \(\gamma = 1/(2 \max_i v_i)\) ensures \(\gamma \cdot v_i \leqslant 1/2 < 1\) for all \(i = 1, \ldots, n\). Since \(w_i\) is a positive integer, we have \(0 < \bar{h}_i < \bar{g}_i\), so the interval \([\bar{h}_i, \bar{g}_i]\) lies to the right of 0 and has a length of \(\gamma \cdot v_i\). These properties imply \(\|\bar{h} - \bar{0}\|_1 < \|\bar{g} - \bar{0}\|_1\), resulting in \(f^1_{S^+, S^-}(\bar{0}) = 0\). We are asked if there exists \(\bar y\) with \(\|y\|_1\leqslant\ell = W\) such that \(f^1_{S^+,S^-}(\bar y) = 1\), or, equivalently, \(\| \bar h - \bar y\|_1 \geqslant\| \bar g - \bar y \|_1\). We show that the answer is Yes if and only if the original knapsack instance has a solution.

Assume first that the original knapsack instance has a solution. Define a vector \(\bar{y} \in \mathbb{R}^n\) by setting \(\bar{y}_i = 0\) for items not placed in the knapsack and \(\bar{y}_i = \bar{g}_i = w_i\) for items that are placed. Note that \(\|\bar{y}\|_1\) equals the total weight of the items in the knapsack, which does not exceed \(W = \ell\). We now need to show that \(\|\bar{h} - \bar{y}\|_1 \geqslant\|\bar{g} - \bar{y}\|_1\), or equivalently: \[\|\bar{h} - \bar{y}\|_1 - \|\bar{g} - \bar{y}\|_1 \;= \;\sum_{i=1}^n (|\bar{h}_i - \bar{y}_i| - |\bar{g}_i - \bar{y}_i|) \;\geqslant\; 0.\] It is more convenient to express this inequality in the equivalent form: \[\label{eq95length} \sum_{i=1}^n (|\bar{h}_i - \bar{y}_i| - |\bar{g}_i - \bar{y}_i| + \gamma v_i)/2 \;\geqslant\;\gamma (v_1 + \ldots + v_n)/2.\tag{4}\] The term \(|\bar{h}_i - \bar{y}_i| - |\bar{g}_i - \bar{y}_i|\) represents the distance from \(\bar{y}_i\) to the left endpoint of \([\bar{h}_i, \bar{g}_i]\) minus the distance from \(\bar{y}_i\) to the right endpoint of \([\bar{h}_i, \bar{g}_i]\). It is minus the length of the interval to the left of it, and plus the length of the interval to the right of it, and the length of the interval in our case is \(\gamma v_i\). Thus, if \(\bar{y}_i = 0\), the left-hand side of 4 contributes 0; if \(\bar{y}_i = \bar{g}_i\) (the right endpoint), it contributes \(\gamma v_i\). Therefore, the left-hand side of 4 is the sum of the values of the items in the knapsack, scaled by \(\gamma\). This proves 4 , as it follows directly from the fact that we began with a feasible solution to the original knapsack problem.

We now show the other direction. Assume that there exists \(\bar y\in\mathbb{R}^n\) such that \(\|\bar{y}\|_1 \leqslant\ell = W\) and \(\| \bar h - \bar y\|_1 \geqslant\| \bar g - \bar y \|_1\), with the latter being equivalent to 4 . Consider again the quantity \(|\bar h_i - \bar y_i| - |\bar g_i - \bar y_i|\) as a function of \(\bar y_i\). To the right of \(\bar g_i = w_i\) it is constant and is equal to the length of the interval. Hence, without loss of generality, \(\bar y_i \leqslant\bar g_i\) for every \(i = 1, \ldots, n\), as otherwise we can decrease \(\|\bar{y}\|_1\) without changing the left-hand side of 4 . Likewise, to the left of the interval, the quantity in question is also constant and is equal to the minus of the length of the interval, and the minimal absolute value there is \(0\). Hence, we may assume that if \(\bar y_i\) lies to the left of \([\bar h_i, \bar g_i]\), then \(\bar y_i = 0\) for every \(i = 1, \ldots, n\). Again, if not, \(\|\bar{y}\|_1\) can be decreased without changing the left-hand side of 4 .

We now establish that, without loss of generality, we may assume \(\bar{y}_i = 0\) or \(\bar{y}_i = \bar{g}_i\) for every \(i = 1, \ldots, n\). First, suppose there are two different components, \(\bar{y}_i\) and \(\bar{y}_j\), that lie within their respective intervals but are strictly smaller than their right endpoints. Start decreasing \(\bar{y}_i\) and increasing \(\bar{y}_j\) at the same rate. The terms involving \(\bar{y}_i\) and \(\bar{y}_j\) in 4 will begin to decrease and increase, respectively, at twice the same rate, leaving the left-hand side of 4 unchanged. Similarly, \(\|\bar{y}\|_1\) remains constant. This process continues until either \(\bar{y}_i\) reaches \(\bar{h}_i\) or \(\bar{y}_j\) reaches \(\bar{g}_j\). In the first case, we can further decrease \(\bar{y}_i\) to 0 without reducing the left-hand side of 4 . In the second case, \(\bar{y}_j\), which was strictly within its interval, becomes equal to its right endpoint. In both scenarios, the number of indices \(i\) for which \(\bar{y}_i \in (\bar{h}_i, \bar{g}_i)\) strictly decreases. We repeat this procedure until at most one index \(i\) satisfies \(\bar{y}_i \in (\bar{h}_i, \bar{g}_i)\).

Now, if at most one problematic \(i\) remains where \(\bar{y}_i \in (\bar{h}_i, \bar{g}_i)\), we simply increase \(\bar{y}_i\) to \(\bar{g}_i\). We claim that the solution remains feasible. Increasing \(\bar{y}_i\) raises the left-hand side of 4 , so the corresponding inequality is still satisfied. We now explain why \(\|\bar{y}\|_1 \leqslant W = \ell\) continues to hold. This follows from the fact that \(W\) is an integer and the length of any interval is less than 1. Before the increase, \(\|\bar{y}\|_1 = |\bar{y}_1| + \ldots + |\bar{y}_n|\) was at most \(W\). After the increase, the sum becomes integral because \(\bar{y}_i = 0\) or \(\bar{y}_i = \bar{g}_i = w_i\) for every \(i\). Consequently, the total sum cannot exceed \(W\), as the increase is too small to make the sum reach \(W + 1\).

Therefore, it holds that \(\bar y_i = 0\) or \(\bar y_i = \bar g_i = w_i\) for every \(i = 1,\ldots, n\). We place objects with \(\bar y_i = w_i\) into the knapsack. The condition \(\|\bar{y}\|_1 \leqslant\ell = W\) ensures that the sum of the weights of the objects placed in the knapsack does not exceed the capacity. Now, notice that the left-hand side of 4 becomes the sum of \(\gamma v_i\) for the objects placed in the knapsack, which guarantees that the total value of the objects placed is at least half of the total value of all objects.

We only have to show that it is enough to establish the theorem for \(k = 1\). This is because \(1\)-Counterfactual Explanation\((\mathbb{R},D_1)\) for \(|S^+| = |S^-| = 1\) reduces to \(k\)-Counterfactual Explanation\((\mathbb{R},D_1)\) for \(|S^+| = |S^-| = (k+1)/2\) for every odd integer \(k\geqslant 1\). Indeed, consider any input to \(1\)-Counterfactual Explanation\((\mathbb{R},D_1)\) with \(|S^+| = |S^-| = 1\). It consists of two singleton sets \(S^+ = \{\bar g\}\) and \(S^- = \{\bar h\}\) for \(\bar g, \bar h\in \mathbb{R}^n\), a vector \(\bar x \in\mathbb{R}^n\) and an integer \(\ell > 0\). The question is whether there exists \(\bar y\in\mathbb{R}^n\) such that \(\|\bar x - \bar y\|_1 \leqslant\ell\) and \(f^{1}_{S^+,S^-}(\bar x) \neq f^{1}_{S^+,S^-}(\bar y)\). In this special case, we have \(f^{1}_{S^+,S^-}(\bar z) = 1\) if \(\| \bar z - \bar g\|_1\leqslant\| \bar z - \bar h\|_1\) and \(f^{1}_{S^+,S^-}(\bar z) = 0\) otherwise. In other words, \(f^{1}_{S^+,S^-}(\bar z)\) can be defined as the sign of the difference \(\| \bar z - \bar h\|_1\;- \| \bar z - \bar g\|_1\) (where the sign of a non-negative number is 1 and the sign of a negative number is 0).

Without loss of generality, we may assume that \(\bar x = \bar{0}\). We now transform our input into an input for \(k\)-Counterfactual Explanation\((\mathbb{R},D_1)\) with \(|S^+| = |S^-| = (k + 1)/2\). We first add arbitrary \((k-1)/2\) points to \(S^+\) and \((k-1)/2\) points to \(S^-\), for example: \[\begin{align} \bar p_1 =(1, 0, \ldots,0),\,\, \ldots,\,\, \bar p_{\frac{k - 1}{2}} = \left(\frac{k - 1}{2}, 0, \ldots,0\right) &\text{ to } S^+,\\ \bar p_\frac{k + 1}{2} =\left(\frac{k + 1}{2}, 0, \ldots,0\right),\,\, \ldots,\,\, \bar p_{k-1} = \left(k-1, 0, \ldots,0\right) &\text{ to } S^-. \end{align}\] We then add one more coordinate to all vectors, where we put \(0\) for \(\bar x, \bar p_1, \ldots, \bar p_{k-1}\) and \(M = 10 (\ell + k)\) for \(\bar g, \bar h\). Let \(B_\ell\) be the ball of radius \(\ell\) around \(\bar x = \bar{0}\) (in the space with the new coordinate). Observe that any point among \(\bar p_1, \ldots, \bar p_{k-1}\) is much closer to any point in \(B_\ell\) than \(\bar g\) and \(\bar h\). Hence, for any potential counterfactual explanation \(\bar y \in B_\ell\), the closest \(k-1\) points in \(S^+\cup S^-\) will be \(\bar p_1, \ldots, \bar p_{k-1}\), among which half is from \(S^+\) and half is from \(S^-\). Hence, the value \(f^k_{S^+, S^-}(\bar y)\) for any \(\bar y\in B_\ell\) is determined by whether \(\bar g\) or \(\bar h\) (with an additional coordinate) is closer to \(\bar y\), with value 1 in case of the equality. This means that the answer to the problem is determined by whether the sign of \(\|\bar y - \bar h\|_1 - \|\bar y - \bar g\|_1\) is different for some \(\bar y \in B_\ell\) from the sign of \(\|\bar x - \bar h\|_1 - \|\bar x - \bar g\|_1\). Despite we have an additional coordinate, the answer to this is the same as in the initial \(1\)-Counterfactual Explanation problem. This is because \(\bar g\) and \(\bar h\) have the same value in this additional coordinate so that it cannot contribute to the difference, meaning that we can restrict ourselves to \(\bar y \in B_\ell\) that have \(0\) in this additional coordinate. ◻

Proof. For a given \(S^+, S^-\subseteq \mathbb{R}^n\), \(\bar x \in\mathbb{R}^n\) and \(X\subseteq \{1, \ldots, n\}\), our task is to decide, whether there is a vector, coinciding with \(\bar x\) on coordinates in \(X\) but differing in the value of \(f^1_{S^+, S^-}\). We will use the following notation: for a vector \(\bar v\in\mathbb{R}^n\), we write \(\bar v = (\bar v_1, \bar v_2)\), denoting by \(\bar v_1\) the projection of \(\bar v\) to coordinates from \(X\) and by \(\bar v_2\) the projection to the remaining coordinates.

In this notation, our task is to see, if there is \(\bar y_2 \in \mathbb{R}^{[n]\setminus X}\) with the property that \(f^1_{S^+, S^-}((\bar x_1, \bar y_2)) \neq f^1_{S^+, S^-}((\bar x_1, \bar x_2))\). First, assume that \(f^1_{S^+, S^-}((\bar x_1, \bar x_2)) = 0\). By Proposition 1 for \(k = 1\), we are asked if there exists \(\bar y_2 \in \mathbb{R}^{[n]\setminus X}\) and \(\bar a\in S^+\) such that: \[\label{eq95ac} \|(\bar x_1, \bar y_2) - (\bar a_1, \bar a_2)\|_1 \leqslant\|(\bar x_1, \bar y_2) - (\bar c_1, \bar c_2)\|_1 \text{ for every } \bar c\in S^-.\tag{5}\] Using linearity of the \(\ell_1\)-norm under concatenation of vectors, we rewrite 5 as follows: \[\label{eq95ac2}\|\bar x_1 - \bar a_1\|_1 - \|\bar x_1 - \bar c_1\|_1 \leqslant\|\bar y_2 - \bar c_2\|_1 - \|\bar y_2 - \bar a_2\|_1 \text{ for every } \bar c\in S^-.\tag{6}\] The left-hand side of 6 does not depend on \(\bar y_2\). The right-hand side of 6 , for every \(\bar c_2\), attains its maximum at \(\bar y_2 = \bar a_2\), by the triangle inequality. This gives the following algorithm for our problem: for every \(\bar a\in S^+\), check if \(\bar y_2 = \bar a_2\) satisfies all inequalities in 5 . If for some \(\bar a\in S^+\) it does, the set \(X\) is not a sufficient reason, otherwise \(X\) is a sufficient reason.

The argument for the case \(f^1_{S^+, S^-}((\bar x_1, \bar x_2)) = 0\) is exactly the same, with the roles of \(S^+\) and \(S^-\) swapped and with non-strict inequalities replaced by strict ones. ◻

Proof. Clearly, the \(k\)-Check Sufficient Reason\((\mathbb{R},D_1)\) is in \({\rm coNP}\). Indeed, if a given set of coordinates is not a sufficient reason, then a counter-example can be found as a solution to a linear program, constructible from the input in polynomial time.

We now show the coNP-hardness of the \(k\)-Check Sufficient Reason\((\mathbb{R},D_1)\) problem. We reduce from the complement to the partition problem, where we are given \(n\) positive integers \(v_1, \ldots, v_n\), and the question is whether there exists \(T\subseteq \{1, \ldots, n\}\) such that \(\sum_{i \in T} v_i = \sum_{i \notin T} v_i\). NP-completeness of the partition problem (as well as \({\rm coNP}\)-completeness of its complement) is standard [49].

Let us first assume for simplicity that the same point can appear in the data set multiple times (we will explain later how to get rid of this simplification). Given \(n\) positive integers \(v_1, \ldots, v_n\) (an input to the partition problem), consider an \(n\)-dimensional data set \(S\), consisting of the points \[\begin{align} \bar{\alpha} &= (0, 0, \ldots, 0) \qquad \text{classified 1, multiplicity 1,}\\ \bar{\beta} &= (2v_1, 2v_2, \ldots, 2 v_n) \qquad \text{classified 1, multiplicity (k - 1)/2,}\\ \bar{\gamma} &= (v_1, v_2, \ldots, v_n) \qquad \text{classified 0, multiplicity (k + 1)/2.} \end{align}\] The size of the dataset is \(k+1\), and we have a point \(\bar{\gamma}\) with multiplicity \((k+1)/2\), classified as \(0\). Hence, we have \(f_{S^+, S^-}^k(\bar{x}) = 0\) if and only if \(\bar{\gamma}\) is not the farthest point to \(\bar{x}\) in the dataset, i.e., if \(\|\bar{\gamma}- \bar{x}\|_1 < \|\bar{\alpha}- \bar{x}\|_1\) or \(\|\bar{\gamma} - \bar{x}\|_1 < \|\bar{\beta} - \bar{x}\|_1\) (here we require strict inequalities because of our optimistic view on \(k\)-NN classification). Observe that \(f_{S^+, S^-}^k(\bar{\alpha}) = 0\) because \(\|\bar{\gamma}\|_1 < \|\bar{\beta}\|_1\). We claim that there exists \(\bar{y}\in\mathbb{R}^n\) such that \(f_{S^+, S^-}^k(\bar y) = 1\) if and only if the initial partition problem has a solution. In other words, we claim that the empty set of coordinates is not a sufficient reason for \(\bar x = \bar 0\) if and only if the initial partition problem has a solution.

The condition \(f_{S^+, S^-}^k(\bar y) = 1\) can be rewritten as \[\begin{cases} \|\bar \alpha- \bar y\|_1 \leqslant\|\bar \gamma - \bar y\|_1 \\ \|\bar \beta- \bar y\|_1 \leqslant\|\bar \gamma - \bar y\|_1 \end{cases},\] or, equivalently, \[\begin{cases} \sum\limits_{i = 1}^n (|\bar y_i - 0| - |\bar y_i - v_i|) \leqslant 0 \\ \sum\limits_{i = 1}^n (|\bar y_i - 2v_i| - |\bar y_i - v_i|) \leqslant 0. \end{cases}\] We claim that we can restrict our search to \(\bar y\in\mathbb{R}^n\) where \(\bar y_i \in\{0, 2v_i\}\) for every \(i = 1, \ldots, n\). Indeed, consider the two expressions that appear in our conditions as functions of \(\bar y_i\): \[A_1(\bar y_i) = |\bar y_i - 0| - |\bar y_i - v_i|, \qquad A_2(\bar y_i) = |\bar y_i - 2v_i| - |\bar y_i - v_i|.\] If \(\bar y_i\) is to the left of \(v_i\), then we can decrease \(A_1\) without changing \(A_2\) by moving \(\bar y_i\) to \(0\). In turn, if \(\bar y_i\) is to the right of \(v_i\), we can decrease \(A_2\) without changing \(A_1\) by moving \(\bar y_i\) to \(2v_i\).

Now, take any “restricted” \(\bar y\). Let \(T\) denote the set of \(i \in\{1, \ldots, n\}\) such that \(\bar y_i = 2v_i\) (for \(i\notin T\), we have \(\bar y_i = 0\)). Then our conditions can be rewritten as: \[\begin{cases} \sum\limits_{i \in T}^n v_i + \sum\limits_{i \notin T}^n (-v_i)\leqslant 0 \\ \sum\limits_{i \in T}^n(-v_i) + \sum\limits_{i \notin T}^n v_i \leqslant 0. \end{cases}\] These conditions are equivalent to \(\sum_{i \in T}^n v_i = \sum_{i \notin T}^n v_i\), as required in the partition problem.

We now explain how to get rid of points with multiplicities. There are \(k +1\) points in our dataset (taking into account multiplicities). We add \(k + 1\) auxiliary coordinates. For \(i = 1, \ldots, k + 1\), for the \(i\)th point of the dataset, we put 1 to the \(i\)-th auxiliary coordinate and 0 to all the other auxiliary coordinates. For example, for \(k = 3\), we obtain the following dataset: \[\begin{align} &(1, 0, 0, 0, \bar{\alpha}) \qquad \text{classified 1},\\ &(0, 1, 0, 0, \bar{\beta}) \qquad \text{classified 1},\\ &(0, 0, 1, 0, \bar \gamma) \qquad \text{classified 0},\\ &(0,0 , 0, 1, \bar \gamma) \qquad \text{classified 0}. \end{align}\] We consider \(\bar x = (0, \ldots, 0)\) as the input and ask, whether the set of auxiliary coordinates is a sufficient reason for \(\bar x\). The same argument as before shows that this is the case if and only if the initial instance of the partition problem has a solution. Indeed, we are not allowed to change 0s in the \(k+ 1\) auxiliary coordinates of \(\bar x\). Hence, these coordinates contribute 1 to distances from \(\bar y\) to all the points. This does not change the differences of distances on which our argument is based on.

Finally, we explain why this reduction implies that \(k\)-Minimal Sufficient Reason\((\mathbb{R},D_1)\) is \({\rm NP}\)-hard (under Turing reductions) as well. The crucial thing is that the set of \(X\) for which we ask, whether \(X\) is a sufficient reason, has constant-size, namely, \(k+1\). It remains to note that \(X\) is a sufficient reason if and only if it has a subset which is a minimal sufficient reason. Hence, if we could solve \(k\)-Minimal Sufficient Reason\((\mathbb{R},D_1)\) in polynomial-time, we could solve the partition problem in polynomial-time by running the algorithm for the minimal sufficient reason problem on all subsets of \(X\). ◻

Proof. Fix \(p \geqslant 0\). We reduce from the following modified version of the Vertex Cover problem: Given an undirected graph \(G = (V,E)\) and an integer \(\ell\), is there a set \(V' \subseteq V\) with \(|V'| \leqslant\ell\) such that at least \(|E|-p\) edges have an endpoint in \(V'\)? Notice that for \(p = 0\) this is exactly the Vertex Cover problem. The fact that this problem is NP-complete for \(p > 0\) is obtained by an easy reduction from Vertex Cover (simply extend the input graph with \(p\) additional isolated edges).

We define a Boolean matrix \(A\) as the transpose of the incidence matrix of \(G\), i.e., \(A[i,j] = 1\) if and only if edge \(e_i\) is incident to vertex \(v_j\). We then define our matrix \(B\) by extending \(A\) with a column of all 1s on the right. We consider the instance \((B,\ell+1)\) for the problem \(p\)-BMCF.

Suppose first that \(T \subseteq \{1,\dots,|V|+1\}\) is a solution for the instance \((B,\ell+1)\) of \(p\)-BMCF. Notice, by construction, that \(|T| > 0\) (as we can assume without loss of generality that \(G\) contains at least \(p+1\) edges, and thus \(B\) contains at least \(p+1\) rows). Then there exists a solution \(T' \subseteq \{1,\dots,|V|+1\}\) for \((B,\ell+1)\) such that \(|T| = |T'|\) and \(T'\) contains index \(|V|+1\). Indeed, if \(T\) does not contain index \(|V|+1\) then we can obtain such a solution \(T'\) by simply removing any index from \(T\) and adding index \(|V|+1\). Then \(|T'| \leqslant\ell+1\) and \(|T''| \leqslant\ell\), for \(T'' = T' \setminus \{|V|+1\}\). We claim that \(U = \{v_i \mid i \in T''\}\) satisfies that at least \(|E|-p\) edges of \(G\) have an endpoint in \(U\). In fact, take an arbitrary edge \(e \in E\) such that row \(e\) has weight at most \(|T'|-1\) after flipping the columns in \(T'\). We know that there exist at least \(|E| - p\) such edges. We claim that, for each such an edge \(e\), it is the case that \(U \cap e \neq \emptyset\). Assume, on the contrary. Then the weight of row \(e\) after flipping the columns in \(T'\) is \[2 \, - \, |U \cap e| + (|T'|-1) - |U \cap e| \;= \;|T'|+1.\] This is a contradiction.

Suppose, in turn, that \(G\) has a vertex set \(U \subseteq V\) with \(|U| \leqslant\ell\) such that at least \(|E|-p\) edges have an endpoint in \(U\). Let us define \(T = \{i \mid v_i \in U\}\) and \(T' = T \cup \{|V|+1\}\). Then \(|T'| = |U| + 1 \leqslant\ell + 1\). We claim that \(T'\) is a solution for the instance \((B,\ell+1)\) of \(p\)-BMCF. Take an arbitrary edge \(e \in E\) that is covered by \(U\). In a similar fashion as above, the weight of row \(e\) after flipping the columns in \(T'\) is \[2 \, - \, |U \cap e| + (|T'|-1) - |U \cap e| \;= \; |T'|+1 - 2|U \cap e|.\] But \(|U \cap e| > 0\) since \(U\) covers \(e\), which implies that the weight of row \(e\) after flipping the columns in \(T'\) is at most \(|T'|-1\). ◻

Proof of Theorem 6. Fix an odd integer \(k = 2p + 1\), for \(p \geqslant 0\). The proof is by reduction from \(p\)-BMCF. Suppose that the input to \(p\)-BMCF is given by a Boolean matrix \(B\) of dimension \(m \times n\) and an integer \(\ell \leqslant n\). From the proof of Proposition 5, we can assume that \(B\) contains no repeated rows, each row of \(B\) contains at least two 0s, and \(m \geqslant p+1\). From \(B\), we define the input \((S^+,S^-,\bar x,\ell)\) for \(k\)-Counterfactual Explanation as follows:

• Each row \(b\) of \(B\) defines a tuple in \(S^+\) of dimension \(n+p+1\). This tuple is obtained by extending \(b\) with \(p+1\) 0s on the right.

• We define \(S^-\) to contain all tuples of the form \(\{0\}^{n+j} \times \{1\} \times \{0\}^{p-j}\), for \(1 \leqslant j \leqslant p+1\). Observe that there are \(p+1\) such tuples.

• Finally, \(\bar x = \{1\}^{n+p+1}\).

Notice that the \(p+1\) closest points to \(\bar x\) in the set \(S^+ \cup S^-\) belong to \(S^+\), as every row of \(B\) contains at least two 0s. Therefore, \(f^k_{S^+,S^-}(\bar x) = 1\).

Assume first that the input \((B,\ell)\) to \(p\)-BMCF has a solution \(T \subseteq \{1,\dots,n\}\). Then \(|T| \leqslant\ell\). Let \(\bar y \in \{0,1\}^{n+p}\) be the point that is obtained from \(\bar x\) by flipping from 1 to 0 precisely the elements indexed in \(T\). Then the Hamming distance between \(\bar x\) and \(\bar y\) is \(|T| \leqslant\ell\), and the Hamming distance between \(\bar y\) and any point in \(S^-\) is \(n-|T| + p\). Let \(B_T\) be the matrix that is obtained from \(B\) after flipping the columns in \(T\). We know that at least \(m-p\) of the rows in \(B_T\) have weight at most \(|T|-1\). Take any such row \(b\), and let \(\phi(b)\) be its corresponding element in \(S^+\). It follows that the distance between \(\bar y\) and \(\phi(b)\) is at least \(n - (|T|-1) + p + 1 = n - |T| -p + 2 > n-|T| + p\). Therefore, \(S^+\) contains at most \(p\) elements which are at distance at most \(n-|T| + p\) from \(\bar y\). Hence, \(f^k_{S^+,S^-}(\bar y) = 0\).

Assume, in turn, that the input \((S^+,S^-,\bar x,\ell)\) to the problem Counterfactual Explanation has a solution given by \(\bar y\), where \(\bar y\) is at distance \(d \leqslant\ell\) from \(\bar x\). Let \(T \subseteq \{1,n+p+1\}\) be the set of indices for which \(\bar y\) takes value 0 and \(T' = T \cap \{1,\dots,n\}\). We claim that \(T'\) is a solution for \((B,\ell)\) with respect to \(p\)-BCMF. Notice first that the Hamming distance between \(\bar y\) and an arbitrary element in \(S^-\) is at most \[(n-|Y'|) + (p+1) - (d - |Y'|) + 1 \;= \;n + p - d + 2.\] This means that there cannot be \(p+1\) elements in \(S^+\) whose Hamming distance from \(\bar y\) is at most \(n+p-d + 2\) (as, otherwise, \(f^k_{S^+,S^-}(\bar y) = 1\), which is a contradiction). Suppose, for the sake of contradiction, that after flipping the columns in \(T'\) and obtaining matrix \(B_{T'}\) there are at least \(p+1\) rows whose weight is at least \(|Y'|\). Take any such row \(b\). Then the distance between \(\bar y\) and the element in \(S^+\) that uniquely represents \(b\) is at most \[(n-|Y'|) + (p+1) - (d - |Y'|) \;= \;n + p - d + 1 \;< \;n + p - d + 2.\] This is our desired contradiction. ◻

Proof. We show that \(1\)-Check Sufficient Reason\((\{0,1\},D_H)\) can be solved in polynomial time. Let \(\bar{x}\in\{0,1\}^n\), \(S^+,S^-\subseteq \{0,1\}^n\), and \(X\subseteq\{1,\dots,n\}\). Suppose that \(X\) is not a sufficient reason. Assume without loss of generality that \(f^{1}_{S^+,S^-}(\bar x)=1\). Then there is a vector \(\bar{z}\in\{0,1\}^n\) with \(\bar{z}[i]=\bar{x}[i]\) for every \(i\in X\) such that \(f^{1}_{S^+,S^-}(\bar z)=0\). For each \(\bar{y}\in S^{-}\), let \(\bar{y}_X\) be the vector such that \(\bar{y}_X[i]= \bar{x}[i]\), for every \(i\in X\), and \(\bar{y}_X[i]= \bar{y}[i]\), for every \(i\not\in X\). We claim that without loss of generality, the vector \(\bar{z}\) can always be chosen to be a vector in \(\{\bar{y}_X\mid \bar{y}\in S^{-}\}\). Indeed, since \(f^{1}_{S^+,S^-}(\bar z)=0\), there is \(\bar{y}\in S^-\) such that \(d_H(\bar{z},\bar{y})<d_H(\bar{z},\bar{w})\), for every \(\bar{w}\in S^+\). By flipping the components of \(\bar{z}\) belonging to \(\{i\not\in X\mid \bar{z}[i]\neq \bar{y}[i]\}\) to obtain \(\bar{y}_X\), the distance \(d_H(\bar{z},\bar{y})\) decreases by an amount of \(r=|\{i\not\in X\mid \bar{z}[i]\neq \bar{y}[i]\}|\), while the distances \(d_H(\bar{z},\bar{w})\) can decrease by at most a quantity of \(r\). Hence the strict inequality still holds, in particular, we have that \(d_H(\bar{y}_X,\bar{y})<d_H(\bar{y}_X,\bar{w})\), for every \(\bar{w}\in S^+\).

The above discussion implies that in order to check whether \(X\) is a sufficient reason when \(f^{1}_{S^+,S^-}(\bar x)=1\) (the other case is analogous), it suffices to check that none of the vectors in \(\{\bar{y}_X\mid \bar{y}\in S^{-}\}\) satisfies \(f^{1}_{S^+,S^-}(\bar{y}_X)=0\). This can be easily checked in polynomial time. ◻

Proof. The \({\rm coNP}\) upper bound is direct: given \(S^+, S^-\), \(\bar{x}\in\{0,1\}^n\) and \(X\subseteq \{1,\dots, n\}\), for all \(\bar{y}\in\{0,1\}^n\) such that \(\bar{y}[i] = \bar{x}[i]\), for every \(i\in X\), we can verify in polynomial time whether \(f^{k}_{S^+,S^-}(\bar y) = f^{k}_{S^+,S^-}(\bar x)\).

We show that the complement of \(k\)-Check Sufficient Reason\((\{0,1\},D_H)\) is NP-hard for every fixed odd integer \(k \geqslant 3\). We reduce from the Vertex Cover problem: given an undirected graph \(G=(V,E)\) with \(n\) vertices, and an integer \(q\geqslant 0\), decide whether there is a subset of vertices \(C\subseteq V\) with size \(|C|\leqslant q\) such that \(C\) is a vertex cover, that is, every edge in \(E\) has an endpoint in \(C\). We can assume without loss of generality that \(q\geqslant n/2\). Indeed, if \(q<n/2\), we consider the instance \((G', q'=n-q)\), where \(G'\) results from \(G\) by adding \(n-2q\) fresh nodes, each of them connected by an edge to every original node in \(G\). Since any subset of vertices of size \(n\) or \(n-1\) is a vertex cover, we can also assume that \(q\leqslant n-2\).

Take a graph \(G=(V,E)\) with \(V=\{1,\dots,n\}\) and \(E=\{e_1,\dots,e_m\}\), for \(m\geqslant 1\). The vector dimension is \(n+(k+1)/2 + (2q-n)\) and then we write vectors in \(\{0,1\}^{n+(k+1)/2+(2q-n)}\) as concatenations \((\bar{x}, \bar{y}, \bar{z})\) of three vectors \(\bar{x}\in \{0,1\}^{n}\), \(\bar{y}\in \{0,1\}^{(k+1)/2}\) and \(\bar{z}\in \{0,1\}^{2q-n}\). We denote by \(\bar{0}_r\) and \(\bar{1}_r\) the vectors \((0,\dots,0)\in \{0,1\}^{r}\) and \((1,\dots,1)\in \{0,1\}^{r}\), respectively. For \(h\in\{1,\dots, (k+1)/2\}\) we define the canonical vector \(\bar{\alpha}_h\in\{0,1\}^{(k+1)/2}\) such that \(\bar{\alpha}_h[h']=1\) for \(h'=h\) and \(\bar{\alpha}_h[h']=0\), for \(h'\neq h\). For each \(j\in\{1,\dots,m\}\), we define the vector \(\bar{y}_j\in\{0,1\}^{n}\) such that \(\bar{y}_j[i]=1\) if the edge \(e_j\) is incident to the vertex \(i\), and \(\bar{y}_j[i]=0\) otherwise. The sets \(S^-,S^{+}\subseteq\{0,1\}^{n+(k+1)/2 + (2q-n)}\) are defined as follows: \[\begin{align} S^{-} & =\{(\bar{y}_j, \bar{\beta}, \bar{1}_{2q-n}) \mid j\in\{1,\dots,m\}, \bar{\beta}\in \{0,1\}^{(k+1)/2}\setminus \{\bar{0}_{(k+1)/2}\}\}.\\ S^{+} & = \{(\bar{0}_n, \bar{\alpha}_1, \bar{1}_{2q-n})\}\cup \{(\bar{1}_n, \bar{\alpha}_h, \bar{0}_{2q-n})\mid h\in\{2,\dots,(k+1)/2\}\}. \end{align}\] Note that \(|S^+| = (k+1)/2\). Finally, we set \(\bar{x}=(\bar{0}_n, \bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\). Note that \(f^{k}_{S^+,S^-}(\bar x)=0\) as \(d_H(\bar x, (\bar{1}_n, \bar{\alpha}_h, \bar{0}_{2q-n}))=n+1\) for every \(h\in \{2,\dots,(k+1)/2\}\), while \[d_{H}(\bar x, (\bar{y}_1, \bar{\alpha}_h, \bar{1}_{2q-n}))= 2 + 1 + 2q-n\leqslant 3 + 2(n-2) - n = n-1\] for every \(h\in\{1,\dots,(k+1)/2\}\).

We claim that there is a vertex cover \(C\subseteq\{1,\dots,n\}\) with \(|C|\leqslant q\) if and only if the empty set is not a sufficient reason for \(\bar{x}\) w.r.t \(f^{k}_{S^+,S^-}\). The latter condition is equivalent to the existence of a vector \(\bar{z}\in \{0,1\}^{n+(k+1)/2+(2q-n)}\) with \(f^{k}_{S^+,S^-}(\bar z)=1\). It suffices to show the following two properties:

1. If there is a vertex cover \(C\subseteq\{1,\dots,n\}\) of \(G\) with \(|C|=q\), then \(f^{k}_{S^+,S^-}(\bar z)=1\), for \(\bar{z}=(\bar{w}_C,\bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\), where \(\bar{w}_C[i]=0\) if \(i\in C\), and \(\bar{w}_C[i]=1\) if \(i\in \{1,\dots,n\}\setminus C\).

2. Suppose that \(f^{k}_{S^+,S^-}(\bar z)=1\) for \(\bar{z}=(\bar{w}, \bar{\gamma}, \bar{t})\) and let \(C=\{i\in\{1,\dots,n\}\mid \bar{w}[i]=0\}\). Then we have only two possibilities: either \(|C|\leqslant q\) and \(C\) is a vertex cover of \(G\); or \(|C|=q+1\) and every subset \(C'\subseteq C\) with \(|C'|=q\) is a vertex cover of \(G\).

These two properties imply the correctness of the reduction. If there is a vertex cover of size at most \(q\), without loss of generality, we can assume the size is \(q\) and then we can apply (1). For the backward direction, if \(f^{k}_{S^+,S^-}(\bar z)=1\) for some \(\bar{z}\), property (2) implies that, in any of the possible two cases, there is a vertex cover of size at most \(q\).

We start with property (1). Suppose \(C\) is a vertex cover with \(|C|=q\) and define \(\bar{w}_C\in\{0,1\}^n\) such that \(\bar{w}_C[i]=0\) if \(i\in C\) and \(\bar{w}_C[i]=1\), if \(i\in\{1,\dots,n\}\setminus C\). We claim that \(f^{k}_{S^+,S^-}(\bar z)=1\) for the vector \(\bar{z}=(\bar{w}_C, \bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\). For every \((\bar{y}_j, \bar{\beta}, \bar{1}_{2q-n})\in S^{-}\), we have \[d_H(\bar{z}, (\bar{y}_j, \bar{\beta}, \bar{1}_{2q-n})) \geqslant|V\setminus C| + 1 + 2q-n = n-q + 1 + 2q - n = q+1.\] Here we are using the fact that \(C\) covers the edge \(e_j\), that is, \(|C\cap e_j|\geqslant 1\), and then: \[d_H(\bar{w}_C, \bar{y}_j) = |C\cap e_j| + |V\setminus C| - (2-|C\cap e_j|) \geqslant 1 + |V\setminus C| - (2-1) = |V\setminus C|.\] On the other hand, we have: \[d_H(\bar{z}, (\bar{0}_n, \bar{\alpha}_1, \bar{1}_{2q-n})) = |V\setminus C| + 1 + 2q-n = q+1\] and \[d_H(\bar{z}, (\bar{1}_n, \bar{\alpha}_h, \bar{0}_{2q-n})) = |C| + 1 = q+1\] for every \(h\in\{2,\dots,(k+1)/2\}\).

We now turn to property (2). Suppose that \(f^{k}_{S^+,S^-}(\bar z)=1\), for some \(\bar{z}= (\bar{w}, \bar{\gamma}, \bar{t})\in \{0,1\}^{n+(k+1)/2 + (2q-n)}\) and define \(C = \{i\in \{1,\dots,n\}\mid \bar{w}[i] = 0\}\). We can always pick vectors \(\bar{\beta}_1,\dots, \bar{\beta}_{(k+1)/2}\) from \(\{0,1\}^{(k+1)/2}\setminus \{\bar{0}_{(k+1)/2}\}\) such that \(d_H(\bar{\gamma}, \bar{\beta}_h)\leqslant 1\), for every \(h\in\{1,\dots, (k+1)/2\}\).

By contradiction, suppose first that \(|C|\geqslant q+2\). Then: \[\begin{align} d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{y}_1, \bar{\beta}_h, \bar{1}_{2q-n})) & \leqslant d_H(\bar{w}, \bar{y}_1) + 1 + d_H(\bar{t}, \bar{1}_{2q-n})\\ & = |C\cap e_1| + |V\setminus C| - (2-|C\cap e_1|) + 1 + d_H(\bar{t}, \bar{1}_{2q-n}) \\ & \leqslant 2+ |V\setminus C| + 1 + d_H(\bar{t}, \bar{1}_{2q-n})\\ & \leqslant 2 + (n-q-2) + 1 + 2q - n\\ & = q+1 \end{align}\] for every \(h\in\{1,\dots, (k+1)/2\}\). On the other hand, we have \[d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{1}_n, \bar{\alpha}_h, \bar{0}_{2q-n})) \geqslant d_H(\bar{w}, \bar{1}_n) = |C|\geqslant q+2\] for every \(h\in\{2,\dots, (k+1)/2\}\). By Proposition 1, choosing \(A=\{(\bar{y}_1, \bar{\beta}_h, \bar{1}_{2q-n})\mid h\in \{1,\dots,(k+1)/2\}\}\subseteq S^-\) and \(B = \{(\bar{0}_n, \bar{\alpha}_1, \bar{1}_{2q-n})\}\subseteq S^+\), we have that \(f^{k}_{S^+,S^-}(\bar z)=0\); a contradiction.

Assume that \(|C|\leqslant q\) and, towards a contradiction, suppose that \(C\) is not a vertex cover. There must be an edge \(e_j\) such that \(|C\cap e_j| = 0\). We have that \[\begin{align} d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{y}_j, \bar{\beta}_h, \bar{1}_{2q-n})) & \leqslant d_H(\bar{w}, \bar{y}_j) + 1 + d_H(\bar{t}, \bar{1}_{2q-n})\\ & = |C\cap e_j| + |V\setminus C| - (2-|C\cap e_j|) + 1 + d_H(\bar{t}, \bar{1}_{2q-n}) \\ & = |V\setminus C| - 1 + d_H(\bar{t}, \bar{1}_{2q-n}) \end{align}\] for every \(h\in\{1,\dots, (k+1)/2\}\). On the other hand, we have \[d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{0}_n, \bar{\alpha}_1, \bar{1}_{2q-n})) \geqslant d_H(\bar{w}, \bar{0}_n) + d_H(\bar{t}, \bar{1}_{2q-n}) = |V\setminus C| + d_H(\bar{t}, \bar{1}_{2q-n}).\]

We conclude that \(f^{k}_{S^+,S^-}(\bar z)=0\), using Proposition 1 with \(A=\{(\bar{y}_j, \bar{\beta}_h, \bar{1}_{2q-n})\mid h\in \{1,\dots,(k+1)/2\}\}\subseteq S^-\) and \(B = S^+\setminus \{(\bar{0}_n, \bar{\alpha}_1, \bar{1}_{2q-n})\}\). This is a contradiction.

Finally, suppose that \(|C|=q+1\). We claim that there is no edge with an endpoint in \(V\setminus C\). By contradiction, suppose there is such an edge, say \(e_j\). In particular, \(|C\cap e_j|\leqslant 1\). We obtain: \[\begin{align} d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{y}_j, \bar{\beta}_h, \bar{1}_{2q-n})) & \leqslant d_H(\bar{w}, \bar{y}_j) + 1 + d_H(\bar{t}, \bar{1}_{2q-n})\\ & = |C\cap e_j| + |V\setminus C| - (2-|C\cap e_j|) + 1 + d_H(\bar{t}, \bar{1}_{2q-n}) \\ & \leqslant 1 + |V\setminus C| - (2-1) + 1 + d_H(\bar{t}, \bar{1}_{2q-n})\\ & \leqslant(n-q-1) + 1 + 2q - n\\ & = q \end{align}\] for every \(h\in\{1,\dots, (k+1)/2\}\). On the other hand, we have \[d_H((\bar{w}, \bar{\gamma}, \bar{t}), (\bar{1}_n, \bar{\alpha}_h, \bar{0}_{2q-n})) \geqslant d_H(\bar{w}, \bar{1}_n) = |C| = q+1\] for every \(h\in\{2,\dots, (k+1)/2\}\). Again, by Proposition 1, we conclude that \(f^{k}_{S^+,S^-}(\bar z)=0\); a contradiction. It follows that every edge of \(G\) is contained in \(C\), and, since \(|C|=q+1\), any subset \(C'\subseteq C\) with \(|C'|=q\) is a vertex cover of \(G\). ◻

Proof. Membership is direct: the NP-part of the computation guesses \(S\), checks its size, and calls a coNP-oracle to check that every superset \(S' \supseteq S\) of size at most \(q\) fails to cover \(G\).

For hardness, we reduce from Independent Set Interdiction. Let \((G, p, q)\) be an input instance, where \(G=(V,E)\). We then simply output \((G, p, |V|-q)\), which obviously can be done in polynomial time.

To prove correctness we will need some notation. Given a graph \(G\), we denote by \(\alpha(G)\) the maximum size of an independent set of \(G\), and by \(\tau(G)\) the minimum size of a vertex cover of \(G\). Moreover, given a graph \(G\) and a subset \(S \subseteq V\), we denote by \(\tau(G, S)\) the minimum size of a vertex cover that contains \(S\). Our reduction relies on two simple observations:

1. \(\alpha(G) + \tau(G) = |V|\).

2. \(\tau(G, S) = |S| + \tau(G[V \setminus S])\).

While observation ([obs:1]) corresponds to the well-known fact that the complement of a vertex cover is an independent set (and vice versa), observation ([obs:2]) requires a brief justification. Indeed, note that if \(S' \supseteq S\) is any vertex cover of size \(\tau(G, S)\), then \(S' \setminus S\) must be a vertex cover of \(G[V \setminus S]\), and thus \(\tau(G, S) = |S'| = |S| + |S' \setminus S| \geqslant|S| + \tau(G[V \setminus S])\). Conversely, let \(S''\) be a vertex cover of minimum size for \(G[V \setminus S]\). Then, \(S'' \cup S\) is a vertex cover for \(G\) which contains \(S\), and thus \(|S'' \cup S| = \tau(G[V \setminus S]) + |S| \geqslant\tau(G, S)\).

Now, observe that \(\exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr}\)-Vertex-Cover can be rephrased as whether there exists \(S \subseteq V\) with \(|S| \leqslant p\) such that \(\tau(G, S) > q\). Similarly, the Independent Set Interdiction problem can be rephrased as whether there exists \(S \subseteq V\) with \(|S| \leqslant p\) such that \(\alpha(G[V \setminus S]) < q\), since the independent sets of \(G\) that do not intersect \(S\) are exactly the independent sets of \(G[V \setminus S]\). Using these rephrasings to prove the correctness of our reduction, it suffices to show that for any \(S \subseteq V\) with \(|S| \leqslant p\), we have \[\tau(G, S) > q \iff \alpha(G[V\setminus S]) < |V| - q.\] This now follows easily from our observations: \[\begin{align} \tau(G, S) > q & \iff |S| + \tau(G[V \setminus S]) > q )}\\ & \iff |S| + (|V\setminus S| - \alpha(G[V \setminus S])) > q )}\\ & \iff |S| + (|V| - |S| - \alpha(G[V \setminus S]) > q\\ & \iff \alpha(G[V \setminus S]) < |V| - q. \end{align}\]

It remains to show that hardness holds when \(n/2\leqslant q\leqslant n-2\). Let \((G,p,q)\) be an instance of \(\exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr}\)-Vertex-Cover, where \(G=(V,E)\) and \(n:=|V|\). If \(q<n/2\), we transform the instance to \((G',p,q')\), where \(q'=n-q\) and \(G'=(V',E')\) results from \(G\) by adding \(n-2q\) fresh nodes, each of them connected by an edge to every node in \(G\). Note that \(q'=n'/2\) where \(n'=|V'|\). We claim that \((G,p,q)\in \exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr} \text{-{\sc Vertex-Cover}}\) if and only if \((G',p,q') \in \exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr} \text{-{\sc Vertex-Cover}}\). Suppose first that there is \(S\subseteq V\) with \(|S|\leqslant p\) such that every superset \(S'\) of \(S\) with \(|S'|\leqslant q\) is not a vertex cover of \(G\). It holds that there is no superset \(S''\) of \(S\) with \(|S''|\leqslant q'\) that is a vertex cover of \(G'\). By contradiction, if there is such a \(S''\), as \(q'< n\) and there is an edge from every fresh node to every node in \(V\), then \(S''\) must contain all the \(n-2q\) fresh nodes. It follows that \(|S''\cap V|\leqslant q\). This is a contradiction as \(S''\cap V\) is a vertex cover of \(G\) and a superset of \(S\). On the other hand, assume there is \(S\subseteq V'\) with \(|S|\leqslant p\) such that every superset \(S'\) of \(S\) with \(|S'|\leqslant q'\) is not a vertex cover of \(G'\). We claim that there is no superset \(S''\subseteq V\) of \(S\cap V\) with \(|S''|\leqslant q\) that is a vertex cover of \(G\). If there is such a \(S''\) then by adding the fresh nodes, we obtain a superset of \(S\) that is a vertex cover of \(G'\) of size at most \(q+n-2q=q'\); a contradiction. Finally, note that any instance \((G,p,q)\) with \(q\geqslant n-1\) is a negative instance of \(\exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr} \text{-{\sc Vertex-Cover}}\), as any set of at least \(n-1\) nodes is a vertex cover of \(G\). ◻

Proof of Theorem 8. The upper bound is direct: we guess a subset \(X\) of components with \(|X|\leqslant\ell\) and then verify with an \({\rm coNP}\)-oracle that is a sufficient reason (recall Theorem 7).

We reduce from \(\exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr} \text{-{\sc Vertex-Cover}}\) under the restriction \(n/2\leqslant q\leqslant n-2\). Given an instance \((G,p,q)\) of \(\exists\ooalign{\forall\cr\hidewidth\!/\hidewidth\cr} \text{-{\sc Vertex-Cover}}\), where \(G=(V,E)\) and \(V=\{1,\dots, n\}\), we define the instance \((S^+, S^-, \bar{x}, p)\) of \(k\)-Minimum Sufficient Reason\((\{0,1\},D_H)\), where \((S^+,S^-,\bar{x})\) is define from \((G,q)\) exactly as in the proof of Theorem 7. Recall that the dimension of vectors in \((S^+,S^-,\bar{x})\) is \(n+(k+1)/2 + (2q-n)\), and hence we write vectors as the concatenation of three vectors of dimensions \(n\), \((k+1)/2\) and \((2q-n)\), respectively. The vector \(\bar{x}\) is the all zero vector \(\bar{x}=(\bar{0}_n,\bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\) (here \(\bar{0}_r\) is the all zero vector of dimension \(r\)). It holds that \(f^{k}_{S^+,S^-}(\bar x)=0\). The condition \(n/2\leqslant q\leqslant n-2\) is needed to apply this reduction. The following properties of \((S^+,S^-,\bar{x})\) are shown in the proof of Theorem 7:

1. If there is a vertex cover \(C\subseteq\{1,\dots,n\}\) of \(G\) with \(|C|=q\), then \(f^{k}_{S^+,S^-}(\bar z)=1\), for \(\bar{z}=(\bar{w}_C,\bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\), where \(\bar{w}_C[i]=0\) if \(i\in C\), and \(\bar{w}_C[i]=1\) if \(i\in \{1,\dots,n\}\setminus C\).

2. Suppose that \(f^{k}_{S^+,S^-}(\bar z)=1\) for \(\bar{z}=(\bar{w}, \bar{\gamma}, \bar{t})\) and let \(C=\{i\in\{1,\dots,n\}\mid \bar{w}[i]=0\}\). Then, either \(|C|\leqslant q\) and \(C\) is a vertex cover of \(G\); or \(|C|=q+1\) and every subset \(C'\subseteq C\) with \(|C'|=q\) is a vertex cover of \(G\).

To see that the reduction is correct, assume first that there exists \(S\subseteq\{1,\dots,n\}\) with \(|S|\leqslant p\) such that no superset \(S'\) of \(S\) with \(|S'|\leqslant q\) is a vertex cover of \(G\). We claim that \(S\) is a sufficient reason for \(\bar x\) w.r.t. \(f^k_{S^+,S^-}\). By contradiction, suppose there is a vector \(\bar{z}=(\bar{w}, \bar{\gamma}, \bar{t})\) with \(\bar{z}[i]=\bar{x}[i]=0\), for every \(i\in S\), such that \(f^k_{S^+,S^-}(\bar{z})=1\). Define \(C=\{i\in\{1,\dots,n\}\mid \bar{w}[i]=0\}\). It holds that \(S\subseteq C\). By property (2), we have two possible cases. If \(|C|\leqslant q\), then \(C\) is a vertex cover, and we obtain a contradiction. If \(|C|= q+1\), we pick any \(u\in C\setminus S\) (recall \(p < q\)), and then \(C\setminus \{u\}\) is a superset of \(S\) with \(|C\setminus \{u\}|=q\) that is a vertex cover; a contradiction.

For the other direction, suppose that \(X\subseteq \{1,\dots, n+(k+1)/2+(2q-n)\}\) is a sufficient reason for \(\bar{x}\) with \(|X|\leqslant p\). Take \(S=X\cap \{1,\dots,n\}\). We claim that no superset \(C\) of \(S\) with \(|C|\leqslant q\) is a vertex cover of \(G\). By contradiction, suppose that such a \(C\) exists. We can assume that \(|C|=q\). Take the vector \(\bar{z}=(\bar{w}_C, \bar{0}_{(k+1)/2}, \bar{0}_{2q-n})\), where \(\bar{w}_C[i]=0\), if \(i\in C\), and \(\bar{w}_C[i]=1\), otherwise. It holds that \(\bar{z}[i]=\bar{x}[i]=0\), for every \(i\in X\). Moreover, by property (1), we obtain that \(f^k_{S^+,S^-}(\bar{z})=1\). This is a contradiction. ◻