The Computational Complexity of Circuit Discovery for Inner Interpretability

## Abstract

Abstract Many proposed applications of neural networks in machine learning, cognitive/brain science, and society hinge on the feasibility of inner interpretability via circuit discovery. This calls for empirical and theoretical explorations of viable algorithmic options. Despite advances in the design and testing of heuristics, there are concerns about their scalability and faithfulness at a time when we lack understanding of the complexity properties of the problems they are deployed to solve. To address this, we study circuit discovery with classical and parameterized computational complexity theory: (1) we describe a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control; (2) we formalize a comprehensive set of queries that capture mechanistic explanation, and propose a formal framework for their analysis; (3) we use it to settle the complexity of many query variants and relaxations of practical interest on multi-layer perceptrons (part of, e.g., transformers). Our findings reveal a challenging complexity landscape. Many queries are intractable (NP-hard, Σ 2 p subscript superscript Σ 𝑝 2 \Sigma^{p}_{2} roman_Σ start_POSTSUPERSCRIPT italic_p end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT -hard), remain fixed-parameter intractable (W[1]-hard) when constraining model/circuit features (e.g., depth), and are inapproximable under additive, multiplicative, and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems (NP- vs. Σ 2 p subscript superscript Σ 𝑝 2 \Sigma^{p}_{2} roman_Σ start_POSTSUPERSCRIPT italic_p end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT -complete) with better-understood heuristics, and prove the tractability (PTIME) or fixed-parameter tractability (FPT) of more modest queries which retain useful affordances. This framework allows us to understand the scope and limits of interpretability queries, explore viable options, and compare their resource demands among existing and future architectures.

### 1 Introduction

As artificial neural networks (ANNs) grow in size and capabilities, Inner Interpretability — an emerging field tasked with explaining their inner workings (Räuker et al., ; Vilas et al., ) — attempts to devise scalable, automated procedures to understand systems mechanistically.
Many proposed applications of neural networks in machine learning, cognitive and brain sciences, and society, hinge on the feasibility of inner interpretability.
For instance, we might have to rely on interpretability methods to improve system safety (Bereska & Gavves, ), detect and control vulnerabilities (García-Carrasco et al., ),
prune for efficiency (Hooker et al., ), find and use task subnetworks (Zhang et al., ), explain internal concepts underlying decisions (Lee et al., ), experiment with neuro-cognitive models of language, vision, etc. (Lindsay, ; Lindsay & Bau, ; Pavlick, ), describe determinants of ANN-brain alignment (Feghhi et al., ; Oota et al., ), improve architectures, and extract domain insights (Räuker et al., ).
We will have to solve different instances of these interpretability problems, ideally automatically, for increasingly large models.
We therefore need efficient interpretability procedures, and this requires empirical and theoretical explorations of viable algorithmic options.

Circuit discovery and its challenges. Since top-down approaches to inner interpretability (see Vilas et al., ) work their way down from high-level concepts or algorithmic hypotheses (Lieberum et al., ), there is interest in a complementary bottom-up methodology: circuit discovery (see Shi et al., ; Tigges et al., ).
It centers around neuron- and circuit-level isolation or description (e.g., Hoang-Xuan et al., ; Lepori et al., ) and attempts to build up higher-level abstractions from this low-level foundation.
The motivation is the circuit hypothesis: that models implement their capabilities via small subnetworks (Shi et al., ).
Advances in the design and testing of interpretability heuristics (see Shi et al., ; Tigges et al., ) come alongside interest in the automation of circuit discovery (e.g., Conmy et al., ; Ferrando & Voita, ; Syed et al., ) and at the same time concerns about its feasibility (Voss et al., ; Räuker et al., ).
One issue is the challenge of scaling up methods to larger networks, more naturalistic datasets, and more complex tasks (e.g., Lieberum et al., ; Marks et al., ), given their search over large search spaces involving some manual-intensive steps (Voss et al., ).
A related issue is that current heuristics, though sometimes promising (e.g., Merullo et al., ), often yield discrepant results (see e.g., Shi et al., ; Niu et al., ; Zhang & Nanda, ).
They often find circuits that are not functionally faithful (Yu et al., ), or that lack the expected affordances (e.g., effects on behavior; Shi et al., ).
This questions whether certain localization methods yield results that inform editing (Hase et al., ), and vice versa (Wang & Veitch, ).
More broadly, we run into ‘interpretability illusions’ (Friedman et al., ) when our simplifications (e.g., circuits) mimic the local input-output behavior of the system but lack global faithfulness (Jacovi & Goldberg, ) .

Exploring viable algorithmic options. These challenges come at a time when, despite emerging theoretical frameworks (e.g., Vilas et al., ; Geiger et al., ), there are notable gaps in the formalization and analysis of the computational problems that interpretability heuristics attempt to solve (see e.g., Wang & Veitch, , §8).
Issues around scalability of circuit discovery and faithfulness have a natural formulation in the language of Computational Complexity Theory (Arora & Barak, ; Downey & Fellows, ).
A fundamental source of breakdown of scalability — which lack of faithfulness is one manifestation of — is the intrinsic resource demands of interpretability problems.
In order to design efficient and effective solutions, we need to understand the complexity properties of circuit discovery queries and the constraints that might be leveraged to yield the desired results.
Though a decade of experimental efforts has made promising inroads, the complexity-theoretic properties that naturally impact scalability and faithfulness remain open questions (see e.g., Subercaseaux, , §6C).
We settle them here by complementing these efforts with a systematic study of the computational complexity of circuit discovery for inner interpretability.
We present a framework that allows us to (a) understand the scope and limits of interpretability queries for description/explanation and prediction/control, (b) explore viable options, and (c) compare their resource demands among existing and future architectures.

#### 1.1 Contributions

- •
We present a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control.
- •
We formalize a comprehensive set of queries that capture mechanistic explanation, and propose a formal framework for their analysis.
- •
We use this framework to settle the complexity of many query variants, parameterizations, approximation schemes and relaxations of practical interest on multi-layer perceptrons, relevant to various architectures such as transformers.
- •
We demonstrate how our proof techniques can also be useful to draw links between interpretability and explainability by using them to improve existing results on the latter.

#### 1.2 Overview of results

- •
We uncover a challenging complexity landscape (see Table 4) where many queries are intractable (NP-hard, $\Sigma^{p}_{2}$-hard), remain fixed-parameter intractable (W[1]-hard) when constraining model/circuit features (e.g., depth), and are inapproximable under additive, multiplicative, and probabilistic approximation schemes.
- •
We prove there exist transformations to tackle some of these hard problems (NP- vs. $\Sigma^{p}_{2}$-complete) with better-understood heuristics, and prove the tractability (PTIME) or fixed-parameter tractability (FPT) of other queries of interest, and identify open problems.
- •
We describe a quasi-minimality property of ANN circuits and exploit it to generate tractable queries which retain useful affordances, and efficient algorithms to compute them.
- •
We establish a separation between local and global query complexity. Together with quasi-minimality, they explain interpretability illusions of faithfulness observed in experiments.

#### 1.3 Related work

This paper gives the first systematic exploration of the computational complexity of inner interpretability problems.
An adjacent area is the complexity analysis of explainability problems (Bassan & Katz, ; Ordyniak et al., ).
It differs from our work in its focus on input queries — aspects of the input that explain model decisions — whereas we look at the inner workings of neural networks via circuit queries.
Barceló et al. () study the explainability of multi-layer perceptrons compared to simpler models through a set of input queries.
Bassan et al. () extend this idea with a comparison between local and global explainability.
None of these works formalize or analyze circuit queries (although Subercaseaux, , identifies it as an open problem); we adapt the local versus global distinction in our framework and show how our proof techniques can tighten some results on explainability queries.
Ramaswamy () explores a small set of circuit queries and only on abstract biological networks modeled as general graphs, which cannot inform circuit discovery in ANNs.
More generally, we join efforts to build a solid theoretical foundation for interpretability (Bassan & Katz, ; Geiger et al., ; Vilas et al., ).

### 2 Mechanistic understanding of neural networks

Mechanistic understanding is a contentious topic (Ross & Bassett, ), but for our purposes it will suffice to adopt a pragmatic perspective.
In many cases of practical interest, we want our interpretability methods to output objects that allow us to, in some limited sense, (1) describe or explain succinctly, and (2) control or predict precisely.
Such objects (e.g., circuits) should be ‘efficiently queriable’; they are often referred to as “a way of making an explanation tractable” (Cao & Yamins, ).
Roughly, this means that we would like short descriptions (e.g., small circuits) with useful affordances (e.g., to readily answer questions and perform interventions of interest).
Circuits have the potential to fulfill these criteria (Olah et al., ).
Here we preview some special circuits with useful properties which we formalize and analyze later on.
Table 1 maps the main circuits we study to their corresponding affordances for description, explanation, prediction and control. Formal definitions of circuit queries are given alongside results in Section 4 (see also The Computational Complexity of Circuit Discovery for Inner Interpretability).

**Table 1: Circuit affordances for description, explanation, prediction, and control.**
| Circuit | Affordance |  |
| --- | --- | --- |
| Description / Explanation | Prediction / Control |  |
| Sufficient Circuit | Which neurons suffice in isolation to cause a behavior? Minimum: shortest description possible in the model. | Inference in isolation. Minimal: ablating any neuron breaks behavior of the circuit. |
| Quasi-minimal Sufficient Circuit | Which neurons suffice in isolation to cause a behavior and which is a breaking point? | Ablating the breaking point breaks behavior of the circuit. |
| Necessary Circuit | Which neurons are part of all circuits for a behavior? Key subcomputations? | Ablating the neurons breaks behavior of any sufficient circuit in the network. |
| Circuit Ablation & Clamping | Which neurons are necessary in the current configuration of the network? | Ablating/Clamping the neurons breaks behavior of the network. |
| Circuit Robustness | How much redundancy supports a behavior? How resilient is it to perturbations? | Ablating any set of neurons of size below threshold does not break behavior. |
| Patched Circuit | Which neurons drive a behavior in a given input context? Control nodes? | Patching neurons changes network behavior for inputs of interest. Steering; Editing. |
| Quasi-minimal Patched Circuit | Which neurons can drive a behavior in a given input context and which neuron is a breaking point? | Patching neurons causes target behavior for inputs of interest; Unpatching breaking point breaks target behavior. |
| Gnostic Neurons | Which neurons respond preferentially to a certain concept? | Concept editing; guided synthesis. |

### 3 Inner interpretability queries as computational problems

We model post-hoc interpretability queries on neural networks as computational problems in order to analyze their intrinsic complexity properties.
These circuit queries also formalize criteria for desired circuits, including those appearing in the literature, such as ‘faithfulness’, ‘completeness’, and ‘minimality’ (Wang et al., ; Yu et al., ).

#### 3.1 Query variants: coverage, size and minimality

The coverage of a circuit refers to the domain over which it behaves in a certain way (e.g., faithful to the model’s prediction).
Local circuits do so over a restricted set of inputs.
Global circuits do so over all possible inputs.
The size of a circuit is measured in number of neurons.
Some circuit queries will require circuits of bounded size whereas others leave the size unbounded.
A circuit with a certain property (e.g., local sufficiency) is minimal if there is no subset of its neurons that also has that property (not to be confused with minimum size among all such circuits present in the network).
To fit our comprehensive suite of problems, we explain how to generate problem variants and later on only present one representative definition of each. (We simplify without loss of generality).

###### Problem 0 ( ProblemName (PN) )

- Input:
a multi-layer perceptron $\mathcal{M}$, CoverageIN, SizeIN.
- Output:
a Property circuit $\mathcal{C}$ in $\mathcal{M}$ of SizeOUT, such that
CoverageOUT $\mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})$, Suffix.

Input: and Table 2 illustrate how to generate problem variants using a template, and ProblemName = Sufficient Circuit as an example.
Problem definitions will be given for search (return specified circuits) or decision (answer yes/no circuit queries) versions.
Others, including optimization (return maximum/minimum-size circuits), can be generated by assigning variables.
Problems presented later on are obtained similarly.
We also explore various parameterizations, approximation schemes, and relaxations that we explain in the following sections as needed.

**Table 2: Generating query variants from problem templates.**
| Description<br>variables | Query variants |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Local | Global |  |  |  |  |  |
| Bounded | Unbounded | Optimal | Bounded | Unbounded | Optimal |  |
| CoverageIN | an input $\mathbf{x}$ | an input $\mathbf{x}$ | an input $\mathbf{x}$ | “ ” | “ ” | “ ” |
| CoverageOUT | “ ” | “ ” | “ ” | $\forall_{\mathbf{x}}$ | $\forall_{\mathbf{x}}$ | $\forall_{\mathbf{x}}$ |
| SizeIN | int. $u\leq|\mathcal{M}|$ | “ ” | “ ” | int. $u\leq|\mathcal{M}|$ | “ ” | “ ” |
| SizeOUT | size $|\mathcal{C}|\leq u$ | “ ” | min. size | size $|\mathcal{C}|\leq u$ | “ ” | min. size |
| Property | minimal / “ ” | minimal / “ ” | “ ” | minimal / “ ” | minimal / “ ” | “ ” |
| Suffix | if it exists, otherwise $\bot$ | “ ” | “ ” | if it exists, otherwise $\bot$ | “ ” | “ ” |

###### Problem 0 ( ProblemName (PN) )

#### 3.2 Classical and parameterized complexity

We prove theorems about interpretability queries building on techniques from classical (Garey & Johnson, ) and parameterized complexity (Downey & Fellows, ).
Here we give a brief, informal overview of the main concepts underlying our analyses (see The Computational Complexity of Circuit Discovery for Inner Interpretability for extensive formal definitions).
We will explore beyond classical polynomial-time tractability (PTIME) by studying fixed-parameter tractability (FPT).
This allows a more fine-grained look at the sources of complexity of problems.
NP-hard queries are considered intractable because they cannot be computed by polynomial-time algorithms.
However, a relaxation of interest is to allow unreasonable resource demands as long as they are contained in problem parameters that can be kept small in practice.
Parameterizing a given neural network and requested circuit leads to parameterized problems (see Table 3 for problem parameters we study later).
Parameterized queries in FPT admit fixed-parameter tractable algorithms.
W-hard queries, however, do not.
We study counting problems via analogous classes #P and #W[1].
We also investigate completeness for NP and classes higher up the polynomial hierarchy such as $\Sigma^{p}_{2}$ and $\Pi^{p}_{2}$ to explore the possibility to tackle hard interpretability problems with better-understood methods for well-known NP-complete problems (de Haan & Szeider, ).
Most proof techniques involve various kinds of reductions between computational problems.

**Table 3: Model and circuit parameterizations.**
| Parameter description | Notation |  |
| --- | --- | --- |
|  | Model (given) | Circuit (requested) |
| Number of layers (depth) | $\hat{L}$ | $\hat{l}$ |
| Maximum layer width | $\hat{L}_{w}$ | $\hat{l}_{w}$ |
| Total number of units(^1^11Note the colored parameters bound the input size if bounded (hence vacuously making problems tractable). We avoid this in analyses.) | $\hat{U}=|\mathcal{M}|\leq\hat{L}\cdot\hat{L}_{w}$ | $|\mathcal{C}|=\hat{u}$ |
| Number of input units | $\hat{U}_{I}$ | $\hat{u}_{I}$ |
| Number of output units | $\hat{U}_{O}$ | $\hat{u}_{O}$ |
| Maximum weight | $\hat{W}$ | $\hat{w}$ |
| Maximum bias | $\hat{B}$ | $\hat{b}$ |

#### 3.3 Approximation

Although sometimes computing optimal solutions is intractable, it is conceivable we could devise tractable interpretability procedures to obtain approximate solutions that are useful in practice.
We consider 5 notions of approximation: additive, multiplicative, and three probabilistic schemes (see The Computational Complexity of Circuit Discovery for Inner Interpretability for formal definitions).
Additive approximation algorithms return solutions at most a fixed distance $c$ away from optimal (e.g., from the minimum-sized circuit), ensuring that errors cannot get impractically large ($c$-approximability).
Multiplicative approximation returns solutions at most a factor of optimal away.
Some hard problems allow for polynomial-time multiplicative approximation schemes (PTAS) where we can get arbitrarily close to optimal solutions as long as we expend increasing compute time (Ausiello et al., ).
Finally, consider three other types of probabilistic polynomial-time approximability (henceforth 3PA) that may be acceptable in situations where always getting the correct output for an input is not required: (1) algorithms that always run in polynomial time and produce the correct output for a given input in all but a small number of cases (Hemaspaandra & Williams, ); (2) algorithms that always run in polynomial time and produce the correct output for a given input with high probability (Motwani & Raghavan, ); and (3) algorithms that run in polynomial time with high probability but are always correct (Gill, ).

#### 3.4 Model architecture

The Multi-Layer Perceptron (MLP) is a natural first step in our exploration because (a) it is proving useful as a stepping stone in current experimental (e.g., Lampinen et al., ) and theoretical work (e.g., Rossem & Saxe, ; McInerney & Burke, ); (b) it exist as a leading standalone architecture (Yu et al., ), as the central element of all-MLP architectures (Tolstikhin et al., ), and as a key component of state-of-the-art models such as transformers (Vaswani et al., ); (c) they are of active interest to the interpretability community (e.g., Geva et al., ; ; Dai et al., ; Meng et al., ; ; Niu et al., ; Vilas et al., ; Hanna et al., ); and (d) we can relate our findings on the complexity of inner interpretability to those of explainability which also begins with MLPs (e.g., Barceló et al., ; Bassan et al., ).
Although MLP blocks can be taken as a unit to simplify search, it is recommended to investigate MLPs by treating each neuron as a unit (e.g., Gurnee et al., ; Cammarata et al., ; Olah et al., ), as it better reflects the semantics of computations in neural networks (Lieberum et al., , sec. 2.3.1). We adopt this perspective in our analyses.
We write $\mathcal{M}$ for an MLP model and $\mathcal{M}(\mathbf{x})$ for its output on input vector $\mathbf{x}$.
Its size $|\mathcal{M}|$ is the number of neurons.
A circuit $\mathcal{C}$ is a subset of neurons which induce a (possibly end-to-end) subgraph of $\mathcal{M}$ (see The Computational Complexity of Circuit Discovery for Inner Interpretability for formal definitions).

### 4 Results & Discussion: the complexity of circuit discovery

In this section we present each circuit query with its computational problem and a discussion of the complexity profile we obtain across variants, relaxations, and parameterizations. For an overview of the results for all queries, see Table 4.
Proofs of the theorems can be found in the The Computational Complexity of Circuit Discovery for Inner Interpretability.

#### 4.1 Sufficient Circuit

Sufficient circuits (SCs) are sets of neurons connected end-to-end that suffice, in isolation, to reproduce some model behavior over an input domain.
Therefore, they are conceptually related to the desired outcome of masking components that do not contribute to the behavior of interest (small, parameter-efficient subnetworks).
SCs remain relevant as, despite valid criticisms of zero-ablation (e.g., Conmy et al., ), circuit discovery through pruning might be justified (Yu et al., ).

###### Problem 1 ( Bounded Locally Sufficient Circuit (BLSC) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an input vector $\mathbf{x}$, and an integer $u\leq|\mathcal{M}|$.
- Output:
a circuit $\mathcal{C}$ in $\mathcal{M}$ of size $|\mathcal{C}|\leq u$, such that $\mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})$, if it exists, otherwise $\bot$.

We find that many variants of SC are NP-hard (see Table 4).
Counterintuitively, this intractability does not depend straightfowardly on parameters such as network depth (W[1]-hard relative to $\mathcal{P}$).
Therefore, hardness is not mitigated by keeping models shallow.
Given this barrier, we explore the possibility of obtaining approximate solutions but find that hard SC variants are inapproximable relative to all schemes in Section 3.3.
An alternative is to consider the membership of these problems in a well-studied class whose solvers are better understood than interpretability heuristics (de Haan & Szeider, ).
We prove that local versions of SC are NP-complete.
This implies there exist efficient transformations from instances of SC to those of the satisfiability problem (SAT), opening up the possibility to borrow techniques that work reasonably well in practice for SAT (Biere et al., ).
Interestingly, this is not possible for the global version, which we prove is complete for a class higher up the complexity hierarchy ($\Sigma^{p}_{2}$-complete).
This result establishes a formal separation between local and global query complexity that partly explains ‘interpretability illusions’ (Friedman et al., ; Yu et al., ) arising in practice due to local but not global faithfulness.

Next we explore the following alternative scenario.
Given a model and a target behavior, if we knew that SCs with some desired property (e.g., minimality) are abundant, this would provide some confidence in the ability of heuristic search to stumble upon one of them.
To explore this, we analyze various queries where the output is a count of the number of SCs (i.e., counting problems).
We find that both local and global, bounded and unbounded variants are #P-complete and remain intractable (#W[1]-hard) when parameterized by many network features including depth (Table 3).

The hardness profile of SC over all these variants calls for exploring more substantial relaxations.
We introduce the notion of quasi-minimality of SCs for this purpose and later demonstrate its usefulness beyond this particular problem.
Any neuron in a minimal/minimum SC is a breaking point in the sense that removing it will break the target behavior.
In quasi-minimal SCs we are guaranteed to know at least one neuron that causes this breakdown, though there may be other neurons that do not.

###### Problem 2 ( Unbounded Quasi-minimal Locally Sufficient Circuit (UQLSC) )

- Input:
a multi-layer perceptron $\mathcal{M}$, and an input vector $\mathbf{x}$.
- Output:
a circuit $\mathcal{C}$ in $\mathcal{M}$ and a neuron $v\in\mathcal{C}$ such that
$\mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})$ and $[\mathcal{C}\setminus\{v\}](\mathbf{x})\neq\mathcal{M}(\mathbf{x})$.

By introducing this relaxation, which gives up some affordances but retains others of interest, we get a feasible interpretability query. Input: is in PTIME.
We describe an efficient algorithm to compute it which can be heuristically biased towards finding smaller circuits and combined with techniques that exploit weights and gradients (see The Computational Complexity of Circuit Discovery for Inner Interpretability).

###### Problem 1 ( Bounded Locally Sufficient Circuit (BLSC) )

###### Problem 2 ( Unbounded Quasi-minimal Locally Sufficient Circuit (UQLSC) )

#### 4.2 Gnostic Neuron

Gnostic neurons, sometimes called ‘grandmother neurons’ in neuroscience (Gale et al., ) and ‘concept neurons’ or ‘object detectors’ in AI (e.g., Bau et al., ), are one of the oldest and still current interpretability queries of interest (see also ‘knowledge neurons’; Niu et al., ).

###### Problem 3 ( Bounded Gnostic Neurons (BGN) )

- Input:
A multi-layer perceptron $\mathcal{M}$ and two sets of input vectors $\mathcal{X}$ and $\mathcal{Y}$, an integer $k$, and an activation threshold $t$.
- Output:
A set of neurons $V$ in $\mathcal{M}$ of size $|V|\geq k$ such that $\forall_{v\in V}$ it is the case that $\forall_{\mathbf{x}\in\mathcal{X}}$ computing $\mathcal{M}(\mathbf{x})$ produces activations $A^{v}_{\mathbf{x}}\geq t$ and $\forall_{\mathbf{y}\in\mathcal{Y}}:A^{v}_{\mathbf{y}}<t$,
if it exists, otherwise $\bot$.

It is probably not a coincidence that (i) the idea and search for such neurons has emerged early and remained popular, and (ii) it is a tractable problem.
Input: is in PTIME.
Alternatives might require GNs to have some behavioral effect when intervened; such variants would remain tractable.

###### Problem 3 ( Bounded Gnostic Neurons (BGN) )

#### 4.3 Circuit Ablation and Clamping

The idea that some neurons perform key subcomputations for certain tasks naturally leads to the hypothesis that ablating them should have downstream effects on the corresponding model behaviors.
Searching for neuron sets with this property has been one strategy (i.e., zero-ablation) to get at important circuits (Wang & Veitch, ).
The circuit ablation (CA) problem formalizes this idea.

###### Problem 4 ( Bounded Local Circuit Ablation (BLCA) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an input vector $\mathbf{x}$, and an integer $u\leq|\mathcal{M}|$.
- Output:
a subset of neurons $\mathcal{C}$ in $\mathcal{M}$ of size $|\mathcal{C}|\leq u$, such that $[\mathcal{M}\setminus\mathcal{C}](\mathbf{x})\neq\mathcal{M}(\mathbf{x})$,
if it exists, otherwise $\bot$.

A difference between CAs and minimal SCs is that the former can be interpreted as a possibly non-minimal breaking set in the context of the whole network whereas the latter is by default a minimal breaking set when the SC is taken in isolation. In this sense, CA can be seen as a less stringent criterion for circuit affordances. A related idea is circuit clamping (CC): fixing the activations of certain neurons to a level that produces a change in the behavior of interest.

###### Problem 5 ( Bounded Local Circuit Clamping (BLCC) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an input vector $\mathbf{x}$, a value $r$, and an integer $u$ with $1<u\leq|\mathcal{M}|$.
- Output:
a subset of neurons $\mathcal{C}$ in $\mathcal{M}$ of size $|\mathcal{C}|\leq u$, such that for the $\mathcal{M}^{*}$ induced by clamping all $c\in\mathcal{C}$ to value $r$, $\mathcal{M}^{*}(\mathbf{x})\neq\mathcal{M}(\mathbf{x})$, if it exists, otherwise $\bot$.

Despite these more modest criteria, we find that both the local and global variants of CA and CC are NP-hard, fixed-parameter intractable W[1]-hard relative to various parameters, and inapproximable in all 5 senses studied.
However, we prove these problems are in NP-complete, which opens up practical options not available for other problems we study (see remarks in Section 4.1).

###### Problem 4 ( Bounded Local Circuit Ablation (BLCA) )

###### Problem 5 ( Bounded Local Circuit Clamping (BLCC) )

#### 4.4 Circuit Patching

A critique of zero-ablation is the arbitrariness of the value, leading to alternatives such as mean-ablation (e.g., Wang et al., ).
A related contrast is studying circuits in isolation versus embedded in surrounding subnetworks.
Activation patching (Ghandeharioun et al., ; Zhang & Nanda, ) and path patching (Goldowsky-Dill et al., ) try to pinpoint which activations play an in-context role in model behavior over a domain, which inspires the circuit patching (CP) problem.

###### Problem 6 ( Bounded Local Circuit Patching (BLCP) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an integer $k$, an input vector $\mathbf{y}$, and a set $\mathcal{X}$ of input vectors.
- Output:
a subset $\mathcal{C}$ in $\mathcal{M}$ of size $|\mathcal{C}|\leq k$, such that for the $\mathcal{M}^{*}$ induced by patching $\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{y})$ and $\mathcal{M}\setminus\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{x})$, $\mathcal{M}^{*}(\mathbf{x})=\mathcal{M}(\mathbf{y})$ for all $\mathbf{x}\in\mathcal{X}$, if it exists, otherwise $\bot$.

We find that local/global variants are intractable (NP-hard) in a way that does not depend on parameters such as network depth or size of the patched circuit (W[1]-hard), and are inapproximable ($\{c,\text{PTAS},\text{3PA}\}$-inapprox.).
Although we also prove the local variant of CP is NP-complete and therefore approachable in practice with solvers for hard problems not available for the global variants (see remarks in Section 4.1), these complexity barriers motivate exploring further relaxations.
With some modifications the idea of quasi-minimality can be repurposed to do useful work here.

###### Problem 7 ( Unbounded Quasi-minimal Local Circuit Patching (UQLCP) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an input vector $\mathbf{y}$, and a set $\mathcal{X}$ of input vectors.
- Output:
a subset $\mathcal{C}$ in $\mathcal{M}$ and a neuron $v\in\mathcal{C}$, such that for the $\mathcal{M}^{*}$ induced by patching $\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{y})$ and $\mathcal{M}\setminus\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{x})$,
$\forall_{\mathbf{x}\in\mathcal{X}}:\mathcal{M}^{*}(\mathbf{x})=\mathcal{M}(
\mathbf{y})$, and for $\mathcal{M}^{\prime}$ induced by patching identically
except for $v\in\mathcal{C}$, $\exists_{\mathbf{x}\in\mathcal{X}}:\mathcal{M}^{\prime}(\mathbf{x})\neq
\mathcal{M}(\mathbf{y})$.

In this way we obtain a tractable query (PTIME) for quasi-minimal patching, sidestepping barriers while retaining some useful affordances (see Table 1).
We present an algorithm to compute Input: efficiently that can be combined with strategies exploiting weights and gradients (see The Computational Complexity of Circuit Discovery for Inner Interpretability).

**Table 4: Classical and parameterized complexity results by problem variant.**
| Classical &<br>parameterized problems(^2^22Problem versions are for bounded size circuits unless otherwise stated. Each cell contains the complexity of the problem variant in terms of classical and FP (in)tractability, membership in complexity classes, and various approximation schemes. ‘?’ marks potentially fruitful open problems. ‘N/A’ stands for not applicable.)<br>$\mathcal{P}_{\mathcal{M}}=\{\hat{L},\hat{U}_{I},\hat{U}_{O},\hat{W},\hat{B}\}<br>\newline<br>\mathcal{P}_{\mathcal{C}}=\{\hat{l},\hat{l}_{w},\hat{u},\hat{u}_{I},\hat{u}_{O<br>},\hat{w},\hat{b}\}$ | Problem variants |  |  |  |
| --- | --- | --- | --- | --- |
| Local | Global |  |  |  |
| Decision/Search | Optimization | Decision/Search | Optimization |  |
| Sufficient Circuit (SC) | NP-complete | {$c$, PTAS, 3PA}-inapproximable | $\Sigma^{p}_{2}$-complete | {$c$, PTAS, 3PA}-inapproximable |
| $\mathcal{P}$-SC<br>$(\mathcal{P}=\mathcal{P}_{\mathcal{M}}\cup\mathcal{P}_{\mathcal{C}})$ | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable |
| Minimal SC | NP-complete | ? | $\in\Sigma^{p}_{2}$ NP-hard | ? |
| $\mathcal{P}$-Minimal SC | W[1]-hard | ? | W[1]-hard | ? |
| Unbounded Minimal SC | ? | N<br>A | $\in\Sigma^{p}_{2}$ NP-hard | N<br>A |
| $\mathcal{P}$-Unbounded Minimal SC | ? |  | ? |  |
| Unbounded Quasi-Minimal SC | PTIME |  | ? |  |
| Count SC | #P-complete | N<br>A | #P-hard | N<br>A |
| $\mathcal{P}$-Count SC | #W[1]-hard |  | #W[1]-hard |  |
| Count Minimal SC | #P-complete |  | #P-hard |  |
| $\mathcal{P}$-Count Minimal SC | #W[1]-hard |  | #W[1]-hard |  |
| Count Unbounded Minimal SC | #P-complete |  | #P-hard |  |
| Gnostic Neuron (GN) | PTIME | N/A | ? | N/A |
| Circuit Ablation (CA) | NP-complete | {$c$, PTAS, 3PA}-inapproximable | $\in\Sigma^{p}_{2}$ NP-hard | {$c$, PTAS, 3PA}-inapproximable |
| $\{\hat{L},\hat{U}_{I},\hat{U}_{O},\hat{W},\hat{B},\hat{u}\}$-CA | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable |
| Circuit Clamping (CC) | NP-complete | {$c$, PTAS, 3PA}-inapproximable | $\in\Sigma^{p}_{2}$ NP-hard | {$c$, PTAS, 3PA}-inapproximable |
| $\{\hat{L},\hat{U}_{O},\hat{W},\hat{B},\hat{u}\}$-CC | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable |
| Circuit Patching (CP) | NP-complete | {$c$, PTAS, 3PA}-inapproximable | $\in\Sigma^{p}_{2}$ NP-hard | {$c$, PTAS, 3PA}-inapproximable |
| $\{\hat{L},\hat{U}_{O},\hat{W},\hat{B},\hat{u}\}$-CP | W[2]-hard | {$c$, PTAS, 3PA}-inapproximable | W[2]-hard | {$c$, PTAS, 3PA}-inapproximable |
| Unbounded Quasi-Minimal CP | PTIME | N/A | ? | N/A |
| Necessary Circuit (NC) | $\in\Sigma^{p}_{2}$ NP-hard | {$c$, PTAS, 3PA}-inapproximable | $\in\Sigma^{p}_{2}$ NP-hard | {$c$, PTAS, 3PA}-inapproximable |
| $\{\hat{L},\hat{U}_{I},\hat{U}_{O},\hat{W},\hat{u}\}$-NC | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable | W[1]-hard | {$c$, PTAS, 3PA}-inapproximable |
| Count NC | ? | ? | ? | ? |
| Circuit Robustness (CR) | coNP-complete | ? | $\in\Pi^{p}_{2}$ coNP-hard | ? |
| $\{\hat{L},\hat{U}_{I},\hat{U}_{O},\hat{W},\hat{B},\hat{u}\}$-CR | coW[1]-hard | ? | coW[1]-hard | ? |
| {$|H|$}-CR | FPT | FPT | ? | ? |
| {$|H|$, $\hat{U}_{I}$}-CR | FPT | FPT | FPT | FPT |
| Sufficient Reasons (SR) | $\in\Sigma^{p}_{2}$ NP-hard | {3PA}-inapproximable | N<br>A |  |
| $\{\hat{L},\hat{U}_{O},\hat{W},\hat{B},\hat{u}\}$-SR | W[1]-hard | {3PA}-inapproximable |  |  |

###### Problem 6 ( Bounded Local Circuit Patching (BLCP) )

###### Problem 7 ( Unbounded Quasi-minimal Local Circuit Patching (UQLCP) )

#### 4.5 Necessary Circuit

The criterion of necessity is a stringent one, and consequently necessary circuits (NCs) carry powerful affordances (see Table 1). Since neurons in NCs collectively interact with all possible sufficient circuits for a target behavior, they are candidates to describe key task subcomputations and intervening on them is guaranteed to have effects even in the presence of high redundance.

###### Problem 8 ( Bounded Globally Necessary Circuit (BGNC) )

- Input:
A multi-layer perceptron $\mathcal{M}$, and an integer $k$.
- Output:
A subset $\mathcal{S}$ of neurons in $\mathcal{M}$ of size $|\mathcal{S}|\leq k$, such that $\mathcal{S}\cap\mathcal{C}\neq\emptyset$ for every circuit $\mathcal{C}$ in $\mathcal{M}$ that is sufficient relative to all possible input vectors, if it exists, otherwise $\bot$.

Unfortunately both local and global versions of NC are NP-hard (in $\Sigma^{p}_{2}$; Table 4), remain intractable even when keeping parameters such as network depth, number of input and output neurons, and others small (Table 3), and does not admit any of the available approximation schemes (Section 3.3).
Tractable versions of NC are unlikely unless substantial restrictions or relaxations are introduced.

###### Problem 8 ( Bounded Globally Necessary Circuit (BGNC) )

#### 4.6 Circuit Robustness

A behavior of interest might be over-determined or resilient in the sense that many circuits in the model implement it and one can take over when the other breaks down.
This is related to the notion of redundancy used in neuroscience (e.g., Nanda et al., ).
Intuitively, when a model implements a task in this way, the behavior should be more robust to a number of perturbations.
The possibility of verifying it experimentally motivates the circuit robustness (CR) problem.

###### Problem 9 ( Bounded Local Circuit Robustness (BLCR) )

- Input:
A multi-layer perceptron $\mathcal{M}$, a subset $H$ of $\mathcal{M}$, an input vector $\mathbf{x}$, and an integer $k$ with $1\leq k\leq|H|$.
- Output:
<YES> if for each subset $H^{\prime}\subseteq H$, with $|H^{\prime}|\leq k$,
$\mathcal{M}(\mathbf{x})=[\mathcal{M}\setminus H^{\prime}](\mathbf{x})$,
otherwise <NO>.

We find that Local CR is coNP-complete while Global CR is in $\Pi^{p}_{2}$ and coNP-hard.
It remains fixed-parameter intractable (coW[1]-hard) relative to model parameters (Table 3).
Pushing further, we explore parameterizing CR by $\{|H|\}$ and prove fixed-parameter tractability of $\{|H|\}$-CR which holds both for the local and global versions.
There exist algorithms for CR that scale well as long as $|H|$ is reasonable; a scenario that might be useful to probe robustness in practice. This wraps up our results for circuit queries.
We briefly digress into explainability before discussing some implications.

###### Problem 9 ( Bounded Local Circuit Robustness (BLCR) )

#### 4.7 Sufficient Reasons

Understanding the sufficient reasons (SR) for a model decision in terms of input features consists of knowledge of values of the input components that are enough to determine the output. Given a model decision on an input, the most interesting reasons are those with the least components.

###### Problem 10 ( Bounded Local Sufficient Reasons (BLSR) )

- Input:
a multi-layer perceptron $\mathcal{M}$, an input vector $\mathbf{x}$ of length $|\mathbf{x}|=\hat{u}_{I}$, and an integer $k$ with $1\leq k\leq\hat{u}_{I}$.
- Output:
a subset $\mathbf{x}^{s}$ of $\mathbf{x}$ of size $|\mathbf{x}^{s}|=k$, such that for every possible completion $\mathbf{x}^{c}$ of $\mathbf{x}^{s}$ $\mathcal{M}(\mathbf{x^{c}})=\mathcal{M}(\mathbf{x})$, if it exists, otherwise $\bot$.

To demonstrate the usefulness of our framework beyond inner interpretability, we show how it links to explainability.
Using our techniques for circuit queries, we significantly tighten existing results for SR (Barceló et al., ; Wäldchen et al., ) by proving that hardness (NP-hard, W[1]-hard, 3PA-inapprox.) holds even when the model has only one hidden layer.

###### Problem 10 ( Bounded Local Sufficient Reasons (BLSR) )

### 5 Implications, limitations, and future directions

We presented a framework based on parameterized complexity to accompany experiments on inner interpretability with theoretical explorations of viable algorithms.
With this grasp of circuit query complexity, we can understand the challenges of scalability and the mixed outcomes of experiments with heuristics for circuit discovery.
We can explain ‘interpretability illusions’ (Friedman et al., ) due to lack of faithfulness, minimality (e.g., Shi et al., ; Yu et al., ) and other affordances (Wang & Veitch, ; Hase et al., ), in terms of the kinds of circuits that our current heuristics are well-equipped to discover.
For instance, consider the algorithm for automated circuit discovery proposed by Conmy et al. (), which eliminates one network component at a time if the consequence on behavior is reasonably small.
Since this algorithm runs in polynomial time, it is not likely to solve the problems proven hard here, such as Minimal Sufficient Circuit.
However, one reason we observe interesting results in some cases is because it is well-equipped to solve Quasi-Minimal Circuit problems.
As our conceptual and formal analyses show, quasi-minimal circuits can mimic various desirable aspects of sufficient circuits (Table 1), and the former can be found tractably (results for Input: and Input:).
Indeed, from our proof of tractability of QMSC (see The Computational Complexity of Circuit Discovery for Inner Interpretability) we get a hint on how to improve the running time of the algorithm in Conmy et al. () while retaining guarantees of quasi-minimality; namely, by using a variant of binary search to cut the number of forward passes from $n$ to $\log_{2}(n)$.
At the same time, understanding these properties of circuit discovery heuristics helps us explain observed discrepancies: why we often see (1) lack of faithfulness (i.e., global coverage is out of reach for QMC algorithms), (2) non-minimality (i.e., QM circuits can have many non-breaking points), and (3) large variability in performance across tasks and analysis parameters (e.g., Shi et al., ; Conmy et al., ).

Our results for inner interpretability complement those of explainability (e.g., Barceló et al., ; Bassan et al., ; Wäldchen et al., ).
These two complexity aspects can be studied together for different architectures to assess their intrinsic interpretability.
As in explainability, our findings suggest interpretability methods can be sought relative to additional query restrictions or relaxations.
We have explored many and some yield tractability while retaining affordances of practical interest.

One possibly fruitful avenue we have not explored is to conduct an empirical and formal characterization of learned weights in search of structure that could potentially distinguish conditions of (in)tractability.
Another avenue is to design queries that partially rely on mid-level abstractions (Vilas et al., ) to bridge the gap between circuits and human-intelligible algorithms (e.g., key-value mechanisms; Geva et al., ; Vilas et al., ).

### Acknowledgments

We thank Ronald de Haan for comments on proving membership using alternating quantifier formulas.

## Appendix: Definitions, Theorems and Proofs

### Appendix A Preliminaries

Each section of this appendix is self-contained except for the following definitions.
We re-state interpretability query definitions in a more detailed form in each section for convenience.
To err here on the side of rigor, here we will use more cumbersome notation that we avoided in the main manuscript for succinctness.

#### A.1 Computational problems of known complexity

Some of our proofs construct reductions from the following computational problems.

Clique (Garey & Johnson, , Problem GT19)
Input: An undirected graph $G=(V,E)$ and a positive integer $k$.
Question: Does $G$ have a clique of size at least $k$, i.e.,
a subset $V^{\prime}\subseteq V$, $|V^{\prime}|\geq k$, such that for
all pairs $v,v^{\prime}\in V^{\prime}$, $(v,v^{\prime})\in E$?

Vertex cover (VC) (Garey & Johnson, , Problem GT1)
Input: An undirected graph $G=(V,E)$ and a positive integer $k$.
Question: Does $G$ contain a vertex cover of size at most $k$, i.e.,
a subset $V^{\prime}\subseteq V$, $|V^{\prime}|\leq k$, such that for
all $(u,v)\in E$, at least one of $u$ or $v$ is in $V^{\prime}$?

Dominating set (DS) (Garey & Johnson, , Problem GT2)
Input: An undirected graph $G=(V,E)$ and a positive integer $k$.
Question: Does $G$ contain a dominating set of size at most $k$, i.e.,
a subset $V^{\prime}\subseteq V$, $|V^{\prime}|\leq k$, such that for all
$v\in V$, either $v\in V^{\prime}$ or there is at least one
$v^{\prime}\in V^{\prime}$ such that $(v,v^{\prime})\in E$?

Hitting set (HS) (Garey & Johnson, , Problem SP8)
Input: A collection of subsets $C$ of a finite set $S$ and a
positive integer $k$.
Question: Is there a subset $S^{\prime}$ of $S$, $|S^{\prime}|\leq k$, such that
$S^{\prime}$ has a non-empty intersection with each set in $C$?

Minimum DNF Tautology (3DT) (Schaefer & Umans, , Problem L7)
Input: A 3-DNF tautology $\phi$ with $T$ terms over a set of variables
$V$ and a positive integer $k$.
Question: Is there a 3-DNF formula $\phi^{\prime}$ made up of $\leq k$ of the
terms in $\phi$ that is a also a tautology?

#### A.2 Classical and parameterized complexity

###### Definition 1 (Polynomial-time tractability) .

An algorithm is said to run in polynomial-time if the number of steps it performs is $O(n^{c})$, where $n$ is a measure of the input size and $c$ is some constant. A problem $\Pi$ is said to be tractable if it has a polynomial-time algorithm. P denotes the class of such problems.

Consider a more fine-grained look at the sources of complexity of problems.
The following is a relaxation of the notion of tractability, where unreasonable resource demands are allowed as long as they are constrained to a set of problem parameters.

###### Definition 2 (Fixed-parameter tractability) .

Let $\mathcal{P}$ be a set of problem parameters. A problem $\mathcal{P}$-$\Pi$ is fixed-parameter tractable relative to $\mathcal{P}$ if there exists an algorithm that computes solutions to instances of $\mathcal{P}$-$\Pi$ of any size $n$ in time $f(\mathcal{P})\cdot n^{c}$, where $c$ is a constant and $f(\cdot)$ some computable function. FPT denotes the class of such problems and includes all problems in P.

###### Definition 1 (Polynomial-time tractability) .

###### Definition 2 (Fixed-parameter tractability) .

#### A.3 Hardness and reductions

Most proof techniques in this work involve reductions between computational problems.

###### Definition 3 (Reducibility) .

A problem $\Pi_{1}$ is polynomial-time reducible to $\Pi_{2}$ if there exists a polynomial-time algorithm (reduction) that transforms instances of $\Pi_{1}$ into instances of $\Pi_{2}$ such that solutions for $\Pi_{2}$ can be transformed in polynomial-time into solutions for $\Pi_{1}$.
This implies that if a tractable algorithm for $\Pi_{2}$ exists, it can be used to solve $\Pi_{1}$ tractably.
Fpt-reductions transform an instance $(x,k)$ of some problem parameterized by $k$ into an instance $(x^{\prime},k^{\prime})$ of another problem, with $k^{\prime}\leq g(k)$, in time $f(k)\cdot p(|x|)$ where $p$ is a polynomial.
These reductions analogously transfer fixed-parameter tractability results between problems.

Hardness results are generally conditional on two conjectures with extensive theoretical and empirical support.
Intractability statements build on these as follows.

###### Conjecture 1 .

P $\neq$ NP.

###### Definition 4 (Polynomial-time intractability) .

The class NP contains all problems in P and more. Assuming 1,
NP-hard problems lie outside P.
These problems are considered intractable because they cannot be solved in polynomial-time (unless 1 is false; see Fortnow, ).

###### Conjecture 2 .

FPT $\neq$ W[1].

###### Definition 5 (Fixed-parameter intractability) .

The class W[1] contains all problems in the class FPT and more.
Assuming 2, W[1]-hard parameterized problems lie outside FPT.
These problems are considered fixed-parameter intractable, relative to a given parameter set, because no fixed-parameter tractable algorithm can exist to solve them (unless 2 is false; see Downey & Fellows, ).

The following two easily-proven lemmas will be useful in our parameterized complexity proofs.

###### Lemma 1 .

(Wareham, , Lemma 2.1.30)
If problem $\Pi$ is fp-tractable relative to aspect-set $K$ then $\Pi$ is fp-tractable for any aspect-set $K^{\prime}$ such that $K\subset K^{\prime}$.

###### Lemma 2 .

(Wareham, , Lemma 2.1.31)
If problem $\Pi$ is fp-intractable relative to aspect-set $K$ then $\Pi$ is fp-intractable for any aspect-set $K^{\prime}$ such that $K^{\prime}\subset K$.

###### Definition 3 (Reducibility) .

###### Conjecture 1 .

###### Definition 4 (Polynomial-time intractability) .

###### Conjecture 2 .

###### Definition 5 (Fixed-parameter intractability) .

###### Lemma 1 .

###### Lemma 2 .

#### A.4 Approximation

Although sometimes computing optimal solutions might be intractable, it is still conceivable that we could devise tractable procedures to obtain approximate solutions that are useful in practice.
We consider two natural notions of additive and multiplicative approximation and three probabilistic schemes.

##### A.4.1 Multiplicative approximation

For a minimization problem $\Pi$, let $OPT_{\Pi}(I)$ be an optimal solution for $\Pi$, $A_{\Pi}(I)$ be a solution for $\Pi$ returned by an algorithm $A$, and $m(OPT_{\Pi}(I))$ and $m(A_{\Pi}(I))$ be the values of these solutions.

###### Definition 6 (Multiplicative approximation algorithm) .

[Ausiello et al. , Def. 3.5].
Given a minimization problem $\Pi$, an algorithm $A$ is a multiplicative $\epsilon$-approximation algorithm for $\Pi$ if for each instance $I$ of $\Pi$, $m(A_{\Pi}(I))-m(OPT_{\Pi}(I))\leq\epsilon\times m(OPT_{\Pi}(I))$.

It would be ideal if one could obtain approximate solutions for a problem
$\Pi$ that are arbitrarily close to optimal if one is willing to allow
extra algorithm runtime.

###### Definition 7 (Multiplicative approximation scheme) .

[Adapted from Ausiello et al., , Def. 3.10].
Given a minimization problem $\Pi$, a polynomial-time approximation scheme
(PTAS) for $\Pi$ is a set $\cal{A}$ of algorithms such that for each integer
$k>0$, there is a $\frac{1}{k}$-approximation algorithm $A^{k}_{\Pi}\in\cal{A}$
that runs in time polynomial in $|I|$.

###### Definition 6 (Multiplicative approximation algorithm) .

###### Definition 7 (Multiplicative approximation scheme) .

##### A.4.2 Additive approximation

It would be useful to have guarantees that an approximation algorithm for our problems returns solutions at most a fixed distance away from optimal.
This would ensure errors cannot get impractically large.

###### Definition 8 (Additive approximation algorithm) .

[Adapted from Ausiello et al., , Def. 3.3]. An algorithm $A_{\Pi}$ for a problem $\Pi$ is a d-additive approximation algorithm ($d$-AAA) if there exists a constant $d$ such that for all instances $x$ of $\Pi$ the error between the value $m(\cdot)$ of an optimal solution $optsol(x)$ and the output $A_{\Pi}(x)$ is such that $|\ m(optsol(x))-m(A_{\Pi}(x))\ |\leq d$.

###### Definition 8 (Additive approximation algorithm) .

##### A.4.3 Probabilistic approximation

Finally, consider three other types of probabilistic polynomial-time approximability (henceforth 3PA) that may be acceptable in situations where always getting the correct output for an input is not required: (1) algorithms that always run in polynomial time and produce the correct output for a given input in all but a small number of cases (Hemaspaandra & Williams, ); (2) algorithms that always run in polynomial time and produce the correct output for a given input with high probability (Motwani & Raghavan, ); and (3) algorithms that run in polynomial time with high probability but are always correct (Gill, ).

#### A.5 Model architecture

###### Definition 9 (Multi-Layer Perceptron) .

[Adapted from Barceló et al. ].
A multi-layer perceptron (MLP) is a neural network model $\mathcal{M}$, with $\hat{L}$ layers, defined by sequences of
weight matrices $(\mathbf{W}_{1},\mathbf{W}_{2},\dots,\mathbf{W}_{\hat{L}}),\quad\mathbf{W}_{i}
\in\mathbb{Q}^{d_{i-1}\times d_{i}}$,
bias vectors $(\mathbf{b}_{1},\mathbf{b}_{2},\dots,\mathbf{b}_{\hat{L}}),\quad\mathbf{b}_{i}
\in\mathbb{Q}^{d_{i}}$,
and (element-wise) ReLU functions $(f_{1},f_{2},\dots,f_{\hat{L}-1}),\quad f_{i}(x):=\max(0,x).$
The final function is, without loss of generality, the binary step function $f_{\hat{L}}(x):=1\ \text{if}\ x\geq 0,\text{otherwise}\ 0.$
The computation rules for $\mathcal{M}$ are given by
$\mathbf{h}_{i}:=f_{i}(\mathbf{h}_{i-1}\mathbf{W}+\mathbf{b}_{i}),\quad\mathbf{
h}_{0}:=\mathbf{x},$
where $\mathbf{x}$ is the input. The output of $\mathcal{M}$ on $\mathbf{x}$ is defined as $\mathcal{M}(\mathbf{x}):=\mathbf{h}_{\hat{L}}$. The graph $G_{\mathcal{M}}=(V,E)$ of $\mathcal{M}$ has a vertex for each component of each $\mathbf{h}_{i}$. All vertices in layer $i$ are connected by edges to all vertices of layer $i+1$, with no intra-layer connections. Edges carry weights according to $\mathbf{W}_{i}$, and vertices carry the components of $\mathbf{b}_{i}$ as biases. The size of $\mathcal{M}$ is defined as $|\mathcal{M}|:=|V|$.

###### Definition 9 (Multi-Layer Perceptron) .

### Appendix B Local and Global Sufficient Circuit

Minimum locally sufficient circuit (MLSC)
Input: A multi-layer perceptron $M$ of depth $cd_{g}$ with $\#n_{tot,g}$ neurons
and maximum layer width $cw_{g}$, connection-value matrices $W_{1},W_{2},\ldots,W_{cd_{g}}$, neuron bias vector $B$, a Boolean input vector $I$ of length
$\#n_{g,in}$, and integers $d$, $w$, and $\#n$ such that $1\leq d\leq cd_{g}$, $1\leq w\leq cw_{g}$, and $1\leq\#n\leq\#n_{tot,g}$.
Question: Is there a subcircuit $C$ of $M$ of depth $cd_{r}\leq d$ with $\#n_{tot,r}\leq\#n$ neurons and maximum layer width $cw_{r}\leq w$ that produces the
same output on input $I$ as $M$?

Minimum globally sufficient circuit (MGSC)
Input: A multi-layer perceptron $M$ of depth $cd_{g}$ with $\#n_{tot,g}$ neurons
and maximum layer width $cw_{g}$, connection-value matrices $W_{1},W_{2},\ldots,W_{cd_{g}}$, neuron bias vector $B$,
and integers $d$, $w$, and $\#n$ such that
$1\leq d\leq cd_{g}$, $1\leq w\leq cw_{g}$, and $1\leq\#n\leq\#n_{tot,g}$.
Question: Is there a subcircuit $C$ of $M$ of depth $cd_{r}\leq d$ with $\#n_{tot,r}\leq\#n$ neurons and maximum layer width $cw_{r}\leq w$ that produces the
same output as $M$ on every possible Boolean input vector of
length $\#_{in,g}$?

Given a subset $x$ of the neurons in $M$, the subcircuit $C$ of $M$ based on
$x$ has the neurons in $x$ and all connections in $M$ among these neurons.
Note that in order for the output of $C$ to be equal to the output of $M$ on
input $I$, the numbers $\#n_{in,g}$ and $\#n_{out,g}$ of input and output
neurons in $M$ must exactly equal the numbers $\#n_{in,r}$ and $\#n_{out,r}$
of input and output neurons in $C$; hence, no input or output neurons can be
deleted from $M$ in creating $C$. Following Barceló et al. , page 4, all
neurons in $M$ use the ReLU activation function and the output $x$ of each
output neuron is stepped as necessary to be Boolean, i.e, $step(x)=0$ if
$x\leq 0$ and is $1$ otherwise.

For a graph $G=(V,E)$, we shall assume an ordering on the vertices and edges in $V$
and $E$, respectively. For each vertex $v\in V$, let the complete neighbourhood $N_{C}(v)$ of $v$ be the set
composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$
by a single edge, i.e., $v\cup\{u~{}|~{}u~{}\in V~{}\rm{and}~{}(u,v)\in E\}$.
Finally, let VCB be the version of VC in which each vertex in
$G$ has degree at most $B$.

We will prove various classical and parameterized results for MLSC and MGSC
using reductions from Clique (Theorem 1 and 7).
These reductions are summarized in Figure 1 and the
parameterized results are proved relative to the parameters in
Table 5. Additional reductions from VC and DS
(Theorems 5 and 103) use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

Figure: Figure 1: This figure summarizes the reduction from Clique.
Refer to caption: extracted/5918954/figures/reduction-clique.png

**Table 5: Parameters for the minimum sufficient subcircuit and reason problems.**
| Parameter | Description |  |
| --- | --- | --- |
| $cd_{g}$ | # layers in given MLP | All |
| $cw_{g}$ | max # neurons in layer in given MLP | All |
| $\#n_{tot,g}$ | total # neurons in given MLP | All |
| $\#n_{in,g}$ | # input neurons in given MLP | All |
| $\#n_{out,g}$ | # output neurons in given MLP | All |
| $B_{\max,g}$ | max neuron bias in given MLP | All |
| $W_{\max,g}$ | max connection weight in given MLP | All |
| $cd_{r}$ | # layers in requested subcircuit | M{L,G}SC |
| $cw_{r}$ | max # neurons in layer in requested subcircuit | M{L,G}SC |
| $\#n_{tot,r}$ | total # neurons in requested subcircuit | M{L,G}SC |
| $\#n_{in,r}$ | # input neurons in requested subcircuit | M{L,G}SC |
| $\#n_{out,r}$ | # output neurons in requested subcircuit | M{L,G}SC |
| $B_{\max,r}$ | max neuron bias in requested subcircuit | M{L,G}SC |
| $W_{\max,r}$ | max connection weight in requested subcircuit | M{L,G}SC |
| $k$ | Size of requested subset of input vector | MSR |

#### B.1 Results for MLSC

Towards proving NP-completeness, we first prove membership and then follow up with hardness.
Membership of MLSC in NP can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{C}\subseteq\mathcal{M}]:\mathcal{C}(\mathbf{x})=\mathcal{M}( \mathbf{x})$ $$

###### Theorem 1 .

If MLSC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from Clique to MLSC.
Given an instance $\langle G=(V,E),k\rangle$ of Clique, construct the following
instance $\langle M,I,d,w,\#n\rangle$ of MLSC:
Let $M$ be an MLP based on $\#n_{tot,g}=|V|+|E|+2$ neurons spread
across four layers:

- 1.
Input layer: The single input neuron $n_{in}$ (bias 0).
- 2.
Hidden vertex layer: The vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$
(all with bias 0).
- 3.
Hidden edge layer: The edge neurons $ne_{1},ne_{2},\ldots ne_{|E|}$
(all with bias $-1$).
- 4.
Output layer: The single output neuron $n_{out}$ (bias $-(k(k-1)/2-1)$).

The non-zero weight connections between adjacent layers are as follows:

- •
The input neuron $n_{in}$ is connected to each vertex neuron with weight 1.
- •
Each vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected to each edge neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge neuron $ne_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(1)$, $d=4$, $w=k(k-1)/2$, and $\#n=k(k-1)/2+k+2$.
Observe that this instance of MLSC can be created in time polynomial in the size of the
given instance of Clique. Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nv_{1}(1),nv_{2}(1),\ldots nv_{|V|}(1)$ |
| 3 | $ne_{1}(1),ne_{2}(1),\ldots ne_{|E|}(1)$ |
| 4 | $n_{out}(|E|-(k(k-1)/2-1))$ |

Note that it is the stepped output of $n_{out}$ in timestep 4 that yields output 1.

We now need to show the correctness of this reduction by proving that the answer
for the given instance of Clique is “Yes” if and only if the answer for the
constructed instance of MLSC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$ be a clique
in $G$ of size $k$. Consider the subcircuit $C$ based on
neurons $n_{in}$, $n_{out}$, $\{nv^{\prime}~{}|~{}v^{\prime}\in V^{\prime}\}$, and $\{ne^{\prime}~{}|~{}e^{\prime}=(x,y)~{}{\rm and}~{}vx,vy\in V^{\prime}\}$. Observe that in this subcircuit, $cd_{r}=d=4$, $cw_{r}=r=k(k-1)/2$, and $\#n_{tot,r}=\#n=k(k-1)/2+k+2$.
The output behaviour of the neurons in $C$ from the
presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nv^{\prime}_{1}(1),nv^{\prime}_{2}(1),\ldots nv^{\prime}_{|V^{\prime}|}(1)$ |
| 3 | $ne^{\prime}_{1}(1),ne^{\prime}_{2}(1),\ldots ne^{\prime}_{k(k-1)/2}(1)$ |
| 4 | $n_{out}(1)$ |

The output of $n_{out}$ in timestep 4 is stepped to 1, which means that $C$
is behaviorally equivalent to $M$ on $I$.

: Let $C$ be a subcircuit of $M$ that is behaviorally equivalent to $M$
on input $I$ and has $\#n_{tot,r}\leq\#n=k(k-1)/2+k+2$ neurons. As neurons
in all four layers in $M$ must be present in $C$ to produce the required output,
$cd_{r}=d=cd_{g}$ and both $n_{in}$ and $n_{out}$ are in $C$. In order for $n_{out}$
to produce a non-zero output, there must be at least $k(k-1)/2$ edge neurons in
$C$, each of which must be activated by the inclusion of the vertex neurons
corresponding to both of their endpoint vertices. This requires the inclusion of at
least $k$ vertex neurons in $C$, as a set $V^{\prime\prime}$ of vertices in graph can have at
most $|V^{\prime\prime}|(|V^{\prime\prime}|-1)/2$ distinct edges between them (with this maximum occurring
if all pairs of vertices in $V^{\prime\prime}$ have an edge between them). As $\#n_{tot,r}\leq k(k-1)/2+k+2$, all of the above implies that there must be exactly
$k(k-1)/2$ edge neurons and exactly $k$ vertex neurons in $C$ and the vertices
in $G$ corresponding to these vertex neurons must form a clique of size $k$ in $G$.

As Clique is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MLSC is also
$NP$-hard. The result follows from the definition of $NP$-hardness.
∎

###### Theorem 2 .

If $\langle cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_
{in,r},\#n_{out,r},\#n_{tot,r},$ $B_{\max,r},W_{\max,r}\rangle$-MLSC is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MLSC constructed in the reduction in the proof of
Theorem 1, $cd_{g}=cd_{r}=4$, $\#n_{in,g}=\#n_{in,r}=\#n_{out,r}=\#n_{out,r}=W_{\max,g}=W_{\max,r}=1$, and $B_{\max,g},B_{\max,r},\#n_{tot,r},$
and $cw_{r}$ are all functions of $k$ in the given instance of Clique. The result
then follows from the fact that $\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 3 .

$\langle\#n_{tot,g}\rangle$-MLSC is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates each possible subcircuit of $M$ and checks if that
subcircuit is behaviorally equivalent to $M$ on input $I$. If such a subcircuit is
found, return “Yes”; otherwise, return “No”. As each such subcircuit can be
run on $I$ in time polynomial in the size of the given instance of MLSC and the total
number of subcircuits that need to be checked is at most $2^{\#n_{tot,g}}$, the above is
a fixed-parameter tractable algorithm for MLSC relative to parameter-set $\{\#n_{tot,g}\}$.
∎

###### Theorem 4 .

$\langle cd_{g},cw_{g}\rangle$-MLSC is fixed-parameter tractable.

###### Proof.

Follows from the observation that $\#n_{tot,g}\leq cd_{g}\times cw_{g}$ and the
algorithm in the proof of Theorem 3.
∎

Though we have already proved the polynomial-time intractability of MLSC in Theorem
1, the reduction in the proof of the following theorem will be useful in
proving a certain type of polynomial-time inapproximability for MLSC (see Figure 2).

###### Theorem 5 .

If MLSC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from VC to MLSC.
Given an instance $\langle G=(V,E),k\rangle$ of VC, construct the following
instance $\langle M,I,d,w,\#n\rangle$ of MLSC:
Let $M$ be an MLP based on $\#n_{tot,g}=|V|+2|E|+2$ neurons spread
across five layers:

- 1.
Input layer: The single input neuron $n_{in}$ (bias 0).
- 2.
Hidden vertex layer: The vertex neurons $nvN_{1},nvN_{2},\ldots nvN_{|V|}$, all of which are NOT ReLU gates.
- 3.
Hidden edge layer I: The edge AND neurons $neA_{1},neA_{2},\ldots neA_{|E|}$, all of which are 2-way AND ReLU gates.
- 4.
Hidden edge layer II: The edge NOT neurons $neN_{1},neN_{2},\ldots neN_{|E|}$, all of which are NOT ReLU gates.
- 5.
Output layer: The single output neuron $n_{out}$, which is an
$|E|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
The input neuron $n_{in}$ is connected to each vertex NOT neuron with weight 1.
- •
Each vertex NOT neuron $nvN_{i}$, $1\leq i\leq|V|$, is connected to each edge AND neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge AND neuron $neA_{i}$, $1\leq i\leq|E|$, is connected to its corresponding edge NOT neuron $neN_{i}$ with weight 1.
- •
Each edge NOT neuron $neN_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(1)$, $d=5$, $w=|E|$, and $\#n=2|E|+k+2$.
Observe that this instance of MLSC can be created in time polynomial in the size of the
given instance of VC, Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nvN_{1}(0),nvN_{2}(0),\ldots nvN_{|V|}(0)$ |
| 3 | $neA_{1}(0),neA_{2}(0),\ldots neA_{|E|}(0)$ |
| 4 | $neN_{1}(1),neN_{2}(1),\ldots neN_{|E|}(1)$ |
| 5 | $n_{out}(1)$ |

We now need to show the correctness of this reduction by proving that the answer
for the given instance of VC is “Yes” if and only if the answer for the
constructed instance of MLSC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$ be a vertex cover
in $G$ of size $k$. Consider the subcircuit $C$ based on
neurons $n_{in}$, $n_{out}$, $\{nv^{\prime}N~{}|~{}v^{\prime}\in V^{\prime}\}$,
$\{neA_{1},neA_{2},\ldots,neA_{|E|}\}$, and
$\{neN_{1},neN_{2},\ldots,neN_{|E|}\}$.
Observe that in this subcircuit,
$cd_{r}=d=5$, $cw_{r}=w=|E|$, and $\#n_{tot,r}=\#n=2|E|+k+2$.
The output behaviour of the neurons in $C$ from the
presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nvN^{\prime}_{1}(0),nvN^{\prime}_{2}(0),\ldots nvN^{\prime}_{|V^{\prime}|}(0)$ |
| 3 | $neA_{1}(0),neA_{2}(0),\ldots neA_{|E|}(0)$ |
| 4 | $neN_{1}(1),neN_{2}(1),\ldots neN_{|E|}(1)$ |
| 5 | $n_{out}(1)$ |

This means that $C$ is behaviorally equivalent to $M$ on $I$.

: Let $C$ be a subcircuit of $M$ that is behaviorally equivalent to $M$
on input $I$ and has $\#n_{tot,r}\leq\#n=2|E|+k+2$ neurons. As neurons in
all five layers in $M$ must be present in $C$ to produce the required output,
$cd_{r}=cd_{g}$ and both $n_{in}$ and $n_{out}$ are in $C$. In order for $n_{out}$
to produce a non-zero output, there must be at least $|E|$ edge NOT neurons and $|E|$ AND neurons in $C$, and each
of the latter must be connected to at least one of the vertex NOT neurons corresponding to
their endpoint vertices. As $\#n_{tot,r}\leq 2|E|+k+2$, there must be
exactly $|E|$ edge NOT neurons, $|E|$ edge AND neurons, and $k$ vertex NOT neurons in $C$ and the vertices in $G$
corresponding to these vertex NOT neurons must form a vertex cover of size $k$ in $G$.

As VC is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MLSC is also
$NP$-hard. The result follows from the definition of $NP$-hardness.
∎

Figure: Figure 2: This figure summarizes the reduction from Vertex Cover
Refer to caption: extracted/5918954/figures/reduction-vertex_cover.png

We now define our two notions of polynomial-time approximation.
For a minimization problem $\Pi$, let $OPT_{\Pi}(I)$ be an optimal solution
for $\Pi$, $A_{\Pi}(I)$ be a solution for$\Pi$ returned by an algorithm $A$,
and $m(OPT_{\Pi}(I))$ and $m(A_{\Pi}(I))$ be the values of these solutions.
Consider the following alternative to approximation algorithms that give
solutions that are within an additive factor of optimal.

###### Definition 10 .

(Ausiello et al., , Definition 3.5)
Given a minimization problem $\Pi$, an algorithm $A$ is a (multiplicative)
$\epsilon$-approximation algorithm for $\Pi$ if for each instance $I$ of $\Pi$,
$m(A_{\Pi}(I))-m(OPT_{\Pi}(I))\leq\epsilon\times m(OPT_{\Pi}(I))$.

It would be ideal if one could obtain approximate solutions for a problem
$\Pi$ that are arbitrarily close to optimal if one is willing to allow
extra algorithm runtime. This is encoded in the following entity.

###### Definition 11 .

(Adapted from Definition 3.10 in Ausiello et al. )
Given a minimization problem $\Pi$, a polynomial-time approximation scheme
(PTAS) for $\Pi$ is a set $\cal{A}$ of algorithms such that for each integer
$k>0$, there is a $\frac{1}{k}$-approximation algorithm $A^{k}_{\Pi}\in\cal{A}$
that runs in time polynomial in $|I|$.

The question of whether or not a problem has a PTAS can be answered using
the following type of approximation-preserving reducibility.

###### Definition 12 .

(Papadimitriou & Yannakakis, , page 427)
Given two minimization problems $\Pi$ and $\Pi^{\prime}$, $\Pi$ L-reduces to $\Pi^{\prime}$,
i.e., $\Pi\leq_{L}\Pi^{\prime}$ if there are polynomial-time algorithms $f$ and $g$
and constants $\alpha,\beta>0$ such that for each instance $I$ of $\Pi$

Algorithm $f$ produces an instance $I^{\prime}$ of $\Pi^{\prime}$ such that
$m(OPT_{\Pi^{\prime}}(I^{\prime}))\leq\alpha\times m(OPT_{\Pi}(I))$; and

For any solution for $I^{\prime}$ with value $v^{\prime}$, algorithm $g$ produces
a solution for $I$ of value $v$ such that $v-m(OPT_{\Pi}(I))\leq\beta\times(v^{\prime}-m(OPT_{\Pi^{\prime}}(I^{\prime})))$.

###### Lemma 3 .

(Arora et al., , Theorem 1.2.2)
If an optimization problem that is $MAX~{}SNP$-hard under L-reductions has
a PTAS then $P=NP$.

###### Theorem 6 .

If MLSC has a PTAS then $P=NP$.

###### Proof.

We prove that the reduction from VC to MLSC in the proof of Theorem 5 is
also an L-reduction from VCB to MLSC as follows:

- •
Observe that $m(OPT_{VC_{B}}(I))\geq|E|/B$ (the best case in which $G$ is a
collection of $B$-star subgraphs such that each edge is uniquely covered by
the central vertex of its associated star) and $m(OPT_{MLSC}(I^{\prime}))\leq 2|E|+2|E|+2=4|E|+2$ (the worst case in which the vertex neurons
corresponding to the two endpoints of every edge in $G$ are selected).
This gives us
$\displaystyle m(OPT_{MLSC}(I^{\prime}))$
$\displaystyle\leq$
$\displaystyle 4Bm(OPT_{VC_{B}}(I))+2$
$\displaystyle\leq$
$\displaystyle 4Bm(OPT_{VC_{B}}(I))+2Bm(OPT_{VC_{B}}(I))$
$\displaystyle\leq$
$\displaystyle 6Bm(OPT_{VC_{B}}(I))$
which satisfies condition L1 with $\alpha=6B$.
- •
Observe that any solution $S^{\prime}$ for for the constructed instance $I^{\prime}$ of MLSC
of value $k+2|E|+2$ implies a solution $S$ for the given instance $I$ of VCB
of size $k$, i.e., the vertices in $V$ corresponding to the selected vertex neurons
in $S$. Hence, it is the case that $m(S)-m(OPT_{VC_{B}}(I))=m(S^{\prime})-m(OPT_{MLSC}(I^{\prime}))$, which satisfies condition L2 with $\beta=1$.

As VCB is $MAX~{}SNP$-hard under L-reductions (Papadimitriou & Yannakakis, , Theorem 2(d)), the L-reduction
above proves that MLSC is also $MAX~{}SNP$-hard under L-reductions. The result follows from
Lemma 3.
∎

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

###### Theorem 4 .

###### Proof.

###### Theorem 5 .

###### Proof.

###### Definition 10 .

###### Definition 11 .

###### Definition 12 .

###### Lemma 3 .

###### Theorem 6 .

###### Proof.

#### B.2 Results for MGSC

###### Theorem 7 .

If MGSC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from Clique to MGSC. Given an instance $\langle G=(V,E),k\rangle$ of Clique, construct an instance $\langle M,d,w,\#n\rangle$ of MGSC
as in the reduction in the proof of Theorem 1, omitting input vector $I$.
Observe that this instance of MGSC can be created in time polynomial in the size of the
given instance of Clique. As $\#n_{in,g}=1$, there are only two possible Boolean
input vectors, $(0)$ and $(1)$. Given input vector $(1)$, as MLP $M$ in this reduction is
the same as $M$ in the proof of Theorem 1, the output in
timestep 4 is once again 1; moreover, given input vector $(0)$, no vertex or edge neurons
can have output 1 and hence the output in timestep 4 is 0.

We now need to show the correctness of this reduction by proving that the answer
for the given instance of Clique is “Yes” if and only if the answer for the
constructed instance of MGSC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$ be a clique
in $G$ of size $k$. Consider the subcircuit $C$ based on
neurons $n_{in}$, $n_{out}$, $\{nv^{\prime}~{}|~{}v^{\prime}\in V^{\prime}\}$, and $\{ne^{\prime}~{}|~{}e^{\prime}=(x,y)~{}{\rm and}~{}vx,vy\in V^{\prime}\}$. Observe that in this subcircuit,
$cd_{r}=4$, $cw_{r}=k(k-1)/2$, and $\#n_{tot,r}=k(k-1)/2+k+2$.
Given input $(1)$, the output behaviour of the neurons in $C$ from the
presentation of input until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nv^{\prime}_{1}(1),nv^{\prime}_{2}(1),\ldots nv^{\prime}_{|V^{\prime}|}(1)$ |
| 3 | $ne^{\prime}_{1}(1),ne^{\prime}_{2}(1),\ldots ne^{\prime}_{k(k-1)/2}(1)$ |
| 4 | $n_{out}(1)$ |

Moreover, given input $(0)$, no vertex or edge neurons in $C$ can have output 1
and the output of $C$ at timestep 4 is 0. This means that $C$ is behaviorally
equivalent to $M$ on all possible Boolean input vectors

: Let $C$ be a subcircuit of $M$ that is behaviorally equivalent to $M$
on all possible Boolean input vectors and has $\#n_{tot,r}\leq\#n=k(k-1)/2+k+2$ neurons. Consider the case of input vector $(1)$. This vector must cause $C$ to
generate output 1 at timestep 4 as $C$ is behaviorally equivalent to $M$ on all
Boolean input vectors. As neurons in all four layers in $M$ must be present in $C$
to produce the required output, $cd_{r}=cd_{g}$ and both $n_{in}$ and $n_{out}$ are in
$C$. In order for $n_{out}$ to produce a non-zero output, there must be at least
$k(k-1)/2$ edge neurons in $C$, each of which must be activated by the inclusion
of the vertex neurons corresponding to both of their endpoint vertices. This
requires the inclusion of at least $k$ vertex neurons in $C$, as a set $V^{\prime\prime}$ of
vertices in graph can have at most $|V^{\prime\prime}|(|V^{\prime\prime}|-1)/2$ distinct edges between them
(with this maximum occurring if all pairs of vertices in $V^{\prime\prime}$ have an edge between
them). As $\#n_{tot,r}\leq k(k-1)/2+k+2$, all of the above implies that there
must be exactly $k(k-1)/2$ edge neurons and exactly $k$ vertex neurons in $C$ and
the vertices in $G$ corresponding to these vertex neurons must form a clique of
size $k$ in $G$.

As Clique is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MGSC is also
$NP$-hard. The result follows from the definition of $NP$-hardness.
∎

###### Theorem 8 .

If $\langle cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_
{in,r},\#n_{out,r},\#n_{tot,r},$ $B_{\max,r},W_{\max,r}\rangle$-MGSC is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MGSC constructed in the reduction in the proof of
Theorem 7, $cd_{g}=cd_{r}=4$, $\#n_{in,g}=\#n_{in,r}=\#n_{out,r}=\#n_{out,r}=W_{\max,g}=W_{\max,r}=1$, and $B_{\max,g},B_{\max,r},\#n_{tot,r},$
and $cw_{r}$ are all functions of $k$ in the given instance of Clique. The result
then follows from the fact that $\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 9 .

$\langle\#n_{tot,g}\rangle$-MGSC is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates each possible subcircuit of $M$ and checks if that
subcircuit is behaviorally equivalent to $M$ on all possible Boolean input vectors of
length $\#n_{in,g}$. If such a subcircuit is found, return “Yes”; otherwise, return
“No”. There are $2^{\#n_{in,g}}$ possible Boolean input vectors and the total number of
subcircuits that need to be checked is at most $2^{\#n_{tot,g}}$. As $\#n_{in,g}\leq\#n_{tot,g}$ and each such subcircuit can be run on an input vector in time polynomial in
the size of the given instance of MGSC, the above is a fixed-parameter tractable algorithm
for MGSC relative to parameter-set $\{\#n_{tot,g}\}$.
∎

###### Theorem 10 .

$\langle cd_{g},cw_{g}\rangle$-MGSC is fixed-parameter tractable.

###### Proof.

Follows from the observation that $\#n_{tot,g}\leq cd_{g}\times cw_{g}$ and the
algorithm in the proof of Theorem 9.
∎

Let us now consider the PTAS-approximability of MGSC. A first thought
would be to -reuse the reduction in the proof of Theorem
5 if the given MLP $M$ and VC subcircuit are
behaviorally equivalent under both possible input vectors, $(1)$ and $(0)$.
We already know the former is true. With respect to the latter, observe
that the output behaviour of the neurons in $M$ from the presentation of
input $(0)$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(0)$ |
| 2 | $nvN_{1}(1),nvN_{2}(1),\ldots nvN_{|V|}(1)$ |
| 3 | $neA_{1}(1),neA_{2}(1),\ldots neA_{|E|}(1)$ |
| 4 | $neN_{1}(0),neN_{2}(0),\ldots neN_{|E|}(0)$ |
| 5 | $n_{out}(0)$ |

However, in the VC subcircuit, we are no longer guaranteed that both
endpoint vertex NOT neurons for any edge AND neuron (let alone the endpoint
vertex NOT neurons for all edge AND neurons) will be the vertex cover
encoded in the subcircuit. This means that all
edge AND neurons could potentially output 0, which would cause
$M$ to output 1 at timestep 4.

This problem can be fixed if we can modify the given VC graph $G$ to create
a graph $G^{\prime}$ such that

- 1.
we can guarantee that both endpoint vertex NOT neurons for at least
one edge AND neuron are present in a VC subcircuit $C$ constructed
for $G^{\prime}$ (which would make at least one edge AND neuron output 1
and cause $C$ to output 0 at timestep 4); and
- 2.
we can easily extract a graph vertex cover of size at most $k$ for
$G$ from any vertex cover of a particular size for $G^{\prime}$.

Figure: Figure 3: The $c$-way Bowtie Graph $B_{c}$.
Refer to caption: x1.png

To do this, we shall use the $c$-way bowtie graph $B_{c}$. For $c>0$,
$B_{c}$ consists of a central edge $e_{B}$ between vertices $v_{B1}$
and $v_{B2}$ such that $c$ edges radiate outwards from $v_{B1}$ and
$v_{B2}$ to the $c$-sized vertex-sets $V_{B1}=\{v_{B1,1},v_{B1,2},\ldots,v_{B1,c}\}$ and $V_{B2}=\{v_{B2,1},v_{B2,2},\ldots,v_{B2,c}\}$, respectively
(see Figure 3). Note that such a graph has $2c+2$ vertices
and $2c+1$ edges. Given a graph $G=(V,E)$ with no isolated vertices
such that $|V|\leq 2|E|$ (with the minimum occurring in a graph consisting
of $|E|$ endpoint-disjoint edges), let $Bow(G)=B_{4|E|}\cup G$. This
graph has the following useful property.

###### Lemma 4 .

Given a graph $G=(V,E)$ and a positive integer $k\leq|V|$, if $Bow(G)$
has a vertex cover $V^{\prime}$ of size at most $k+2$ then (1) $\{v_{B1},v_{B2}\}\in V^{\prime}$ and (2) $G$ has a vertex cover of size at most $k$.

###### Proof.

Let us prove the two consequent clauses as follows:

- 1.
Any vertex cover $V^{\prime}$ of $Bow(G)$ must cover all the edges in both
$B_{4|E|}$ and $G$. Suppose $\{v_{B1},v_{B2}\}\not\in V^{\prime}$. In
order to cover the edges in $B_{4|E|}$, all $8|E|$ vertices in
$V_{B1}\cup V_{B2}$ must be in $V^{\prime}$. This is however impossible
as $|V^{\prime}|\leq k+2\leq|V|+2\leq 2|E|+2\leq 4|E<8|E|$.
Similarly, suppose only one of $v_{B1}$ and $v_{B2}$ is in $V^{\prime}$;
let us assume it is $v_{B1}$. In that case, all vertices in $V_{B2}$
must be in $V^{\prime}$. However, this too is impossible as $|V^{\prime}-\{v_{B1}\}|\leq k+1\leq|V|+1\leq 2|E|+1\leq 3|E|<4|E|=|V_{B2}|$. Hence, both $v_{B1}$ and $v_{B2}$ must be in $V^{\prime}$.
- 2.
Given (1), $k^{\prime}\leq k$ vertices remain in $V^{\prime}$ to cover $G$. All $k^{\prime}$
of these vertices need not be in $G$, e.g., some may be scattered
over $V_{B1}$ and $V_{B2}$. That being said, it is still the case
that $G$ must have a vertex cover of size at most $k$.

This concludes the proof.
∎

###### Theorem 11 .

If MGSC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from VC to MGSC. Given an instance $\langle G=(V,E),k\rangle$ of VC, construct the following instance $\langle M,d,w,\#n\rangle$ of MGSC based on $G^{\prime}=(V^{\prime},E^{\prime})=Bow(G)$: Let $M$ be an MLP based
on $\#n_{tot,g}=|V^{\prime}|+2|E^{\prime}|+2$ neurons spread
across five layers:

- 1.
Input layer: The single input neuron $n_{in}$ (bias 0).
- 2.
Hidden vertex layer: The vertex neurons $nvN_{1},nvN_{2},\ldots nvN_{|V^{\prime}|}$, all of which are NOT ReLU gates.
- 3.
Hidden edge layer I: The edge AND neurons $neA_{1},neA_{2},\ldots neA_{|E^{\prime}|}$, all of which are 2-way AND ReLU gates.
- 4.
Hidden edge layer II: The edge NOT neurons $neN_{1},neN_{2},\ldots neN_{|E^{\prime}|}$, all of which are NOT ReLU gates.
- 5.
Output layer: The single output neuron $n_{out}$, which is an
$|E^{\prime}|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
The input neuron $n_{in}$ is connected to each vertex NOT neuron with weight 1.
- •
Each vertex NOT neuron $nvN_{i}$, $1\leq i\leq|V^{\prime}|$, is connected to each edge AND neuron
whose corresponding edge has an endpoint $v^{\prime}_{i}$ with weight 1.
- •
Each edge AND neuron $neA_{i}$, $1\leq i\leq|E^{\prime}|$, is connected to its corresponding edge NOT neuron $neN_{i}$ with weight 1.
- •
Each edge NOT neuron $neN_{i}$, $1\leq i\leq|E^{\prime}|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $d=5$, $w=|E^{\prime}|$, and $\#n=2|E^{\prime}|+(k+2)+2=2|E^{\prime}|=k+4$. Observe that this instance of MGSC can be created in time
polynomial in the size of the given instance of VC, the output behaviour of
the neurons in $M$ from the presentation of input $(1)$ until the output is
generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nvN_{1}(0),nvN_{2}(0),\ldots nvN_{|V^{\prime}|}(0)$ |
| 3 | $neA_{1}(0),neA_{2}(0),\ldots neA_{|E^{\prime}|}(0)$ |
| 4 | $neN_{1}(1),neN_{2}(1),\ldots neN_{|E^{\prime}|}(1)$ |
| 5 | $n_{out}(1)$ |

and the output behaviour of the neurons in $M$ from the presentation of
input $(0)$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(0)$ |
| 2 | $nvN_{1}(1),nvN_{2}(1),\ldots nvN_{|V^{\prime}|}(1)$ |
| 3 | $neA_{1}(1),neA_{2}(1),\ldots neA_{|E^{\prime}|}(1)$ |
| 4 | $neN_{1}(0),neN_{2}(0),\ldots neN_{|E^{\prime}|}(0)$ |
| 5 | $n_{out}(0)$ |

We now need to show the correctness of this reduction by proving that the
answer for the given instance of VC is “Yes” if and only if the answer
for the constructed instance of MGSC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime\prime}=\{v^{\prime\prime}_{1},v^{\prime\prime}_{2},\ldots,v^{\prime
\prime}_{k}\}\subseteq V$ be a vertex cover in $G$ of size $k$. Consider the subcircuit $C$
based on neurons $n_{in}$, $n_{out}$, $\{nv^{\prime\prime}N~{}|~{}v^{\prime\prime}\in V^{\prime\prime}\}\cup\{nv_{B1}
N,nv_{B2}B\}$, $\{neA_{1},neA_{2},\ldots,neA_{|E^{\prime}|}\}$, and $\{neN_{1},neN_{2},\ldots,neN_{|E^{\prime}|}\}$. Observe
that in this subcircuit, $cd_{r}=d=5$, $cw_{r}=w=|E^{\prime}|$, and
$\#n_{tot,r}=\#n=2|E^{\prime}|+k+4$. The output behaviour of the neurons
in $C$ from the presentation of input $(1)$ until the output is
generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | All vertex NOT neurons (0) |
| 3 | $neA_{1}(0),neA_{2}(0),\ldots neA_{|E^{\prime}|}(0)$ |
| 4 | $neN_{1}(1),neN_{2}(1),\ldots neN_{|E^{\prime}|}(1)$ |
| 5 | $n_{out}(1)$ |

Moreover, the output behaviour of the neurons in $C$ from the
presentation of input $(0)$ until the output is generated is as
follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(0)$ |
| 2 | All vertex NOT neurons (1) |
| 3 | At least one edge AND neuron has output 1, e.g., $ne_{B}A$ |
| 4 | At least one edge NOT neuron has output 0, e.g., $ne_{B}N$ |
| 5 | $n_{out}(0)$ |

This means that $C$ is behaviorally equivalent to $M$ on all
possible Boolean input vectors.

: Let $C$ be a subcircuit of $M$ that is behaviorally
equivalent to $M$ on all possible Boolean input vectors and has
$\#n_{tot,r}\leq\#n=2|E^{\prime}|+k+4$ neurons. As neurons in
all five layers in $M$ must be present in $C$ to produce the
required output, $cd_{r}=cd_{g}$ and both $n_{in}$ and $n_{out}$ are
in $C$. In order for $n_{out}$ to produce a non-zero output, there
must be at least $|E^{\prime}|$ edge NOT neurons and $|E^{\prime}|$ AND neurons in
$C$, and each of the latter must be connected to at least one of the
vertex NOT neurons corresponding to their endpoint vertices. As
$\#n_{tot,r}\leq 2|E^{\prime}|+k+4$, there must be exactly $|E|$ edge
NOT neurons, $|E^{\prime}|$ edge AND neurons, and $k+2$ vertex NOT neurons
in $C$ and the vertices in $G^{\prime}$ corresponding to these vertex NOT
neurons must form a vertex cover $V^{\prime\prime}$ of size $k+2$ in $G^{\prime}$.
However, as $G^{\prime}=Bow(G)$, Lemma 4 implies not only
that $\{nv_{B1}N,nv_{B2}N\}\in V^{\prime\prime}$ but that $G$ has a vertex
cover of size at most $k$.

As VC is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MGSC is also
$NP$-hard. The result follows from the definition of $NP$-hardness.
∎

###### Theorem 12 .

If MGSC has a PTAS then $P=NP$.

###### Proof.

We prove that the reduction from VC to MLSC in the proof of Theorem
11 is also an L-reduction from VCB to MGSC as follows:

- •
Observe that $m(OPT_{VC_{B}}(I))\geq|E|/B$ (the best case in which
$G$ is a collection of $B$-star subgraphs such that each edge is
uniquely covered by the central vertex of its associated star) and
$m(OPT_{MGSC}(I^{\prime}))\leq 2|E^{\prime}|+2|E^{\prime}|+2=4|E^{\prime}|+2$ (the worst
case in which the vertex neurons corresponding to the two endpoints
of every edge in $G$ are selected). As $|E^{\prime}|=9|E|+1$, this
gives us
$\displaystyle m(OPT_{MLSC}(I^{\prime}))$
$\displaystyle\leq$
$\displaystyle 36|E|+4+2$
$\displaystyle\leq$
$\displaystyle 36Bm(OPT_{VC_{B}}(I))+6$
$\displaystyle\leq$
$\displaystyle 36Bm(OPT_{VC_{B}}(I))+6Bm(OPT_{VC_{B}}(I))$
$\displaystyle\leq$
$\displaystyle 42Bm(OPT_{VC_{B}}(I))$
which satisfies condition L1 with $\alpha=42B$.
- •
Observe that any solution $S^{\prime}$ for for the constructed instance $I^{\prime}$
of MGSC of value $k+2|E^{\prime}|+4$ implies a solution $S$ for the
given instance $I$ of VCB of size $k$ in $S$. Hence, it is the
case that $m(S)-m(OPT_{VC_{B}}(I))=m(S^{\prime})-m(OPT_{MGSC}(I^{\prime}))$,
which satisfies condition L2 with $\beta=1$.

As VCB is $MAX~{}SNP$-hard under L-reductions (Papadimitriou & Yannakakis, , Theorem 2(d)),
the L-reduction above proves that MGSC is also $MAX~{}SNP$-hard under
L-reductions. The result follows from Lemma 3.
∎

###### Theorem 7 .

###### Proof.

###### Theorem 8 .

###### Proof.

###### Theorem 9 .

###### Proof.

###### Theorem 10 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Theorem 11 .

###### Proof.

###### Theorem 12 .

###### Proof.

### Appendix C Sufficient Circuit Search and Counting Problems

###### Definition 13 .

An entity $x$ with property $P$ is minimal if there is no non-empty
subset of elements in $x$ that can be deleted to create an entity $x^{\prime}$ with
property $P$.

We shall assume here that all subcircuits are non-trivial, i.e., the
subcircuit is of size $<|M|$.

Consider the following search problem templates:

Name local sufficient circuit (AccLSC)
Input: A multi-layer perceptron $M$ of depth $cd_{g}$ with $\#n_{tot,g}$ neurons
and maximum layer width $cw_{g}$, connection-value matrices $W_{1},W_{2},\ldots,W_{cd_{g}}$, neuron bias vector $B$, a Boolean input vector $I$ of length
$\#n_{g,in}$, integers $d$ and $w$ such that $1\leq d\leq cd_{g}$ and $1\leq w\leq cw_{g}$ PrmAdd.
Output: A CType subcircuit $C$ of $M$ of depth $cd_{r}\leq d$
with maximum layer width $cw_{r}\leq w$ that $C(I)=M(I)$,
if such a subcircuit exists, and special symbol $\bot$
otherwise.

Name global sufficient circuit (AccGSC)
Input: A multi-layer perceptron $M$ of depth $cd_{g}$ with $\#n_{tot,g}$ neurons
and maximum layer width $cw_{g}$, connection-value matrices $W_{1},W_{2},\ldots,W_{cd_{g}}$, neuron bias vector $B$, integers $d$ and $w$
such that $1\leq d\leq cd_{g}$ and $1\leq w\leq cw_{g}$ PrmAdd.
Output: A CType subcircuit $C$ of $M$ of depth $cd_{r}\leq d$ with
maximum layer width $cw_{r}\leq w$ such that $C(I)=M(I)$
for every possible Boolean input vector $I$ of
length $\#_{in,g}$, if such a subcircuit exists, and special symbol $\bot$ otherwise..

Name local necessary circuit (AccLNC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$ PrmAdd.
Output: A CType subcircuit $C$ of $M$
such that $C\cap C^{\prime}\neq\emptyset$ for every
sufficient circuit $C^{\prime}$ of $M$ relative to $I$, if such a s
subcircuit exists, and special symbol $\bot$ otherwise.

Name global necessary circuit (AccGNC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector
$B$ PrmAdd.
Output: A CType subcircuit $C$ of $M$
such that for for every possible Boolean input
vector $I$ of length $\#n_{in}$, $C\cap C^{\prime}\neq\emptyset$
for every sufficient circuit $C^{\prime}$ of $M$ relative to $I$,
if such a subcircuit exists, and special symbol $\bot$
otherwise.

Name local circuit ablation (AccLCA)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$ PrmAdd.
Output: A CType subcircuit $C$ of $M$
such that $(M/C)(I)\neq M(I)$, if such a subcircuit exists,
and special symbol $\bot$ otherwise.

Name global circuit ablation (AccGCA)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias
vector $B$ PrmAdd.
Output: A CType subcircuit $C$ of $M$ such that $(M/C)(I)\neq M(I)$ every possible Boolean input vector $I$ of length
$\#n_{in}$, if such a subcircuit exists, and special
symbol $\bot$ otherwise.

Each these templates can be filled out to create six search problem
variants as follows:

- 1.
Exact-size Problem:
•
Name $=$ “Exact”
•
Acc $=$ “Ex”
•
PrmAdd $=$ “, and a positive integer $k<|M|$”
•
CType $=$ “size-$k$”
- 2.
Bounded-size Problem:
•
Name $=$ “Bounded”
•
Acc $=$ “B”
•
PrmAdd $=$ “, and a positive integer $k<|M|$”
•
CType $=$ “size-$\leq k$”
- 3.
Minimal Problem:
•
Name $=$ “Minimal”
•
Acc $=$ “Mnl”
•
PrmAdd $=$ “”
•
CType $=$ “minimal”
- 4.
Minimal Exact-size Problem:
•
Name $=$ “Minimal exact”
•
Acc $=$ “MnlEx”
•
PrmAdd $=$ “, and a positive integer $k<|M|$”
•
CType $=$ “minimal size-$k$”
- 5.
Minimal Bounded-size Problem:
•
Name $=$ “Minimal bounded”
•
Acc $=$ “MnlB”
•
PrmAdd $=$ “, and a positive integer $k<|M|$”
•
CType $=$ “minimal size-$\leq k$”
- 6.
Minimum Problem:
•
Name $=$ “Minimum”
•
Acc $=$ “Min”
•
PrmAdd $=$ “”
•
CType $=$ “minimum”

We will use previous results for the following problems
to prove our results for the problems above.

Exact clique (ExClique)
Input: An undirected graph $G=(V,E)$ and a positive integer
$k\leq|V|$.
Output: A $k$-size vertex subset $V^{\prime}$ of $G$ that is a clique of
size $k$ in $G$, if such a $V^{\prime}$ exists, and special
symbol $\bot$ otherwise.

Exact vertex cover (ExVC)
Input: An undirected graph $G=(V,E)$ and a positive integer
$k\leq|V|$.
Output: A $k$-size vertex subset $V^{\prime}$ of $G$ that is a vertex
cover of size $k$ in $G$, if such a $V^{\prime}$ exists, and special
symbol $\bot$ otherwise.

Minimal vertex cover (MnlVC) (Valiant, , Problem 4)
Input: An undirected graph $G=(V,E)$.
Output: A minimal subset $V^{\prime}$ of the vertices in $G$ that is a
vertex cover of $G$.

Given any search problem X above, let #X be the problem that
returns the number of solution outputs. To assess the complexity of
these counting problems, we will use the following definitions in
Garey & Johnson , Section 7.3, adapted from those originally given in
Valiant .

###### Definition 14 .

(Garey & Johnson, , p. 168)
A counting problem #$\Pi$ is in #P if there is a nondeterministic
algorithm such that for each input $I$ of $\Pi$, (1) the number of ‘distinct
“guesses” that lead to acceptance of $I$ exactly equals the number
solutions of $\Pi$ for input $I$ and (2) the length of the longest accepting
computation is bounded by a polynomial in $|I|$.

#P contains very hard problems, as it is known every class in the
Polynomial Hierarchy (which include $P$ and $NP$ as its lowest members)
Turing reduces to #P, i.e., $PH\subseteq P^{\#P}$ (Toda, ). We
use the following type of reduction to isolate problems that are
the hardest (#P-complete) and at least as hard as the hardest
(#P-hard) in #P.

###### Definition 15 .

(Garey & Johnson, , p. 168-169)
Given two search problems $\Pi$ and $\Pi^{\prime}$, a (polynomial time)
parsimonious reduction from $\Pi$ to $\Pi^{\prime}$ is a function $f:I_{\Pi}\rightarrow I_{\Pi^{\prime}}$ that can be computed in polynomial time such that
for every $I\in{\Pi}$, the number of solutions of $\Pi$ for input $I$
is exactly equal to the number of $\Pi^{\prime}$ for input $f(I)$.

We will also derive parameterized counting results using the framework
given in Flum & Grohe , Chapter 14. The definition of class #$W[1]$
(Flum & Grohe, , Definition 14.11) is rather intricate and need not concern us
here. We will use the following type of reduction to isolate problems that
are at least as hard as the hardest (#$W[1]$-hard) in #$W[1]$.

###### Definition 16 .

(Adapted from Flum & Grohe , Definition 14.10.a)
Given two parameterized search problems $\langle k\rangle$-$\Pi$ and
$\langle K\rangle$-$\Pi^{\prime}$, a (fpt) parsimonious reduction from
$\langle k\rangle$-$\Pi$ to $\langle K\rangle$-$\Pi^{\prime}$ is a function $f:I_{\Pi}\rightarrow I_{\Pi^{\prime}}$ computable in fixed-parameter time relative to
parameter $k$ such that for every $I\in{\Pi}$ (1) the number of solutions
of $\Pi$ for input $I$ is exactly equal to the number of $\Pi^{\prime}$ for input
$f(I)$ and (2) for every parameter $k^{\prime}\in K$, $k^{\prime}\leq g_{k^{\prime}}(k)$ for
some function $g_{k^{\prime}}()$.

Reductions are often established to be parsimonious by proving bijections
between solution-sets for $I$ and $f(I)$, i.e., each solution to $I$
corresponds to exactly one solution for $f(I)$ and vice versa.

We will prove various parameterized results for our problems using
reductions from ExClique. The
parameterized results are proved relative to the parameters in
Table 6. Lemmas 1 and 2 will be useful in deriving additional parameterized results from proved ones.

**Table 6: Parameters for the sufficient circuit, necessary circuit, circuit ablation problems. Note that for sufficient circuit problems, there are two versions of each parameter $k$ – namely, those describing the given MLP $M$ and the derived subcircuit $C$ (distinguished by $g$- ands $r$-subscripts, respectively).**
| Parameter | Description |
| --- | --- |
| $cd$ | # layers in given MLP |
| $cw$ | max # neurons in layer in given MLP |
| $\#n_{tot}$ | total # neurons in given MLP |
| $\#n_{in}$ | # input neurons in given MLP |
| $\#n_{out}$ | # output neurons in given MLP |
| $B_{\max}$ | max neuron bias in given MLP |
| $W_{\max}$ | max connection weight in given MLP |
| $k$ | Size of requested neuron subset |

###### Definition 13 .

###### Definition 14 .

###### Definition 15 .

###### Definition 16 .

#### C.1 Results for Sufficient Circuit Problems

###### Theorem 13 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, ExClique polynomial-time parsimoniously reduces to
$\Pi$.

###### Proof.

Consider first the local sufficient circuit problem variants. Observe
that for the reduction from Clique to MLSC in the proof of Theorem 1 (1) the reduction is also from ExClique, (2) each
clique of size $k$ in the given instance of ExClique has exactly
one corresponding sufficient circuit of size $k^{\prime}=k+k(k-1)/2+2$ in the
constructed instance of MLSC and vice versa, and (3) courtesy of the bias in
neuron $n_{out}$ and the structure of the MLP $M$ in the constructed
instance of MLSC, no sufficient circuit can have size $<k^{\prime}$ and
hence problem variants ExLSC, BLSC, MnlExLSC, and MnlBLSC (when $k^{\prime}=k+k(k-1)/2+2$) have the same set of sufficient circuit solutions
Hence, this reduction is also a polynomial-time parsimonious reduction from
ExClique to each local sufficient circuit problem variant in $L$.

As for the global sufficient circuit problem variants, it was pointed
out that in the proof of Theorem 7 that the
reduction above is also a reduction from Clique to MGSC; moreover,
all three properties above also hold modulo MGSC, ExGSC, BGSC, MnlExGSC,
and MnlBGSC. Hence, this reduction is also a polynomial-time parsimonious
reduction from ExClique to each global sufficient circuit problem variant
in $L$.
∎

###### Theorem 14 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, $\langle k\rangle$-ExClique fpt parsimoniously reduces to $\langle cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},$ $\#n_{in,r},\#n_{out,r},\#n_{tot,r},B_{\max,r},W_{\max,r}\rangle$-$\Pi$.

###### Proof.

Observe that in the instance of MLSC constructed in the reduction in the
proof of Theorem 1, $cd_{g}=cd_{r}=4$, $\#n_{in,g}=\#n_{in,r}=\#n_{out,r}=\#n_{out,r}=W_{\max,g}=W_{\max,r}=1$, and
$B_{\max,g},B_{\max,r},\#n_{tot,r},$ and $cw_{r}$ are all functions of $k$
in the given instance of Clique. The result then follows by the
reasoning in the proof of Theorem 13.
∎

###### Theorem 15 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, if $\Pi$ is polynomial-time solvable then $P=NP$.

###### Proof.

Suppose there is a polynomial-time algorithm $A$ for some $\Pi\in L$.
Let $R$ be the polynomial-time algorithm underlying the polynomial-time
parsimonious reduction from ExClique to $\Pi$ specified in the proof
of Theorem 13. Construct an algorithm $A^{\prime}$ for the
decision version of ExClique as follows: Given an input $I$ for
ExCliqueD, create input $I^{\prime}$ for $\Pi$ using $R$, and apply $A$ to $I^{\prime}$
to create solution $S$. If $S=\bot$, return “No”; otherwise, return
“Yes”. Algorithm $A^{\prime}$ is a polynomial-time algorithm for ExCliqueD;
however, as ExCliqueD is $NP$-complete (Garey & Johnson, , Problem GT19), this
implies that $P=NP$, giving the result.
∎

###### Theorem 16 .

if MinLSC or MinGSC is polynomial-time solvable then $P=NP$.

###### Proof.

Suppose there is a polynomial-time algorithm $A$ for MinLSC (MinGSC).
Let $R$ be the polynomial-time algorithm underlying the polynomial-time
parsimonious reduction from ExClique to BLSC (BGSC) specified in the proof
of Theorem 13. Construct an algorithm $A^{\prime}$ for the
decision version of ExClique as follows: Given an input $I$ for
ExCliqueD, create input $I^{\prime}$ for BSC )LSC) using $R$, and apply $A$ to
$I^{\prime}$ to create solution $S$. If $|S|\leq k$, return “Yes”; otherwise,
return “No”. Algorithm $A^{\prime}$ is a polynomial-time algorithm for
ExCliqueD; however, as ExCliqueD is $NP$-complete
(Garey & Johnson, , Problem GT19), this implies that $P=NP$, giving the result.
∎

###### Theorem 17 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$ and $K=\{cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_{in,
r},\#n_{out,r},\#n_{tot,r},B_{\max,r},$ $W_{\max,r}\}$,
if $\langle K\rangle$-$\Pi$ is fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Suppose there is a fixed-parameter tractable algorithm $A$ for
$\langle K\rangle$-$\Pi$ for some $\Pi\in L$. Let $R$ be the fixed-parameter algorithm
underlying the fpt parsimonious reduction from $\langle k\rangle$-ExClique to
$\langle K\rangle$-$\Pi$ specified in the proof of Theorem 14.
Construct an algorithm $A^{\prime}$ for the decision version of $\langle k\rangle$-ExClique
as follows: Given an input $I$ for $\langle k\rangle$-ExCliqueD,
create input $I^{\prime}$ for $\Pi$ using $R$, and apply $A$ to $I^{\prime}$ to create
solution $S$. If $S=\bot$, return “No”; otherwise, return “Yes”.
Algorithm $A^{\prime}$ is a fixed-parameter tractable algorithm for
$\langle k\rangle$-ExCliqueD; however, as $\langle k\rangle$-ExCliqueD is
$W[1]$-complete (Downey & Fellows, ), this implies that $FPT=W[1]$, giving the
result.
∎

###### Theorem 18 .

For $K=\{cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_{in,
r},\#n_{out,r},$ $\#n_{tot,r},B_{\max,r},W_{\max,r}\}$,
if $\langle K\rangle$-MinLSC or $\langle K]\rangle$-MinGSC is fixed-parameter tractable
then $FPT=W[1]$.

###### Proof.

Suppose there is a fixed-parameter tractable algorithm $A$ for
$\langle K\rangle$-MinLSC ($\langle K\rangle$-MinGSC). Let $R$ be the
fixed-parameter algorithm underlying the fpt parsimonious reduction from
$\langle k\rangle$-ExClique to $\langle K\rangle$-BLSC ($\langle K\rangle$-BGSC) specified in the
proof of Theorem 14. Construct an algorithm $A^{\prime}$ for the
decision version of $\langle k\rangle$-ExClique as follows: Given an input $I$ for
$\langle k\rangle$-ExCliqueD, create input $I^{\prime}$ for $\Pi$ using $R$, and apply
$A$ to $I^{\prime}$ to create solution $S$. If $|S|\leq k$, return “Yes”;
otherwise, return “No”. Algorithm $A^{\prime}$ is a fixed-parameter tractable
algorithm for $\langle k\rangle$-ExCliqueD; however, as
$\langle k\rangle$-ExCliqueD is $W[1]$-complete (Downey & Fellows, ), this implies that
$FPT=W[1]$, giving the result.
∎

###### Theorem 19 .

For $\Pi\in L=\{{\bf V}LSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, #$\Pi$ is #P-complete.

###### Proof.

As #ExVC is #P-complete (Provan & Ball , Page 781; see also
Garey & Johnson , Page 169), #ExClique is
#P-hard by the polynomial-time parsimonious reduction from
ExVC to ExClique implicit in Garey & Johnson , Lemma 3.1. The #P-hardness
of #$\Pi$ then follows from the appropriate polynomial-time
parsimonious reduction from ExClique to $\Pi$ specified in the proof
of Theorem 13. Membership of #$\Pi$ in #P and the
result follows from the nondeterministic algorithm for
#$\Pi$ that, on each computation path, guesses a subcircuit $C$ of $M$
and then verified that $C$ satisfies the properties required by $\Pi$
relative to MLP $M$ input $I$.
∎

###### Theorem 20 .

For $\Pi\in L=\{{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, #$\Pi$ is #P-hard.

###### Proof.

The result follows from the #P-hardness of #ExClique noted in the
proof of Theorem 20 and the appropriate polynomial-time
parsimonious reduction from ExClique to $\Pi$ specified in the proof
of Theorem 13.
∎

###### Theorem 21 .

#MnlLSC is #P-complete.

###### Proof.

Consider the reduction from MnlVC to MnlLSC created by modifying the
reduction
from VC to MLSC given in the proof of Theorem 5 such
that the bias and input-line weight of input neuron $n_{in}$ are changed
to 0 and 1 to ensure that all possible input vectors (namely, $\{0\}$ and
$\{1\}$) cause $n_{in}$ to output 1. Observe that this modified reduction
runs in time polynomial in the size of the given instance of MnlVC.
We now need to show that this reduction is parsimonious, i.e., this
reduction creates a bijection between the
solution-sets of the given instance of MnlVC and the constructed instance
of MnlLSC. We prove the two directions of this bijection separately as
follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a minimal vertex cover in $G$. Consider the subcircuit $C$ based
on neurons $n_{in}$, $n_{out}$, $\{nv^{\prime}N~{}|~{}v^{\prime}\in V^{\prime}\}$,
$\{neA_{1},neA_{2},\ldots,neA_{|E|}\}$, and
$\{neN_{1},neN_{2},\ldots,neN_{|E|}\}$.
As shown in the $\Rightarrow$-portion of the proof of correctness
of the reduction in the proof of Theorem 5,
$C$ is behaviorally equivalent to $M$ on $I$.
As $V^{\prime}$ is minimal and only vertex NOT neurons can be
deleted from $M$ to create $C$, $C$ must itself be
minimal. Moreover, note that any such set $V^{\prime}$ in $G$ is associated
with exactly one set of vertex NOT neurons in (and thus exactly
one sufficient circuit of) $M$.

: Let $C$ be a minimal subcircuit of $M$ that is
behaviorally equivalent to $M$ on input $I$. As neurons in all five
layers in $M$ must be present in $C$ to produce the required output,
both $n_{in}$ and $n_{out}$ are in $C$. In order for $n_{out}$
to produce a non-zero output, all $|E|$ edge NOT neurons and all
$|E|$ AND neurons must also be in $C$, and each of the latter must
be connected to at least one of the vertex NOT neurons corresponding
to their endpoint vertices. Hence, the vertices in $G$ corresponding
to the vertex NOT neurons in $C$ must form a vertex cover in $G$.
As $C$ is minimal and only vertex NOT neurons can be
deleted from $M$ to create $C$, this vertex cover must itself be
minimal. Moreover, note that any such set of vertex NOT neurons in
$M$ is associated with exactly one set of vertices in (and hence
exactly one vertex cover of) $G$.

As #MnlVC is #P-complete (Valiant, , Theorem 1(4)), the reduction
above establishes that #MnlLSC is #P-hard. Membership of #MnlLSC in
#P and hence the result follows from the nondeterministic algorithm for
#MnlLSC that, on each computation path, guesses a subcircuit $C$ of $M$
and then verifies that $C$ is minimal and $C(I)=M(I)$.
∎

###### Theorem 22 .

#MnlGSC is #P-hard.

###### Proof.

Recall that the parsimonious reduction from MnlVC to MnlLSC in the proof of
Theorem 21 creates an instance of MnlLSC whose MLP $M$
has the same output for every possible input vector; hence, this reduction
is also a parsimonious reduction from MnlVC to MnlGSC.
As #MnlVC is #P-complete (Valiant, , Theorem 1(4)), this reduction
establishes that #MnlGSC is #P-hard, giving the result.
∎

###### Theorem 23 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$, if #$\Pi$ is polynomial-time solvable then $P=NP$.

###### Proof.

Suppose there is a polynomial-time algorithm $A$ for #$\Pi$ for
some $\Pi\in L$. Let $R$ be the polynomial-time algorithm underlying the
polynomial-time parsimonious reduction from ExClique to $\Pi$ specified in
the proof of Theorem 13. Construct an algorithm $A^{\prime}$ for
the decision version of ExClique as follows: Given an input $I$ for
ExCliqueD, create input $I^{\prime}$ for $\Pi$ using $R$, and apply $A$ to $I^{\prime}$
to create solution $S$. If $S=0$, return “No”; otherwise, return
“Yes”. Algorithm $A^{\prime}$ is a polynomial-time algorithm for ExCliqueD;
however, as ExCliqueD is $NP$-complete (Garey & Johnson, , Problem GT19), this
implies that $P=NP$, giving the result.
∎

###### Theorem 24 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$ and $K=\{cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_{in,
r},\#n_{out,r},\#n_{tot,r},B_{\max,r},W_{\max,r}\}$,
$\langle K\rangle$-#$\Pi$ is #$W[1]$-hard.

###### Proof.

The result follows from the #$W[1]$-hardness of $\langle k\rangle$-#ExClique
(Flum & Grohe, , Theorem 14.18)
and the appropriate fpt parsimonious reduction from $\langle k\rangle$-ExClique to
$\langle K\rangle$-$\Pi$ specified in the proof of Theorem 14.
∎

###### Theorem 25 .

For $\Pi\in L=\{{\bf V}LSC,{\bf V}GSC~{}|~{}{\bf V}\in\{Ex,B,MnlEx,MnlB\}\}$ and $K=\{cd_{g},\#n_{in,g},\#n_{out,g},B_{\max,g},W_{\max,g},cd_{r},cw_{r},\#n_{in,
r},\#n_{out,r},\#n_{tot,r},B_{\max,r},W_{\max,r}\}$,
if $\langle K\rangle$-#$\Pi$ is fixed-parameter tractable then $FPT=\#W[1]$.

###### Proof.

Suppose there is a fixed-parameter tractable algorithm $A$ for
$\langle K\rangle$-#$\Pi$ for some $\Pi\in L$. Let $R$ be the fixed-parameter algorithm
underlying the fpt parsimonious reduction from $\langle k\rangle$-ExClique to
$\langle K\rangle$-$\Pi$ specified in the proof of Theorem 14.
Construct an algorithm $A^{\prime}$ for $\langle k\rangle$-#ExClique
as follows: Given an input $I$ for $\langle k]ra$-#ExClique,
create input $I^{\prime}$ for #$\Pi$ using $R$, and apply $A$ to $I^{\prime}$ to create
solution $S$. If $S=0$, return “No”; otherwise, return “Yes”.
Algorithm $A^{\prime}$ is a fixed-parameter tractable algorithm for
$\langle k\rangle$-#ExCliqueD; however, as $\langle k\rangle$-ExCliqueD is
$\#W[1]$-complete (Flum & Grohe, , Theorem 14.18), this implies that $FPT=\#W[1]$, giving the result.
∎

###### Theorem 13 .

###### Proof.

###### Theorem 14 .

###### Proof.

###### Theorem 15 .

###### Proof.

###### Theorem 16 .

###### Proof.

###### Theorem 17 .

###### Proof.

###### Theorem 18 .

###### Proof.

###### Theorem 19 .

###### Proof.

###### Theorem 20 .

###### Proof.

###### Theorem 21 .

###### Proof.

###### Theorem 22 .

###### Proof.

###### Theorem 23 .

###### Proof.

###### Theorem 24 .

###### Proof.

###### Theorem 25 .

###### Proof.

### Appendix D Global Sufficient Circuit Problem (sigma completeness)

Minimum global sufficient circuit (MGSC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd_{g}}$, neuron bias vector $B$,
and a positive integer $k$.
Question: Is there a subcircuit $C$ of $M$ based on $\leq k$ neurons
from $M$ such that for every possible input $I$ of $M$,
$C(I)=M(I)$?

Given a subset $N$ of the neurons in $M$, the subcircuit $C$ of $M$ based on
$x$ has the neurons in $x$ and all connections in $M$ among these neurons.
Note that in order for the output of $C$ to be equal to the output of $M$ on
input $I$, the numbers $\#n_{in}$ and $\#n_{out}$ of input and output
neurons in $M$ must exactly equal the numbers
of input and output neurons in $C$; hence, no input or output neurons can be
deleted from $M$ in creating $C$. Following Barceló et al. , page 4, all neurons in $M$ use the ReLU activation function and the output $x$ of each output neuron is stepped as necessary to be Boolean, i.e, $step(x)=0$ if $x\leq 0$ and is $1$ otherwise.

We will prove our result for MGSC using a polynomial-time reduction from
the problem Minimum DNF Tautology. Given a DNF formula $\phi$ over a set $V$ of
variables, $\phi$ is a tautology if $\phi$ evaluates to $True$ for
every possible truth-assignment to the variables in $V$.

Our reduction will use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

###### Theorem 26 .

MGSC is $\Sigma^{p}_{2}$-complete.

###### Proof.

Let us first show the membership of MGSC in $\Sigma^{p}_{2}$. Using the
alternating-quantifier definition of classes in the polynomial hierarchy,
membership of a decision problem $\Pi$ in $\Sigma^{p}_{2}$ can be proved by
showing that solving $\Pi$ for input $I$ is equivalent to solving a
quantified formula of the form $\exists(x)\forall(y):p(x,y)$
where both the sizes of $x$ and $y$ and the evaluation time of
predicate formula $p()$ are upper-bounded by polynomials in $|I|$. Such a formula for MGSC is

$$ $\exists(\mathcal{C}\subseteq\mathcal{M})\forall\mathbf{x}\in\{0,1\}^{\#n_{in}} :\mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})$ $$

We now show the $\Sigma^{p}_{2}$-hardness of MGSC.
Consider the following reduction from 3DT to MGSC. Given an instance $\langle\phi,T,V,k\rangle$ of 3DT, construct the following instance $\langle M,k^{\prime}\rangle$
of MGSC: Let $M$ be an MLP based on $3|V|+2T+2$ neurons spread
across five layers:

- 1.
Input neuron layer: The input neurons $ni_{1},ni_{2},\ldots,ni_{|V|}$ (all with bias 0).
- 2.
Hidden layer I: The unnegated variable identity neurons $nvU_{1},nvU_{2},\ldots,nvU_{|V|}$ (all with bias 0) and negated variable
NOT neurons $nvN_{1},nvN_{2},\ldots,nvN_{|V|}$ (all with bias 1).
- 3.
Hidden layer II:
(a)
The term 3-way AND neurons $nT_{1},xT_{2},\ldots,xT_{|T|}$
(all with bias -2).
(b)
The gadget neuron $n_{g}$ (bias $|V|-1$).
- 4.
Hidden layer III: The modified term 2-way AND neurons
$nTm_{1},nTM_{2},\ldots,nTM_{|T|}$ (all with bias $-1$).
- 5.
Output layer: The stepped output neuron $n_{out}$.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input neuron $ni_{i}$, $1\leq i\leq|V|$, is input-connected with
weight 1 to its corresponding input line and output-connected with
weights 1 and -1 to unnegated and negated variable neurons
$nvU_{i}$ and $nvN_{i}$, respectively.
- •
Each term neuron $nT_{i}$, $1\leq i\leq|T|$, is input-connected with
weight 1 to each of the 3 variable neurons corresponding to that
term’s literals.
- •
The gadget neuron $n_{g}$ is input-connected with weight 1 to all of the
unnegated and negated variable neurons.
- •
Each modified term neuron $nTm_{i}$, $1\leq i\leq|T|$, is
input-connected with weight 1 to the term neuron $nT_{i}$ and the
gadget neuron $n_{g}$ and output-connected with weight 1 to the
output neuron $n_{out}$.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $k^{\prime}=3|V|+2k+2$. Observe that this instance of MGSC can be
constructed time polynomial in the size of the given instance of 3DT.

The following observations about the MLP $M$ constructed above will
be of use:

- •
The input to $M$ is exactly that of the 3-DNF formula $\phi$.
- •
The output neuron of $M$ outputs 1 if and only if one or more of the
modified term neurons output 1.
- •
Modified term neuron $nTm_{i}$ outputs 1 if and only both the
term neuron $nT_{i}$ and the gadget neuron $n_{g}$ output 1.
- •
The gadget neuron $n_{g}$ outputs 1 for input $I$ to a subcircuit $C$
of $M$ if and only if
the negated and unnegated variable neurons corresponding to
$I$ each output 1; hence, $n_{g}$ outputs 1 for all possible
inputs to $C$ if and only if all negated and unnegated variable
neurons in hidden layer I are part of $C$.

As $\phi$ is a tautology, the above implies that (1) $M$ outputs 1
for every possible input and (2) every global sufficient circuit of $M$
must include all input and variable neurons, the gadget and output neurons,
and at least one term / modified term neuron-pair.

We now need to show the correctness of this reduction by proving that the
answer for the given instance of 3DT is “Yes” if and only if the answer
for the constructed instance of MGSC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $T^{\prime}$, $|T^{\prime}|=k$ be a subset of the terms
in $\phi$ that is a tautology. As noted above, any global
sufficient circuit $C$ for the constructed MLP $M$ must include all
input and variable neurons, the gadget and output neurons, and at
least one term / modified term neuron-pair. Let $C$ contain
the term / modified term neuron-pairs corresponding to the
terms in $T^{\prime}$. Such a $C$ is therefore a global sufficient
circuit for $M$ of size $k^{\prime}=3|V|=2k+2$.

: Let $C$ be a global sufficient circuit for $M$
of size $k^{\prime}=3|V|+2k+2$. As noted above, $C$ must include all
input and variable neurons, the gadget and output neurons, and $k$
term / modified term neuron-pairs. Let $T^{\prime}$ be the subset of
$k$ terms in $\phi$ corresponding to these neuron-pairs. Given
the input-output equivalence $\phi$ and $M$ (and hence any
sufficient circuit for $M$), the disjunction of the $k$ terms in
$T^{\prime}$ must be a tautology.

As 3DT is $\Sigma^{p}_{2}$-hard (Schaefer & Umans, , Problem L7), the reduction above
establishes that MGSC is also $\Sigma^{p}_{2}$-hard. The result then
follows from the membership of MGSC in $\Sigma^{p}_{2}$ shown at the beginning
of this proof.
∎

###### Theorem 26 .

###### Proof.

### Appendix E Quasi-Minimal Sufficient Circuit Problem

Quasi-Minimal Sufficient Circuit (QMSC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$, a set $\mathcal{X}$ of input vectors of length $\#n_{in}$.
Output: a circuit $\mathcal{C}$ in $\mathcal{M}$ and a neuron $v\in\mathcal{C}$ such that $\mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})$ and $[\mathcal{C}\setminus\{v\}](\mathbf{x})\neq\mathcal{M}(\mathbf{x})$

###### Theorem 27 .

QMSC is in PTIME (i.e., polynomial-time tractable).

###### Proof.

Consider the following algorithm for QMSC.
Build a sequence of MLPs by taking $\mathcal{M}$ with all neurons labeled 1, and generating subsequent $\mathcal{M}_{i}$ in the sequence by labeling an additional neuron with 0 each time (this choice can be based on any heuristic strategy, for instance, one based on gradients).
The first MLP, $\mathcal{M}_{1}$, obtained by removing all neurons labeled 0 (i.e., none) is such that $\mathcal{M}_{1}(x)=\mathcal{M}(x)$, and the last $\mathcal{M}_{n}$ is guaranteed to give $\mathcal{M}_{n}(x)\neq\mathcal{M}(x)$ because all neurons are removed.
Label the first MLP YES, and the last NO.
Perform a variant of binary search on the sequence as follows.
Evaluate the $\mathcal{M}_{i}$ halfway between YES and NO while removing all its neurons labeled 0.
If it satisfies the condition, label it YES, and repeat the same strategy with the sequence starting from the YES just labeled until the last $\mathcal{M}_{n}$.
If it does not satisfy the condition, label it NO and repeat the same strategy with the sequence starting from the YES at the beginning of the original sequence until the NO just labeled.
This iterative procedure halves the sequence each time.
Halt when you find two adjacent $\langle\texttt{YES},\texttt{NO}\rangle$ circuits (guaranteed to exist), and return the circuit set of the YES network V and the single neuron difference between YES and NO (the breaking point), $v\in V$.
The complexity of this algorithm is roughly $O(n\log n)$.

∎

###### Theorem 27 .

###### Proof.

### Appendix F Gnostic Neurons Problem

Gnostic Neurons (GN)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$, and two sets $\mathcal{X}$ and $\mathcal{Y}$ of input vectors of length $\#n_{in}$, and a positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Output: a subset of neurons $V$ in $M$ of size $|V|\geq k$ such that $\forall_{v\in V}$ it is the case that $\forall_{\mathbf{x}\in\mathcal{X}}$ computing $M(\mathbf{x})$ produces activations $A^{v}_{\mathbf{x}}\geq t$ and $\forall_{\mathbf{y}\in\mathcal{Y}}:A^{v}_{\mathbf{y}}<t$.

###### Theorem 28 .

GN is in PTIME (i.e., polynomial-time tractable).

###### Proof.

Consider the complexity of the following subroutines of an algorithm for GN.
Computing the activations of all neurons of $M$ for all $\mathbf{x}\in\mathcal{X}$ and all $\mathbf{y}\in\mathcal{Y}$ takes polynomial time in $|M|,|\mathcal{X}|$ and $|\mathcal{Y}|$.
Labeling neurons that pass or not the activation threshold takes time polynomial in $|M|,|\mathcal{X}|$ and $|\mathcal{Y}|$.
Finally, checking whether the set of neurons that fulfils the condition is of size at least $k$ can be done in polynomial time in $|M|$.
These subroutines can be put together to yield a polynomial-time algorithm for GN.
∎

###### Remark 1

One could also add to the output of the computational problem the requirement that if we silence (or activate) the neuron, we should elicit (or abolish) a behavior. Note that checking these effects can be done in polynomial time in all of the input parts given above and also in the size of the behavior set (which should be added to the input in these variants).

###### Theorem 28 .

###### Proof.

###### Remark 1

### Appendix G Necessary Circuit Problem

Minimum Local Necessary Circuit (MLNC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that $N^{\prime}\cap C\neq\emptyset$ for every
sufficient circuit $C$ of $M$ relative to $I$?

Minimum Global Necessary Circuit (MGNC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that for for every possible Boolean input
vector $I$ of length $\#n_{in}$, $N^{\prime}\cap C\neq\emptyset$
for every sufficient circuit $C$ of $M$ relative
to $I$?

We will use reductions from the Hitting Set problem
to prove our results for the problems above.

Regarding the Hitting Set problem, we shall assume an ordering on the sets and elements in $C$ and $S$,
respectively.

Our parameterized results are proved relative to the parameters in
Table 7. Lemmas 1 and 2 will be useful
in deriving additional parameterized results from proved ones.

Our reductions will use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

**Table 7: Parameters for the minimum necessary circuit problem.**
| Parameter | Description |
| --- | --- |
| $cd$ | # layers in given MLP |
| $cw$ | max # neurons in layer in given MLP |
| $\#n_{tot}$ | total # neurons in given MLP |
| $\#n_{in}$ | # input neurons in given MLP |
| $\#n_{out}$ | # output neurons in given MLP |
| $B_{\max}$ | max neuron bias in given MLP |
| $W_{\max}$ | max connection weight in given MLP |
| $k$ | Size of requested neuron subset |

#### G.1 Results for MLNC

Membership of MLNC in $\Sigma^{p}_{2}$ can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[N\subseteq\mathcal{M}]\ \forall[\mathcal{C}\subseteq\mathcal{M}]:[ \mathcal{C}(\mathbf{x})=\mathcal{M}(\mathbf{x})]\implies N\cap\mathcal{C}\neq\emptyset$ $$

###### Theorem 29 .

If MLNC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from HS to MLNC. Given an instance $\langle C,S,k\rangle$ of HS, construct the following instance $\langle M,I,k^{\prime}\rangle$ of MLNC:
Let $M$ be an MLP based on $\#n_{tot}=|S|+|C|+2$ neurons spread
across four layers:

- 1.
Input neuron layer: The single input neuron $n_{in}$ (bias $+1$).
- 2.
Hidden element layer: The element neurons $ns_{1},ns_{2},\ldots ns_{|S|}$ (all with bias 0).
- 3.
Hidden set layer: The set AND neurons $nc_{1},nc_{2},\ldots,nc_{|C|}$ (such that neuron $nc_{i}$ has bias $-|c_{i}|$).
- 4.
Output layer: The single stepped output neuron $n_{out}$
(bias 0).

The non-zero weight connections between adjacent layers are as follows:

- •
The input neuron has an edge of weight 0 coming from its
input and is in turn connected to each of the element
neurons with weight 1.
- •
Each element neuron $ns_{i}$, $1\leq i\leq|S|$, is connected to each
set neuron $nc_{j}$, $1\leq j\leq|C|$, such that $s_{i}\in c_{j}$ with
weight 1.
- •
Each set neuron $nc_{i}$, $1\leq i\leq|C|$, is connected to the
output neuron with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(0)$ and $k^{\prime}=k$. Observe that this instance of MLNC can
be created in time polynomial in the size of the given instance of HS.
Moreover, the output behaviour of the neurons in $M$ from the presentation
of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $ns_{1},ns_{2},\ldots,ns_{|S|}$ (1) |
| 3 | $nc_{1},nc_{2},\ldots,nc_{|C|}$ (1) |
| 4 | $n_{out}(1))$ |

Note the following about the behavior of $M$:

###### Observation 1 .

For any set neuron $nc_{i}$ to output 1, it must receive input 1 from all
of its incoming element neurons connected with weight 1.

###### Observation 2 .

For the output neuron to output 1, it is sufficient to get input 1 from
any of its incoming set neurons with weight 1.

Observations 1 and 2 imply that any sufficient circuit for
$M$ must contain at least one set neuron and all of its associated
element neurons.

We now need to show the correctness of this reduction by proving that the
answer for the given instance of HS is “Yes” if and only if the answer for
the constructed instance of MLNC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $S^{\prime}=\{s^{\prime}_{1},s^{\prime}_{2},\ldots,s^{\prime}_{k}\}\subseteq S$
be a hitting set of size $k$ for $C$. By the construction above,
the $k$ element neurons corresponding to the elements in $S^{\prime}$
collectively connect with weight 1 to all set neurons in $M$.
By Observations 1 and 2, this means that the
set $N$ of these element neurons has a non-empty intersection with
every sufficient circuit for $M$, and hence that $N$ is a necessary
circuit for $M$ of size $k=k^{\prime}$.

: Let $N$ be a necessary circuit for $M$ of size $k^{\prime}$.
Let $N_{S}$ and $N_{C}$ be the subsets of $N$ that are element and
set neurons. We can create a set $N^{\prime}$ consisting only of element
neurons by replacing each set neuron $n_{c}$ in $N_{C}$ with an arbitrary
element neuron that is not already in $N_{S}$ and is connected to $n_{c}$
with weight 1. Observe that $N^{\prime}$ (whose size may be less than $k^{\prime}$ if
any $n_{c}$ already had an associated element neuron in $N_{S}$) remains
a necessary circuit for $M$. Moreover, as the element neurons in $N^{\prime}$
by definition have a non-empty intersection with each sufficient
circuit for $M$, by Observations 1 and 2 above,
the set $S^{\prime}$ of elements in $S$ corresponding to the element neurons
in $N^{\prime}$ has a non-empty intersection with each set in $C$ and
hence is a hitting set of size $N^{\prime}\leq k^{\prime}=k$

As HS is $NP$-hard (Garey & Johnson, ), the reduction above establishes
that MLNC is also $NP$-hard. The result follows from the definition of
$NP$-hardness.
∎

###### Theorem 30 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},k\rangle$-MLNC is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MLNC constructed in the reduction in the
proof of Theorem 29, $\#n_{in}=\#n_{out}=W_{\max}=1$,
$cd=4$, and $k^{\prime}$ is a function of $k$ in the given instance of HS.
The result then follows from the facts that
$\langle k\rangle$-HS is $W[2]$-hard (by a reduction from $\langle k\rangle$-Dominating set; Downey & Fellows ) and $W[1]\subseteq W[2]$.
∎

###### Theorem 31 .

$\langle\#n_{tot}\rangle$-MLNC is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates every possible subset $N^{\prime}$ of size
at most $k$ of the neurons in MLP $M$ and for each such subset,
generates every possible subset $N^{\prime\prime}$ of $M$, checks if $N^{\prime\prime}$ is
a sufficient circuit for $M$ relative to $I$ and, if so, checks if
$N^{\prime}$ has a non-empty intersection with $N^{\prime\prime}$. If an $N^{\prime}$ is found that
has a non-empty intersection with each sufficient circuit for $M$
relative to $I$, return “Yes”; otherwise, return “No”. The number of
possible subsets $N^{\prime}$ and $N^{\prime\prime}$ are both at most $2^{\#n_{tot}}$.
As all subsequent checking operations can be done
in time polynomial in the size of the given
instance of MLNC, the above is a fixed-parameter tractable
algorithm for MLNC relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 32 .

$\langle cw,cd\rangle$-MLNC is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 31 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 30–32
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MLNC relative
to many subsets of the parameters listed in Table 7.

Let us now consider the polynomial-time cost approximability of MLNC.

###### Theorem 33 .

If MLNC has a polynomial-time $c$-approximation algorithm for any constant
$c>0$ then $P=NP$.

###### Proof.

Recall from the proof of correctness of the reduction in the proof of
Theorem 29 that a given instance of HS has a hitting set
of size $k$ if and only if the constructed instance of MLNC has a
necessary circuit of size $k^{\prime}=k$. This implies
that, given a polynomial-time $c$-approximation algorithm $A$ for MLNC for
some constant $c>0$, we can create a polynomial-time $c$-approximation
algorithm for HS by applying the reduction to the given instance $x$ of HS
to construct an instance $x^{\prime}$ of MLNC, applying $A$ to $x^{\prime}$ to create an
approximate solution $y^{\prime}$, and then using $y^{\prime}$ to create an approximate
solution $y$ for $x$ that has the same cost as $y^{\prime}$. The result then
follows from Ausiello et al. , Problem SP7, which states that if HS has a
polynomial-time $c$-approximation algorithm for any constant $c>0$ a
and is hence in approximation problem class APX then $P=NP$.
∎

Note that this theorem also renders MLNC PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 29 .

###### Proof.

###### Observation 1 .

###### Observation 2 .

###### Theorem 30 .

###### Proof.

###### Theorem 31 .

###### Proof.

###### Theorem 32 .

###### Proof.

###### Theorem 33 .

###### Proof.

#### G.2 Results for MGNC

Membership of MLNC in $\Sigma^{p}_{2}$ can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[N\subseteq\mathcal{M}]\ \forall[\mathcal{C}\subseteq\mathcal{M}\ s.t. \ \forall(\mathbf{x}\in\{0,1\}^{\#n_{in}})]:N\cap\mathcal{C}\neq\emptyset$ $$

###### Theorem 34 .

If MGNC is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLNC constructed by the reduction in the
proof of Theorem 29, the input-connection weight 0 and
bias 1 of the input neuron force this neuron to output 1 for
both of the possible input vectors $(1)$ and $(0)$.
Hence, with slight modifications to the proof
of reduction correctness, this reduction also establishes the
$NP$-hardness of MGNC.
∎

###### Theorem 35 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},k\rangle$-MGNC is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MGNC constructed in the reduction in the
proof of Theorem 34, $\#n_{in}=\#n_{out}=W_{\max}=1$,
$cd=4$, and $k^{\prime}$ is a function of $k$ in the given instance
of HS The result then follows from the facts that
$\langle k\rangle$-HS is $W[2]$-hard (by a reduction from $\langle k\rangle$-Dominating set; Downey & Fellows ) and $W[1]\subseteq W[2]$.
∎

###### Theorem 36 .

$\langle\#n_{tot}\rangle$-MGNC is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 31 such
that each potential sufficient circuit $N^{\prime\prime}$ is checked to ensure that
$M(I)=N^{\prime\prime}(I)$ for
every possible Boolean input vector of length $\#n_{in}$. As the number of
such vectors is $2^{\#n_{in}}<2^{\#n_{tot}}$,
the above is a fixed-parameter tractable
algorithm for MGNC relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 37 .

$\langle cw,cd\rangle$-MGNC is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 36 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 35–37
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MGNC relative
to many subsets of the parameters listed in Table 7.

Let us now consider the polynomial-time cost approximability of MGNC.

###### Theorem 38 .

If MGNC has a polynomial-time $c$-approximation algorithm for any constant
$c>0$ then $P=NP$.

###### Proof.

As the reduction in the proof of Theorem 34 is essentially
the same as the reduction in the proof of Theorem 29, the
result follows by the same reasoning as given in the proof of Theorem
33.
∎

Note that this theorem also renders MGNC PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 34 .

###### Proof.

###### Theorem 35 .

###### Proof.

###### Theorem 36 .

###### Proof.

###### Theorem 37 .

###### Proof.

###### Theorem 38 .

###### Proof.

### Appendix H Circuit Ablation and Clamping Problems

Given an MLP $M$ and a subset $N$ of the neurons in $M$, the MLP $M^{\prime}$
induced by $N$ is said to be active if there is at least one path
between the the input and output neurons in $M^{\prime}$; otherwise, $M^{\prime}$ is
inactive. As we are interested in inductions that preserve or
violate output behaviour, all output neurons of $M$ must be preserved in
$M^{\prime}$; however, we only require that at least one input neuron be so
preserved. Unless otherwise stated, all inductions discussed wrt MLCA and
MGCA below will be assumed to result in active MLP.

Minimum Local Circuit Ablation (MLCA)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that $M(I)\neq M^{\prime}(I)$ for the MLP $M^{\prime}$
induced by $N\setminus N^{\prime}$?

Minimum Global Circuit Ablation (MGCA)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that for the MLP $M^{\prime}$ induced by $N\setminus N^{\prime}$, $M(I)\neq M^{\prime}(I)$ for every possible Boolean input
vector $I$ of length $\#n_{in}$?

Given an MLP $M$ and a neuron $v$ in $M$, $v$ is clamped to value
$val$ if the output of $v$ is always $val$ regardless of the inputs to $v$.
As one can trivially change the output of an MLP by clamping one or
more of its output neurons, we shall not allow the clamping of output
neurons in the problems below.

Minimum Local Circuit Clamping (MLCC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$, a Boolean
value $val$, and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that $M(I)\neq M^{\prime}(I)$ for the MLP $M^{\prime}$ in
which all neurons in $N^{\prime}$ are clamped to value $val$?

Minimum Global Circuit Clamping (MGCC)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean value $val$, and a positive integer $k$ such that
$1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that for the MLP $M^{\prime}$ in which all neurons in
$N^{\prime}$ are clamped to value $val$, $M(I)\neq M^{\prime}(I)$ for every
possible Boolean input vector $I$ of length $\#n_{in}$?

Following Barceló et al. , page 4, all
neurons in $M$ use the ReLU activation function and the output $x$ of each
output neuron is stepped as necessary to be Boolean, i.e, $step(x)=0$ if
$x\leq 0$ and is $1$ otherwise.

For a graph $G=(V,E)$, we shall assume an ordering on the vertices and edges in $V$
and $E$, respectively. For each vertex $v\in V$, let the complete neighbourhood $N_{C}(v)$ of $v$ be the set
composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$
by a single edge, i.e., $v\cup\{u~{}|~{}u~{}\in V~{}\rm{and}~{}(u,v)\in E\}$.

We will prove various classical and parameterized results for MLCA, MGCA,MLCC, and MGCC using reductions from Clique.
The parameterized results are proved relative to the parameters in Table 8. Lemmas 1 and 2 will be useful in deriving additional parameterized results from proved ones.

Additional reductions from DS used to prove polynomial-time cost
inapproximability use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

**Table 8: Parameters for the minimum circuit ablation and clamping problems.**
| Parameter | Description |
| --- | --- |
| $cd$ | # layers in given MLP |
| $cw$ | max # neurons in layer in given MLP |
| $\#n_{tot}$ | total # neurons in given MLP |
| $\#n_{in}$ | # input neurons in given MLP |
| $\#n_{out}$ | # output neurons in given MLP |
| $B_{\max}$ | max neuron bias in given MLP |
| $W_{\max}$ | max connection weight in given MLP |
| $k$ | Size of requested neuron subset |

#### H.1 Results for Minimal Circuit Ablation

The following hardness and inapproximability results are notable for holding
when the given MLP $M$ has three hidden layers.

##### H.1.1 Results for MLCA

Towards proving NP-completeness, we first prove membership and then follow up with hardness.
Membership in NP can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]:[\mathcal{M}\setminus\mathcal{S}]( \mathbf{x})\neq\mathcal{M}(\mathbf{x})$ $$

###### Theorem 39 .

If MLCA is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from Clique to MLCA. Given an
instance $\langle G=(V,E),k\rangle$ of Clique, construct the following
instance $\langle M,I,k^{\prime}\rangle$ of MLCA:
Let $M$ be an MLP based on $\#n_{tot}=3|V|+|E|+2$ neurons spread
across five layers:

- 1.
Input neuron layer: The single input neuron $n_{in}$ (bias $+1$).
- 2.
Hidden vertex pair layer: The vertex neurons $nvP1_{1},nvP1_{2},\ldots nvP1_{|V|}$ and $nvP2_{1},nvP2_{2},\ldots nvP2_{|V|}$
(all with bias 0).
- 3.
Hidden vertex regulator layer: The vertex neurons $nvR_{1},nvR_{2},\ldots nR_{|V|}$
(all with bias 0).
- 4.
Hidden edge layer: The edge neurons $ne_{1},ne_{2},\ldots ne_{|E|}$
(all with bias $-1$).
- 5.
Output layer: The single output neuron $n_{out}$ (bias $-(k(k-1)/2-1)$).

The non-zero weight connections between adjacent layers are as follows:

- •
Each input neuron has an edge of weight 0 coming from its
corresponding input and is in turn connected to each of the vertex
pair neurons with weight 1.
- •
Each P1 (P2) vertex pair neuron $nvP1_{i}$ ($nvP2_{i}$), $1\leq i\leq|V|$, is connected to vertex regulator neuron $nvR_{i}$ with
weight $-2$ (1).
- •
Each vertex regulator neuron $nv_{i}$, $1\leq i\leq|V|$, is connected to each edge neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge neuron $ne_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(1)$ and $k^{\prime}=k$.
Observe that this instance of MLCA can be created in time polynomial in the size of the
given instance of Clique. Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nvP1_{1}(1),nvP1_{2}(1),\ldots nvP1_{|V|}(1),nvP2_{1}(1),nvP2_{2}(1),\ldots nvP<br>2_{|V|}(1)$ |
| 3 | $nvR_{1}(0),nvR_{2}(0),\ldots nvR_{|V|}(0)$ |
| 4 | $ne_{1}(0),ne_{2}(0),\ldots ne_{|E|}(0)$ |
| 5 | $n_{out}(0))$ |

We now need to show the correctness of this reduction by proving that the answer
for the given instance of Clique is “Yes” if and only if the answer for the
constructed instance of MLCA is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a clique in $G$ of size $k^{\prime\prime}\geq k$ and $N^{\prime}$ be the $k^{\prime\prime}\geq k^{\prime}=k$-sized subset of the P1 vertex pair neurons corresponding to
the vertices in $V^{\prime}$. Let $M^{\prime}$ be the version of $M$ in which all
neurons in $N^{\prime}$ are ablated. As each of these vertex pair neurons
previously forced their associated vertex regulator
neurons to output 0 courtesy of their connection-weight of $-2$,
their ablation now allows these $k^{\prime\prime}$ vertex regulator neurons to
output 1. As $V^{\prime}$ is a clique of size $k^{\prime\prime}$,
exactly $k^{\prime\prime}(k^{\prime\prime}-1)/2\geq k(k-1)/2$ edge neurons in $M^{\prime}$ receive
the requisite inputs of 1 on both of their endpoints from the vertex
regulator neurons associated with the P1 vertex pair neurons in $N^{\prime}$.
This in turn ensures the output neuron produces output 1. Hence,
$M(I)=0\neq 1=M^{\prime}(I)$.

: Let $N^{\prime}$ be a subset of $N$ of size at most $k^{\prime}=k$
such that for the MLP $M^{\prime}$ induced by ablating all neurons in $N^{\prime}$,
$M(I)\neq M(I^{\prime})$. As $M(I)=0$ and circuit
outputs are stepped to be Boolean, $M^{\prime}(I)=1$. Given the bias of the
output neuron, this can only occur if at least $k(k-1)/2$ edge
neurons in $M^{\prime}$ have output 1 on input $I$, which requires that each
of these neurons receives 1 from both of its endpoint vertex
regulator neurons. These vertex regulator neurons can
only output 1 if all of their associated P1 vertex neurons have
been ablated; moreover, there must be exactly
$k$ such neurons. This means that the vertices in
$G$ corresponding to the P1 vertex pair neurons in $N^{\prime}$ must form a
clique of size $k$ in $G$.

As Clique is $NP$-hard (Garey & Johnson, ), the reduction above establishes
that MLCA is also $NP$-hard. The result follows from the definition of
$NP$-hardness.
∎

###### Theorem 40 .

If $\langle cd,\#n_{in}.\#n_{out},W_{\max},B_{\max},k\rangle$-MLCA is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MLCA constructed in the reduction in the proof of Theorem 39, $\#n_{in}=\#n_{out}=W_{\max}=1$, $cd=5$, and $B_{\max}$ and $k$ are function of $k$ in the given instance of Clique. The result then follows from the fact that $\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 41 .

$\langle\#n_{tot}\rangle$-MLCA is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates every possible subset $N^{\prime}$ of size
at most $k$ of the neurons $N$ in MLP $M$ and for each such subset, creates
the MLP $M^{\prime}$ induced from $M$ by ablating the neurons in $N^{\prime}$ and
(assuming $M^{\prime}$ is active) checks if $M^{\prime}(I)\neq M(I)$. If such a subset is
found, return “Yes”; otherwise, return “No”. The number of possible
subsets $N^{\prime}$ is at most $k\times\#n_{tot}^{k}\leq\#n_{tot}\times\#n_{tot}^{\#n_{tot}}$. As any such $M^{\prime}$ can be generated from $M$, checked
or activity, and run on $I$ in time polynomial in the size of the given
instance of MLCA, the above is a fixed-parameter tractable
algorithm for MLCA relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 42 .

$\langle cw,cd\rangle$-MLCA is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 41 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 40–42
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MLCA relative
to many subsets of the parameters listed in Table 8.

Let us now consider the polynomial-time cost approximability of MLCA. As
MLCA is a minimization problem, we cannot do this using reductions from a
maximization problem like Clique. Hence we will instead use a
reduction from another minimization problem, namely DS.

###### Theorem 43 .

If MLCA is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from DS to MLCA.
Given an instance $\langle G=(V,E),k\rangle$ of DS, construct the following
instance $\langle M,I,k^{\prime}\rangle$ of MLCA:
Let $M$ be an MLP based on $\#n_{tot,g}=3|V|+1$ neurons spread
across four layers:

- 1.
Input layer: The input vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$, all of which have bias 1.
- 2.
Hidden vertex neighbourhood layer I: The vertex neighbourhood AND neurons $nvnA_{1},nvnA_{2},\ldots nvnA_{|V|}$, where $nvnA_{i}$ is an $x$-way AND ReLU gates such that $x=|N_{C}(v_{i})|$.
- 3.
Hidden vertex neighbourhood layer II: The vertex neighbourhood NOT neurons $nvnN_{1},nvnN_{2},\ldots nvnN_{|V|}$, all of which are NOT ReLU gates.
- 4.
Output layer: The single output neuron $n_{out}$, which is a
$|V|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected
to its input line with weight 0 and to each vertex neighbourhood AND
neuron $nvnA_{j}$ such that $v_{i}\in N_{C}(v_{j})$ with weight 1.
- •
Each vertex neighbourhood AND neuron $nvnA_{i}$, $1\leq i\leq|V|$, is
connected to its corresponding vertex neighbourhood NOT neuron
$nvnN_{i}$ with weight 1.
- •
Each vertex neighbourhood NOT neuron $nvnN_{i}$, $1\leq i\leq|V|$, is
connected to the output neuron $n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I$ be the $|V|$-length one-vector and $k^{\prime}=k$. Observe that
this instance of MLCA can be created in time polynomial in the size of the
given instance of DS, Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as
follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nv_{1}(1),nv_{2}(1),\ldots nv_{|V|}(1)$ |
| 2 | $nvnA_{1}(1),nvnA_{2}(1),\ldots nvnA_{|V|}(1)$ |
| 3 | $nvnN_{1}(0),nvnN_{2}(0),\ldots nvnN_{|V|}(0)$ |
| 4 | $n_{out}(0)$ |

We now need to show the correctness of this reduction by proving that the answer
for the given instance of DS is “Yes” if and only if the answer for the
constructed instance of MLCA is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a dominating set in $G$ of size $k$ and $N^{\prime}$ be the $k^{\prime}=k$-sized subset of the input vertex neurons in $M$ corresponding
to the vertices in $V^{\prime}$. Create MLP $M^{\prime}$ by ablated in $M$ the
neurons in $N^{\prime}$. As $V^{\prime}$ is
a dominating set, each vertex neighbourhood AND neuron in $M^{\prime}$ is
missing a i-input from at least one input vertex neuron in $N^{\prime}$,
which in turn ensures that each vertex neighbourhood AND neuron
in $M^{\prime}$ has output 0. This in turn ensures that $M$ produces output
1 on input $I$ such that $M(I)=0\neq 1=M^{\prime}(I)$.

: Let $N^{\prime}$ be a $k^{\prime\prime}\leq k^{\prime}=k$-sized subset of the
set $N$ of neurons in $M$ whose ablation in $M$ creates an MLP $M^{\prime}$
such that $M(I)=0\neq M^{\prime}(I)$. As all MLP outputs are stepped
to be Boolean, this implies that $M^{\prime}(I)=1$. This can only happen
if all vertex neighbourhood NOT neurons output 1, which in turn can
happen only if all vertex neighbourhood AND gates output 0. As
$I=1^{|V|}$, this can only happen if for each vertex neighbourhood
AND neuron, at least one input vertex neuron previously producing a
1-input to that vertex neighbourhood AND neuron has been ablated in
creating $M^{\prime}$. This in turn implies that the $k^{\prime\prime}$ vertices in
$G$ corresponding to the elements of $N^{\prime}$ form a dominating set of
size $k^{\prime\prime}\leq k$ for $G$.

As DS is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MLCA is
also $NP$-hard. The result follows from the definition of $NP$-hardness.
∎

###### Theorem 44 .

If MLCA has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then
$FPT=W[1]$.

###### Proof.

Recall from the proof of correctness of the reduction in the proof of
Theorem 43 that a given instance of DS has a dominating set of size $k$ if and only if the constructed instance of MLCA has a subset $N^{\prime}$ of size $k^{\prime}=k$ of the neurons in given MLP $M$ such that the ablation in $M$ of the neurons in $N^{\prime}$ creates an MLP $M^{\prime}$ such that $M(I)\neq M^{\prime}(I)$.
This implies that, given a polynomial-time $c$-approximation algorithm $A$ for MLCA for some constant $c>0$, we can create a polynomial-time $c$-approximation algorithm for DS by applying the reduction to the given instance $x$ of DS to construct an instance $x^{\prime}$ of MLCA, applying $A$ to $x^{\prime}$ to create an approximate solution $y^{\prime}$, and then using $y^{\prime}$ to create an approximate solution $y$ for $x$ that has the same cost as $y^{\prime}$.
The result then follows from Chen & Lin , Corollary 2, which implies that if DS has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then $FPT=W[1]$.
∎

Note that this theorem also renders MLCA PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 39 .

###### Proof.

###### Theorem 40 .

###### Proof.

###### Theorem 41 .

###### Proof.

###### Theorem 42 .

###### Proof.

###### Theorem 43 .

###### Proof.

###### Theorem 44 .

###### Proof.

##### H.1.2 Results for MGCA

Membership in in $\Sigma^{p}_{2}$ can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]\ \forall[\mathbf{x}\in\{0,1\}^{\#n_{ in}}]:[\mathcal{M}\setminus\mathcal{S}](\mathbf{x})\neq\mathcal{M}(\mathbf{x})$ $$

###### Theorem 45 .

If MGCA is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLCA constructed by the reduction in the
proof of Theorem 39, the input-connection weight 0 and
bias 1 of the input neuron force this neuron to output 1 for
both of the possible input vectors $(1)$ and $(0)$.
Hence, with slight modifications to the proof
of reduction correctness, this reduction also establishes the
$NP$-hardness of MGCA.
∎

###### Theorem 46 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MGCA is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MGCA constructed in the reduction in the
proof of Theorem 45, $\#n_{in}=\#n_{out}=W_{\max}=1$,
$cd=5$, and $B_{\max}$ and $k$ are function of $k$ in the given instance
of Clique. The result then follows from the fact that
$\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 47 .

$\langle\#n_{tot}\rangle$-MGCA is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 41 such
that each created MLP $M$ is checked to ensure that $M(I)\neq M^{\prime}(I)$ for
every possible Boolean input vector of length $\#n_{in}$. As the number of
such vectors is $2^{\#n_{in}}\leq 2^{\#n_{tot}}$,
the above is a fixed-parameter tractable
algorithm for MGCA relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 48 .

$\langle cw,cd\rangle$-MGCA is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 47 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 46–48
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MGCA relative
to many subsets of the parameters listed in Table 8.

Let us now consider the polynomial-time cost approximability of MGCA. As
MGCA is a minimization problem, we cannot do this using reductions from a
maximization problem like Clique. Hence we will instead use a
reduction from another minimization problem, namely DS.

###### Theorem 49 .

If MGCA is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLCA constructed by the reduction in the
proof of Theorem 43, the input-connection weight 0 and
bias 1 of the vertex input neurons force each such neuron to output 1 for
input value 0 or 1.
Hence, with slight modifications to the proof
of reduction correctness, this reduction also establishes the
$NP$-hardness of MGCA.
∎

###### Theorem 50 .

If MGCA has a polynomial-time $c$-approximation algorithm for any constant
$c>0$ then $FPT=W[1]$.

###### Proof.

As the reduction in the proof of Theorem 49 is essentially
the same as the reduction in the proof of Theorem 43, the
result follows by the same reasoning as given in the proof of Theorem
44.
∎

Note that this theorem also renders MGCA PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 45 .

###### Proof.

###### Theorem 46 .

###### Proof.

###### Theorem 47 .

###### Proof.

###### Theorem 48 .

###### Proof.

###### Theorem 49 .

###### Proof.

###### Theorem 50 .

###### Proof.

#### H.2 Results for Minimal Circuit Clamping

Towards proving NP-completeness, we first prove membership and then follow up with hardness.
Membership in NP can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]:\mathcal{M}_{\mathcal{S}}(\mathbf{x}) \neq\mathcal{M}(\mathbf{x})$ $$

The following hardness results are notable for holding
when the given MLP $M$ has only one hidden layer.

##### H.2.1 Results for MLCC

###### Theorem 51 .

If MLCC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from Clique to MLCC. Given an
instance $\langle G=(V,E),k\rangle$ of Clique, construct the following
instance $\langle M,I,val,k^{\prime}\rangle$ of MLCC:
Let $M$ be an MLP based on $\#n_{tot}=|V|+|E|+1$ neurons spread
across three layers:

- 1.
Input vertex layer: The vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$
(all with bias $-2$).
- 2.
Hidden edge layer: The edge neurons $ne_{1},ne_{2},\ldots ne_{|E|}$
(all with bias $-1$).
- 3.
Output layer: The single output neuron $n_{out}$ (bias $-(k(k-1)/2-1)$).

Note that this MLP has only one hidden layer.
The non-zero weight connections between adjacent layers are as follows:

- •
Each vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected to each edge neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge neuron $ne_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=0^{\#n_{in}})$, $val=1$, and $k^{\prime}=k$.
Observe that this instance of MLCC can be created in time polynomial in the size of the
given instance of Clique. Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nv_{1}(0),nv_{2}(0),\ldots nv_{|V|}(0)$ |
| 2 | $ne_{1}(0),ne_{2}(0),\ldots ne_{|E|}(0)$ |
| 3 | $n_{out}(0)$ |

We now need to show the correctness of this reduction by proving that the answer
for the given instance of Clique is “Yes” if and only if the answer for the
constructed instance of MLCC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a clique in $G$ of size $k^{\prime\prime}\geq k$ and $N^{\prime}$ be the $k^{\prime\prime}\geq k^{\prime}=k$-sized
subset of the input vertex neurons corresponding to the vertices in
$V^{\prime}$. Let $M^{\prime}$ be the version of $M$ in which all neurons in $N^{\prime}$
are clamped to value $val=1$. As $V^{\prime}$ is a clique of size $k^{\prime\prime}$,
exactly $k^{\prime\prime}(k^{\prime\prime}-1)/2\geq k(k-1)/2$ edge neurons in $M^{\prime}$ receive
the requisite inputs of 1 on both of their endpoints from the vertex
neurons in $N^{\prime}$. This in turn ensures the output
neuron produces output 1. Hence, $M(I)=0\neq 1=M^{\prime}(I)$.

: Let $N^{\prime}$ be a subset of $N$ of size at most $k^{\prime}=k$
such that for the MLP $M^{\prime}$ induced by clamping all neurons in $N^{\prime}$
to value $val=1$, $M(I)\neq M(I^{\prime})$. As $M(I)=0$ and circuit
outputs are stepped to be Boolean, $M^{\prime}(I)=1$. Given the bias of the
output neuron, this can only occur if at least $k(k-1)/2$ edge
neurons in $M^{\prime}$ have output 1 on input $I$, which requires that each
of these neurons receives 1 from both of its endpoint vertex neurons.
As $I=0^{\#n_{in}}$, these 1-inputs could only have come from
the clamped vertex neurons in $N^{\prime}$; moreover, there must be exactly
$k$ such neurons. This means that the vertices in
$G$ corresponding to the vertex neurons in $N^{\prime}$ must form a
clique of size $k$ in $G$.

As Clique is $NP$-hard (Garey & Johnson, ), the reduction above establishes
that MLCC is also $NP$-hard. The result follows from the definition of
$NP$-hardness.
∎

###### Theorem 52 .

If $\langle cd,\#n_{out},W_{\max},B_{\max},k\rangle$-MLCC is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MLCC constructed in the reduction in the
proof of Theorem 51, $\#n_{out}=W_{\max}=1$, $cd=3$, and
$B_{\max}$ and $k$ are function of $k$ in the given instance of
Clique. The result then follows from the fact that
$\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 53 .

$\langle\#n_{tot}\rangle$-MLCC is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates every possible subset $N^{\prime}$ of size
at most $k$ of the neurons $N$ in MLP $M$ and for each such subset, creates
the MLP $M^{\prime}$ induced from $M$ by clamping the neurons in $N^{\prime}$ to $val$ and
checks if $M^{\prime}(I)\neq M(I)$. If such a subset is found, return
“Yes”; otherwise, return “No”. The number of possible subsets
$N^{\prime}$ is at most $k\times\#n_{tot}^{k}\leq\#n_{tot}\times\#n_{tot}^{\#n_{tot}}$. As any such $M^{\prime}$ can be
generated from $M$ and $M^{\prime}$ can be run on $I$ in time polynomial in the
size of the given instance of MLCC, the above is a fixed-parameter tractable
algorithm for MLCC relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 54 .

$\langle cw,cd\rangle$-MLCC is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 53 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 52–54
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MLCC relative
to many subsets of the parameters listed in Table 8.

Let us now consider the polynomial-time cost approximability of MLCC. As
MLCC is a minimization problem, we cannot do this using reductions from a
maximization problem like Clique. Hence we will instead use a
reduction from another minimization problem, namely DS.

###### Theorem 55 .

If MLCC is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from DS to MLCC.
Given an instance $\langle G=(V,E),k\rangle$ of DS, construct the following
instance $\langle M,I,val,k^{\prime}\rangle$ of MLCC:
Let $M$ be an MLP based on $\#n_{tot,g}=3|V|+1$ neurons spread
across four layers:

- 1.
Input layer: The input vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$, all of which have bias 1.
- 2.
Hidden vertex neighbourhood layer I: The vertex neighbourhood AND neurons $nvnA_{1},nvnA_{2},\ldots nvnA_{|V|}$, where $nvnA_{i}$ is an $x$-way AND ReLU gates such that $x=|N_{C}(v_{i})|$.
- 3.
Hidden vertex neighbourhood layer II: The vertex neighbourhood NOT neurons $nvnN_{1},nvnN_{2},\ldots nvnN_{|V|}$, all of which are NOT ReLU gates.
- 4.
Output layer: The single output neuron $n_{out}$, which is a
$|V|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected
to its input line with weight 0 and to each vertex neighbourhood AND
neuron $nvnA_{j}$ such that $v_{i}\in N_{C}(v_{j})$ with weight 1.
- •
Each vertex neighbourhood AND neuron $nvnA_{i}$, $1\leq i\leq|V|$, is
connected to its corresponding vertex neighbourhood NOT neuron
$nvnN_{i}$ with weight 1.
- •
Each vertex neighbourhood NOT neuron $nvnN_{i}$, $1\leq i\leq|V|$, is
connected to the output neuron $n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I$ be the $|V|$-length one-vector, $val=0$, and $k^{\prime}=k$.
Observe that this instance of MLCC can be created in time polynomial in
the size of the given instance of DS, Moreover, the output behaviour of the
neurons in $M$ from the presentation of input $I$ until the output is
generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nvN_{1}(1),nvN_{2}(1),\ldots nvN_{|V|}(1)$ |
| 2 | $nvnA_{1}(1),nvnA_{2}(1),\ldots nvnA_{|V|}(1)$ |
| 3 | $nvnN_{1}(0),nvnN_{2}(0),\ldots nvnN_{|V|}(0)$ |
| 4 | $n_{out}(0)$ |

We now need to show the correctness of this reduction by proving that the
answer for the given instance of DS is “Yes” if and only if the answer
for the constructed instance of MLCC is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a dominating set in $G$ of size $k$ and $N^{\prime}$ be the $k^{\prime}=k$-sized subset of the input vertex neurons in $M$ corresponding
to the vertices in $V^{\prime}$. Create MLP $M^{\prime}$ by clamping in $M$ the
neurons in $N^{\prime}$ to $val=0$. As $V^{\prime}$ is
a dominating set, each vertex neighbourhood AND neuron in $M^{\prime}$ is
now missing a i-input from at least one input vertex neuron in $N^{\prime}$,
which in turn ensures that each vertex neighbourhood AND neuron
in $M^{\prime}$ has output 0. This in turn ensures that $M$ produces output
1 on input $I$ such that $M(I)=0\neq 1=M^{\prime}(I)$..

: Let $N^{\prime}$ be a $k^{\prime\prime}\leq k^{\prime}=k$-sized subset of the
set $N$ of neurons in $M$ whose clamping to $val=0$ in $M$
creates an MLP $M^{\prime}$ such that $M(I)=0\neq M^{\prime}(I)$. As all
MLP outputs are stepped to be Boolean, this implies that $M^{\prime}(I)=1$. This can only happen if
all vertex neighbourhood NOT neurons output 1, which in turn can
happen only if all vertex neighbourhood AND gates output 0. As
$I=1^{|V|}$, this can only happen if for each vertex neighbourhood
AND neuron, at least one input vertex neuron previously producing a
1-input to that vertex neighbourhood AND neuron has been clamped to
0 in creating $M^{\prime}$. This in turn implies that the $k^{\prime\prime}$ vertices in
$G$ corresponding to the elements of $N^{\prime}$ form a dominating set of
size $k^{\prime\prime}\leq k$ for $G$.

As DS is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MLCC
is also $NP$-hard. The result follows from the definition of
$NP$-hardness.
∎

###### Theorem 56 .

If MLCC has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then
$FPT=W[1]$.

###### Proof.

Recall from the proof of correctness of the reduction in the proof of
Theorem 55 that a given instance of DS has a dominating set
of size $k$ if and only if the constructed instance of MLCC has a subset
$N^{\prime}$ of size $k^{\prime}=k$ of the neurons in given MLP $M$ such that the
clamping to $val=0$ in $M$ of the neurons in $N^{\prime}$ creates an MLP $M^{\prime}$
such that $M(I)\neq M^{\prime}(I)$. This implies
that, given a polynomial-time $c$-approximation algorithm $A$ for MLCC for
some constant $c>0$, we can create a polynomial-time $c$-approximation
algorithm for DS by applying the reduction to the given instance $x$ of DS
to construct an instance $x^{\prime}$ of MLCC, applying $A$ to $x^{\prime}$ to create an
approximate solution $y^{\prime}$, and then using $y^{\prime}$ to create an approximate
solution $y$ for $x$ that has the same cost as $y^{\prime}$. The result then
follows from Chen & Lin , Corollary 2, which implies that if DS has a
polynomial-time $c$-approximation algorithm for any constant $c>0$ then
$FPT=W[1]$.
∎

Note that this theorem also renders MLCC PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 51 .

###### Proof.

###### Theorem 52 .

###### Proof.

###### Theorem 53 .

###### Proof.

###### Theorem 54 .

###### Proof.

###### Theorem 55 .

###### Proof.

###### Theorem 56 .

###### Proof.

##### H.2.2 Results for MGCC

Membership in in $\Sigma^{p}_{2}$ can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]\ \forall[\mathbf{x}\in\{0,1\}^{\#n_{ in}}]:\mathcal{M}_{\mathcal{S}}(\mathbf{x})\neq\mathcal{M}(\mathbf{x})$ $$

###### Theorem 57 .

If MGCC is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLCC constructed by the reduction in the
proof of Theorem 51, the biases of $-2$ in the input vertex
neurons force these neurons to map any given Boolean input vector
onto $0^{\#n_{in}}$. Hence, with slight modifications to the proof
of reduction correctness, this reduction also establishes the
$NP$-hardness of MGCC.
∎

###### Theorem 58 .

If $\langle cd,\#n_{out},W_{\max},B_{\max},k\rangle$-MGCC is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MGCC constructed in the reduction in the
proof of Theorem 57, $\#n_{out}=W_{\max}=1$, $cd=3$, and
$B_{\max}$ and $k$ are function of $k$ in the given instance of
Clique. The result then follows from the fact that
$\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 59 .

$\langle\#n_{tot}\rangle$-MLCC is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 53 such
that each created MLP $M$ is checked to ensure that $M(I)\neq M^{\prime}(I)$ for
every possible Boolean input vector of length $\#n_{in}$. As the number of
such vectors is $2^{\#n_{in}}\leq 2^{\#n_{tot}}$,
the above is a fixed-parameter tractable
algorithm for MGCC relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 60 .

$\langle cw,cd\rangle$-MGCC is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 59 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Observe that the results in Theorems 58–60
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MGCC relative
to many subsets of the parameters listed in Table 8.

Let us now consider the polynomial-time cost approximability of MGCC. As
MGCC is a minimization problem, we cannot do this using reductions from a
maximization problem like Clique. Hence we will instead use a
reduction from another minimization problem, namely DS.

###### Theorem 61 .

If MGCC is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLCC constructed by the reduction in the
proof of Theorem 55, the input-connection weight 0 and
bias 1 of the vertex input neurons force each such neuron to output 1 for
input value 0 or 1. Hence, with slight modifications to the proof
of reduction correctness, this reduction also establishes the
$NP$-hardness of MGCC.
∎

###### Theorem 62 .

If MGCC has a polynomial-time $c$-approximation algorithm for any constant
$c>0$ then $FPT=W[1]$.

###### Proof.

As the reduction in the proof of Theorem 61 is essentially
the same as the reduction in the proof of Theorem 55, the
result follows by the same reasoning as given in the proof of Theorem
56.
∎

Note that this theorem also renders MGCC PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 57 .

###### Proof.

###### Theorem 58 .

###### Proof.

###### Theorem 59 .

###### Proof.

###### Theorem 60 .

###### Proof.

###### Theorem 61 .

###### Proof.

###### Theorem 62 .

###### Proof.

### Appendix I Circuit Patching Problem

Minimum local circuit patching (MLCP)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
Boolean input vectors $x$ and $y$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq(\#n_{tot}-(\#n_{in}+\#n_{out}))$.
Question: Is there a subset $C$, $|C|\leq k$, of the internal neurons
in $M$ such that for the MLP $M^{\prime}$ created when $M$ is
$y$-patched wrt $C$, i.e., $M^{\prime}$ is created when $M/C$ is
patched with activations from $M(x)$ and $C$ is patched with
activations from $M(y)$, $M^{\prime}(x)=M(y)$?

Minimum Global Circuit Patching (MGCP)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
Boolean input vector $y$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq(\#n_{tot}-(\#n_{in}+\#n_{out}))$.
Question: Is there a subset $C$, $|C|\leq k$, of the internal neurons
in $M$ such that, for all possible input vectors x, for the
MLP $M^{\prime}$ created when $M$ is
$y$-patched wrt $C$, i.e., $M^{\prime}$ is created when $M/C$ is
patched with activations from $M(x)$ and $C$ is patched with
activations from $M(y)$, $M^{\prime}(x)=M(y)$?

Following Barceló et al. , page 4, all
neurons in $M$ use the ReLU activation function and the output $x$ of each
output neuron is stepped as necessary to be Boolean, i.e, $step(x)=0$ if
$x\leq 0$ and is $1$ otherwise.

For a graph $G=(V,E)$, we shall assume an ordering on the vertices and edges in $V$
and $E$, respectively. For each vertex $v\in V$, let the complete neighbourhood $N_{C}(v)$ of $v$ be the set
composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$
by a single edge, i.e., $v\cup\{u~{}|~{}u~{}\in V~{}\rm{and}~{}(u,v)\in E\}$.

We will prove various classical and parameterized results for MLCP and MGCP
using
reductions from Dominating Set. The parameterized results are proved relative to the
parameters in Table 9. Our reductions (Theorems
63 and 67)
uses specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

**Table 9: Parameters for the minimum circuit patching problem.**
| Parameter | Description |
| --- | --- |
| $cd$ | # layers in given MLP |
| $cw$ | max # neurons in layer in given MLP |
| $\#n_{tot}$ | total # neurons in given MLP |
| $\#n_{in}$ | # input neurons in given MLP |
| $\#n_{out}$ | # output neurons in given MLP |
| $B_{\max}$ | max neuron bias in given MLP |
| $W_{\max}$ | max connection weight in given MLP |
| $k$ | Size of requested patching-subset of $M$ |

#### I.1 Results for MLCP

Towards proving NP-completeness, we first prove membership and then follow up with hardness.
Membership in NP can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]:\mathcal{M}_{\mathcal{S}}(\mathbf{x}) =\mathcal{M}(\mathbf{y})$ $$

###### Theorem 63 .

If MLCP is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from DS to MLCP adapted from the reduction from DS to MSR in Theorem 103.
Given an instance $\langle G=(V,E),k\rangle$ of DS, construct the following instance $\langle M,x,y,k^{\prime}\rangle$
of MLCP: Let $M$ be an MLP based on $\#n_{tot}=4|V|+1$ neurons spread
across five layers:

- 1.
Input layer: The input vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$, all of which have bias 0.
- 2.
Hidden vertex layer: The hidden vertex neurons $nhv_{1},nhv_{2},\ldots nhv_{|V|}$, all of which are identity ReLU gates with bias 0.
- 3.
Hidden vertex neighbourhood layer I: The vertex neighbourhood AND neurons $nvnA_{1},nvnA_{2},\ldots nvnA_{|V|}$, where $nvnA_{i}$ is an $x$-way AND ReLU gates such that $x=|N_{C}(v_{i})|$.
- 4.
Hidden vertex neighbourhood layer II: The vertex neighbourhood NOT neurons $nvnN_{1},nvnN_{2},\ldots nvnN_{|V|}$, all of which are NOT ReLU gates.
- 5.
Output layer: The single output neuron $n_{out}$, which is a
$|V|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected
to its associated hidden vertex neuron $nhv_{i}$ with weight 1.
- •
Each hidden vertex neuron $nhv_{i}$, $1\leq i\leq|V|$, is connected
to each vertex neighbourhood AND neuron $nvnA_{j}$ such that $v_{i}\in N_{C}(v_{j})$ with weight 1.
- •
Each vertex neighbourhood AND neuron $nvnA_{i}$, $1\leq i\leq|V|$, is
connected to its corresponding vertex neighbourhood NOT neuron
$nvnN_{i}$ with weight 1.
- •
Each vertex neighbourhood NOT neuron $nvnN_{i}$, $1\leq i\leq|V|$, is
connected to the output neuron $n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $x$ and $y$ be the $|V|$-length one- and zero-vectors and
$k^{\prime}=k$. Observe that this instance of MLCP can be created in time
polynomial in the size of the given instance of DS, Moreover, the output
behaviour of the neurons in $M$ from the presentation of input $x$ until
the output is generated is

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nv_{1}(1),nv_{2}(1),\ldots nv_{|V|}(1)$ |
| 2 | $nhv_{1}(1),nhv_{2}(1),\ldots nhv_{|V|}(1)$ |
| 3 | $nvnA_{1}(1),nvnA_{2}(1),\ldots nvnA_{|V|}(1)$ |
| 4 | $nvnN_{1}(0),nvnN_{2}(0),\ldots nvnN_{|V|}(0)$ |
| 5 | $n_{out}(0)$ |

and the output behaviour of the neurons in $M$ from the presentation of
input $y$ until the output is generated is

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nv_{1}(0),nv_{2}(0),\ldots nv_{|V|}(0)$ |
| 2 | $nhv_{1}(0),nhv_{2}(0),\ldots nhv_{|V|}(0)$ |
| 3 | $nvnA_{1}(0),nvnA_{2}(0),\ldots nvnA_{|V|}(0)$ |
| 4 | $nvnN_{1}(1),nvnN_{2}(1),\ldots nvnN_{|V|}(1)$ |
| 5 | $n_{out}(1)$ |

We now need to show the correctness of this reduction by proving that the answer
for the given instance of DS is “Yes” if and only if the answer for the
constructed instance of MLCP is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a dominating set in $G$ of size $k$ and $C$ be the $k^{\prime}=k$-sized
subset of the hidden vertex neurons in $M$ corresponding to the
vertices in $V^{\prime}$. As $V^{\prime}$ is
a dominating set, each vertex neighbourhood AND neuron receives
input 0 from at least one hidden vertex neuron in $C$ when
$M$ is $y$-patched wrt $C$. This ensures that each
vertex neighbourhood AND neuron has output 0, which in turn
ensures that each vertex neighbourhood NOT neuron has output
1 and for $M^{\prime}$ created by $y$-patching $M$ wrt $C$, $M^{\prime}(x)=M(y)=1$.

: Let $C$ be a $k^{\prime}=k$-sized subset of the internal
neurons of $M$ such that when $M^{\prime}$ is created by $y$-patching $M$
wrt $C$, $M^{\prime}(x)=M(y)=1$. The output of $M^{\prime}$ on $X$ can be 1 (and
hence equal to the output of $M$ on $y$) only if
all vertex neighbourhood NOT neurons output 1, which in turn can
happen only if all vertex neighbourhood AND gates output 0. However,
as all elements of $x$ have value 1, this means that
each vertex neighbourhood AND neuron must be connected to
at least one patched hidden vertex neuron (all of which have
output 0 courtesy of $y$), which in turn implies that the
$k^{\prime}=k$ vertices in $G$ corresponding to the patched hidden
vertex neurons in $C$ form a dominating set of size $k$ for $G$.

As DS is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MLCP is
also $NP$-hard. The result follows from the definition of $NP$-hardness.
∎

###### Theorem 64 .

If $\langle cd,\#n_{out},W_{\max},B_{\max},k\rangle$-MLCP is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MLCP constructed in the reduction in the
proof of Theorem 63, $\#n_{out}=W_{\max}=1$, $cd=4$, and
$B_{\max}$ and $k$ are function of $k$ in the given instance of
DS. The result then follows from the facts that
$\langle k\rangle$-DS is $W[2]$-hard (Downey & Fellows, ) and $W[1]\subseteq W[2]$.
∎

###### Theorem 65 .

$\langle\#n_{tot}\rangle$-MLCP is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates all possible subset $C$ of the
internal neurons in $M$ and for each such subset, checks if $M^{\prime}$ created
by $y$-patching $M$ wrt $C$ is such that $M^{\prime}(x)=M(y)$. If such a $C$ is
found, return “Yes”; otherwise, return “No”. The number of possible
subsets $C$ is at most $2^{(\#n_{tot}}$. Given this, as $M$ can be patched
relative to $C$ and run on $x$ and $y$ in time polynomial in the size of the
given instance of MLCP, the above is a fixed-parameter tractable algorithm
for MLCP
relative to parameter-set $\{\#n_{tot}\}$.
∎

Observe that the results in Theorems 64 and 65
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MLCP relative
to many subset of the parameters listed in Table 9.

Let us now consider the polynomial-time cost approximability of MLCP.

###### Theorem 66 .

If MLCP has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then
$FPT=W[1]$.

###### Proof.

Recall from the proof of correctness of the reduction in the proof of
Theorem 63 that a given instance of DS has a dominating set
of size $k$ if and only if the constructed instance of $MLCP$ has a subset
$C$ of the internal neurons in $M$ of size $k^{\prime}=k$ such that for the MLP
$M^{\prime}$ created from $M$ by $y$-patching $M$ wrt $C$, $M^{\prime}(x)=M(y)$ This
implies that, given a polynomial-time $c$-approximation algorithm $A$ for
MLCP for some constant $c>0$, we can create a polynomial-time
$c$-approximation algorithm for DS by applying the reduction to the given
instance $I$ of DS to construct an instance $I^{\prime}$ of MLCP, applying $A$ to
$I^{\prime}$ to create an approximate solution $S^{\prime}$, and then using $S^{\prime}$ to create
an approximate solution $S$ for $I$ that has the same cost as $S^{\prime}$. The
result then follows from Chen & Lin , Corollary 2, which implies that if
DS has a polynomial-time $c$-approximation algorithm for any constant
$c>0$ then $FPT=W[1]$.
∎

Note that this theorem also renders MLCP PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 63 .

###### Proof.

###### Theorem 64 .

###### Proof.

###### Theorem 65 .

###### Proof.

###### Theorem 66 .

###### Proof.

#### I.2 Results for MGCP

Membership in in $\Sigma^{p}_{2}$ can be proven via the definition of the polynomial hierarchy and the following alternating quantifier formula:

$$ $\exists[\mathcal{S}\subseteq\mathcal{M}]\ \forall[\mathbf{x}\in\{0,1\}^{\#n_{ in}}]:\mathcal{M}_{\mathcal{S}}(\mathbf{x})=\mathcal{M}(\mathbf{y})$ $$

###### Theorem 67 .

If MGCP is polynomial-time tractable then $P=NP$.

###### Proof.

Modify the reduction in the proof of Theorem 63 such that
each hidden vertex neuron has input weight 0 and bias 1; this will force
all hidden vertex neurons to output 1 for all input vectors $x$ instead of
just when $x$ is the all-one vector.
Hence, with slight modifications to the proof
of reduction correctness for the reduction in the proof of Theorem
63, this modified reduction establishes the
$NP$-hardness of MGCP.
∎

###### Theorem 68 .

If $\langle cd,\#n_{out},W_{\max},B_{\max},k\rangle$-MGCP is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MGCP constructed in the reduction in the
proof of Theorem 67, $\#n_{out}=W_{\max}=1$, $cd=4$, and
$B_{\max}$ and $k$ are function of $k$ in the given instance of
DS. The result then follows from the facts that
$\langle k\rangle$-DS is $W[2]$-hard (Downey & Fellows, ) and $W[1]\subseteq W[2]$.
∎

###### Theorem 69 .

$\langle\#n_{tot}\rangle$-MGCP is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 65 such that
each circuit $M^{\prime}$ created by $y$-patching $M$ is checked to ensure that
$M^{\prime}(x)=M(y)$ for every possible Boolean input vector $x$ of length
$\#n_{in}$. As the number of such vectors is $2^{\#n_{in}}<2^{\#n_{tot}}$,
the above is a fixed-parameter tractable
algorithm for MGCP relative to parameter-set $\{\#n_{tot}\}$.
∎

Observe that the results in Theorems 68 and 69
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MGCP relative
to many subset of the parameters listed in Table 9.

Let us now consider the polynomial-time cost approximability of MGCP.

###### Theorem 70 .

If MGCP has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then
$FPT=W[1]$.

###### Proof.

As the reduction in the proof of Theorem 67 is essentially
the same as the reduction in the proof of Theorem 63, the
result follows by the same reasoning as given in the proof of Theorem
66.
∎

Note that this theorem also renders MGCP PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 67 .

###### Proof.

###### Theorem 68 .

###### Proof.

###### Theorem 69 .

###### Proof.

###### Theorem 70 .

###### Proof.

### Appendix J Quasi-Minimal Circuit Patching Problem

Quasi-Minimal Circuit Patching (QMCP)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$, an input vector $\mathbf{y}$ and a set $\mathcal{X}$ of input vectors of length $\#n_{in}$.
Output: a subset $\mathcal{C}$ in $\mathcal{M}$ and a neuron $v\in\mathcal{C}$, such that for the $\mathcal{M}^{*}$ induced by patching $\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{y})$ and $\mathcal{M}\setminus\mathcal{C}$ with activations from $\mathcal{M}(\mathbf{x})$, $\forall_{\mathbf{x}\in\mathcal{X}}:\mathcal{M}^{*}(\mathbf{x})=\mathcal{M}(
\mathbf{y})$, and for $\mathcal{M}^{\prime}$ induced by patching identically except for $v\in\mathcal{C}$, $\exists_{\mathbf{x}\in\mathcal{X}}:\mathcal{M}^{\prime}(\mathbf{x})\neq
\mathcal{M}(\mathbf{y})$.

###### Theorem 71 .

QMCP is in PTIME (i.e., polynomial-time tractable).

###### Proof.

Consider the following algorithm for QMCP.
Build a sequence of MLPs by taking $\mathcal{M}$ with all neurons labeled 0, and generating subsequent $\mathcal{M}_{i}$ in the sequence by labeling an additional neuron with 1 each time (this choice can be based on any heuristic strategy, for instance, one based on gradients).
The first MLP, $\mathcal{M}_{1}$, obtained by patching all neurons labeled 1 (i.e., none) is such that $\mathcal{M}_{1}(x)\neq\mathcal{M}(y)$, and the last $\mathcal{M}_{n}$ is guaranteed to give $\mathcal{M}_{n}(x)=\mathcal{M}(y)$ because all neurons are patched.
Label the first MLP NO, and the last YES.
Perform a variant of binary search on the sequence as follows.
Evaluate the $\mathcal{M_{i}}$ halfway between NO and YES while patching all its neurons labeled 1.
If it satisfies the condition, label it YES, and repeat the same strategy with the sequence starting from the first $\mathcal{M}_{i}$ until the YES just labeled.
If it does not satisfy the condition, label it NO and repeat the same strategy with the sequence starting from the NO just labeled until the YES at the end of the original sequence.
This iterative procedure halves the sequence each time.
Halt when you find two adjacent $\langle\texttt{NO},\texttt{YES}\rangle$ patched networks (guaranteed to exist), and return the patched neuron set of the YES network V and the single neuron difference between YES and NO (the breaking point), $v\in V$.
The complexity of this algorithm is roughly $O(n\log n)$.

∎

###### Theorem 71 .

###### Proof.

### Appendix K Circuit Robustness Problem

###### Definition 17 .

Given an MLP $M$, a subset $H$ of the elements in $M$, an integer $k\leq|H|$, and an input $I$ to $M$, $M$ is $k$-robust relative to
$H$ for $I$ if for each subset $H^{\prime}\subseteq H$, $|H^{\prime}|\leq k$,
$M(I)=(M/H^{\prime})(I)$.

Maximum Local Circuit Robustness (MLCR)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a subset $H$ of the neurons in $M$,
a Boolean input vector $I$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq|H|$.
Question: Is $M$ $k$-robust relative to $H$ for $I$?

Restricted Maximum Local Circuit Robustness (MLCR^∗)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq|M|$.
Question: Is $M$ $k$-robust relative to $H=M$ for $I$?

Maximum Global Circuit Robustness (MGCR)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a subset $H$ of the neurons in $M$, and a
positive integer $k$ such that $1\leq k\leq|H|$.
Question: Is $M$ $k$-robust relative to $H$ for every possible
Boolean input vector $I$ of length $\#n_{in}$?

Restricted Maximum Global Circuit Robustness (MGCR^∗)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
and a positive integer $k$ such that $1\leq k\leq|M|$.
Question: Is $M$ $k$-robust relative to $H=M$ for every possible
Boolean input vector $I$ of length $\#n_{in}$?

Following Barceló et al. , page 4, all
neurons in $M$ use the ReLU activation function and the output $x$ of each
output neuron is stepped as necessary to be Boolean, i.e, $step(x)=0$ if
$x\leq 0$ and is $1$ otherwise.

We will use previous results for Minimum Local/Global Circuit Ablation, Clique and Vertex Cover to prove our
results for the problems above.

For a graph $G=(V,E)$, we shall assume an ordering on the vertices and edges in $V$
and $E$, respectively.

We will prove various classical and parameterized results for MLCR,
MLCR^∗, MGCR, and MGCR^∗. The
parameterized results are proved relative to the parameters in
Table 10. Lemmas 1 and 2 will be useful in deriving additional parameterized results from proved ones.

**Table 10: Parameters for the minimum circuit robustness problem.**
| Parameter | Description | Appl. |
| --- | --- | --- |
| $cd$ | # layers in given MLP | All |
| $cw$ | max # neurons in layer in given MLP | All |
| $\#n_{tot}$ | total # neurons in given MLP | All |
| $\#n_{in}$ | # input neurons in given MLP | All |
| $\#n_{out}$ | # output neurons in given MLP | All |
| $B_{\max}$ | max neuron bias in given MLP | All |
| $W_{\max}$ | max connection weight in given MLP | All |
| $k$ | Requested level of robustness | All |
| $|H|$ | Size of investigated region | M$\{$L,G$\}$CR |

Several of our proofs involve
problems that are hard for $coW[1]$ and $coNP$, the complement
classes of $W[1]$ and $NP$ (Garey & Johnson, , Section 7.1). Given a decision
problem X let co-X be the complement problem in which all
instances answers are switched.

###### Observation 3 .

MLCR^∗ is the complement of MLCA.

###### Proof.

Let $X=\langle M,I,k\rangle$ be a shared input of MLCR^∗ and MLCA. If the
the answer to MLCA on input $X$ is “Yes”, this means that there is a
subset $H$ of size $\leq k$ of the neurons of $M$ that can be ablated
such that $M(I)\neq(M/H)(I)$. This implies that the answer to MLCR^∗
on input $X$ is “No”. Conversely, if the answer to MLCA on input $X$
is “No”, this means that there is no subset $H$ of size $\leq k$ of the
neurons of $M$ that can be ablated such that $M(I)\neq(M/H)(I)$. This
implies that the answer to MLCR^∗ on input $X$ is “Yes’. The
observation follows from the definition of complement problem.
∎

The following lemmas will be of use in
the derivation and interpretation of results involving complement problems
and classes.

###### Lemma 5 .

(Garey & Johnson, , Section 7.1)
Given a decision problem X, if X is $NP$-hard then
co-X is $coNP$-hard.

###### Lemma 6 .

Given a decision problem X, if X is $coNP$-hard and
X is polynomial-time solvable then $P=NP$.

###### Proof.

Suppose decision problem X is $coNP$-hard and solvable in
polynomial-time by algorithm $A$. By the definition
of problem, class hardness, for every problem Y in $coNP$ there is
a polynomial-time many-one reduction $\Pi$ from Y to X; let
$A_{\Pi}$ be the polynomial-time algorithm encoded in $\Pi$. We
can create a polynomial-time algorithm $A^{\prime}$ for co-Y by
running $A_{\Pi}$ on a given input, running $A$, and then complementing
the produced output, i.e., “Yes” $\Rightarrow$ “No” and “No”
$\Rightarrow$ “Yes”. However, as coX is $NP$-hard by Lemma
5, this implies that $P=NP$.
∎

###### Lemma 7 .

(Flum & Grohe, , Lemma 8.23)
Let $\cal{C}$ be a parameterized complexity class. Given a parameterized
decision problem X, if X is $\cal{C}$-hard then
co-X is $co\cal{C}$-hard.

###### Lemma 8 .

Given a parameterized decision problem X, if X is
fixed-parameter tractable then co-X is fixed-parameter tractable.

###### Proof.

Given a fixed-parameter tractable algorithm $A$ for X, we
can create a fixed-parameter tractable algorithm $A^{\prime}$ for co-X by
running $A$ on a given input and then complementing
the produced output, i.e., “Yes” $\Rightarrow$ “No” and “No”
$\Rightarrow$ “Yes”.
∎

###### Lemma 9 .

Given a parameterized decision problem X, if X is
$coW[1]$-hard and fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Suppose decision problem X is $coW[1]$-hard and solvable in
polynomial-time by algorithm $A$. By the definition of problem class
hardness, for every problem Y in $coW[1]$ there is
a parameterized reduction $\Pi$ from Y to X; let
$A_{\Pi}$ be the fixed-parameter tractable algorithm encoded in $\Pi$. We
can create a polynomial-time algorithm $A^{\prime}$ for co-Y by
running $A_{\Pi}$ on a given input, running $A$, and then complementing
the produced output, i.e., “Yes” $\Rightarrow$ “No” and “No”
$\Rightarrow$ “Yes”. However, as coX is $W[1]$-hard by Lemma
7, this implies that $P=NP$.
∎

We will also be deriving polynomial-time inapproximability results for
optimization versions of MLCR, MLCR^∗, MGCR, and MGCR^∗, i.e.,

- •
Max-MLCR, which asks for the maximum value $k$ such that $M$ is
$k$-robust relative to $H$ for $I$.
- •
Max-MLCR^∗, which asks for the maximum value $k$ such that $M$ is
$k$-robust relative to $H=M$ for $I$.
- •
Max-MGCR, which asks for the maximum value $k$ such that $M$ is
$k$-robust relative to $H$ for every possible Boolean input vector
$I$ of length $\#n_{in}$
- •
Max-MGCR^∗, which asks for the maximum value $k$ such that $M$ is
$k$-robust relative to $H=M$ for every possible Boolean input
vector $I$ of length $\#n_{in}$

The derivation of such results is complicated by both the $coNP$-hardness
of the decision versions of these problems (and the scarcity of
inapproximability results for $coNP$-hard problems which one could
transfer to our problems by $L$-reductions) and the fact that the
optimization versions of our problems are evaluation problems that
return numbers rather than graph structures (which makes the use of
instance-copy and gap inapproximability proof techniques
[Garey & Johnson , Chapter 6] extremely difficult). We shall sidestep many
of these issues by deriving our results within the $OptP$ framework for
analyzing evaluation problems developed in Krentel ; Gasarch et al. .
In particular, we shall find the following of use.

###### Definition 18 .

(Adapted from (Krentel, , page 493))
Let $f,g:\Sigma^{*}\rightarrow\mathcal{Z}$. A metric reduction
from $f$ to $g$ is a pair $(T_{1},T_{2})$ of polynomial-time computable
functions where $T_{1}:\Sigma^{*}\rightarrow\Sigma^{*}$ and $T_{2}:\Sigma^{*}\times\mathcal{Z}\rightarrow\mathcal{Z}$ such that $f(x)=T_{2}(x,g(T_{1}(x)))$ for all $x\in\Sigma^{*}$.

###### Lemma 10 .

(Corollary of (Krentel, , Theorem 4.3))
Given an evaluation problem $\Pi$ that is $OptP[O(\log n)]$-hard under
metric reductions, if $\Pi$ has a $c$-additive
approximation algorithm for some $c\in o(poly)$(^3^33 Note that $o(poly)$ is the set of all functions $f$ that are strictly upper bounded by all polynomials of $n$, i.e., $f(n)\leq c\times g(n)$ for $n\geq n_{0}$ for all $c>0$ and $g(n)\in\cup_{k}n^{k}=n^{O(1)}$.)
then $P=NP$.

Some of our metric reductions use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

The hardness (inapproximability) results in this section hold
when the given MLP $M$ has three (six) hidden layers.

###### Definition 17 .

###### Observation 3 .

###### Proof.

###### Lemma 5 .

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Lemma 8 .

###### Proof.

###### Lemma 9 .

###### Proof.

###### Definition 18 .

###### Lemma 10 .

#### K.1 Results for MLCR-special and MLCR

Let us first consider problem MLCR^∗.

###### Theorem 72 .

If MLCR^∗ is polynomial-time tractable then $P=NP$.

###### Proof.

As MLCR^∗ is the complement of MLCA by Observation 3
and MLCA is $NP$-hard by the proof of Theorem 39, Lemma 5 implies that MLCR^∗ is $coNP$-hard. The result then follows from Lemma 6.
∎

###### Theorem 73 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MLCR^∗ is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

The $coW[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MLCR^∗ follows from the $W[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MLCA (Theorem 40),
Observation 3, and Lemma 7. The result
then follows from Lemma 9.
∎

###### Theorem 74 .

$\langle\#n_{tot}\rangle$-MLCR^∗ is fixed-parameter tractable.

###### Proof.

The result follows from the fixed-parameter tractability of
$\langle\#n_{tot}\rangle$-MLCA Theorem 41, Observation
3, and Lemma 8.
∎

###### Theorem 75 .

$\langle cw,cd\rangle$-MLCR^∗ is fixed-parameter tractable.

###### Proof.

The result follows from the fixed-parameter tractability of
$\langle cw,cd\rangle$-MLCA Theorem 42, Observation
3, and Lemma 8.
∎

Observe that the results in Theorems
73–75
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MLCR^∗
relative to many subsets of the parameters listed in Table 10.

We can derive a polynomial-time additive inapproximability result for
Max-MLCR^∗ using the following chain of metric reductions based on
two evaluation problems:

- •
Min-VC, which asks for the minimum value $k$ such that $G$ has
a vertex cover of size $k$.
- •
Min-MLCA, which asks for the minimum value $k$ such that there is
a $k$-size subset $N^{\prime}$ of the $|N|$ neurons in $M$ such that
$M(I)\neq(M/N^{\prime})(I)$.

###### Lemma 11 .

Min-VC metric reduces to Min-MLCA.

###### Proof.

Consider the following reduction from Min-VC to Min-MLCA. Given an
instance $X=\langle G=(V,E)\rangle$ of Min-VS, construct the following
instance $X^{\prime}=\langle M,I\rangle$ of Min-MLCA:
Let $M$ be an MLP based on $\#n_{tot}=3|V|+2|E|+2$ neurons spread
across six layers:

- 1.
Input neuron layer: The single input neuron $n_{in}$ (bias $+1$).
- 2.
Hidden vertex pair layer: The vertex neurons $nvP1_{1},nvP1_{2},\ldots nvP1_{|V|}$ and $nvP2_{1},nvP2_{2},\ldots nvP2_{|V|}$
(all with bias 0).
- 3.
Hidden vertex AND layer: The vertex neurons $nvA_{1},nvA_{2},\ldots nA_{|V|}$, all of which are 2-way AND ReLU gates.
- 4.
Hidden edge AND layer: The edge neurons $neA_{1},neA_{2},\ldots neA_{|E|}$, all of which are 2-way AND ReLU gates.
- 5.
Hidden edge NOT layer: The edge neurons $neN_{1},neN_{2},\ldots neN_{|E|}$, all of which are NOT ReLU gates.
- 6.
Output layer: The single output neuron $n_{out}$, which is
an $|E|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input neuron has an edge of weight 0 coming from its
corresponding input and is in turn connected to each of the vertex
pair neurons with weight 1.
- •
Each vertex pair neuron $nvP1_{i}$ ($nvP2_{i}$), $1\leq i\leq|V|$, is connected to vertex AND neuron $nvR_{i}$ with
weight 2 (0).
- •
Each vertex AND neuron $nvA_{i}$, $1\leq i\leq|V|$, is connected to
each edge AND neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge AND neuron $neA_{i}$, $1\leq i\leq|E|$, is connected to
edge NOT neuron $neN_{i}$ with weight 1.
- •
Each edge NOT neuron $neN_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(1)$. Observe that this instance of Min-MLCA can be
created in time polynomial in the size of the given instance of Min-VC.
Moreover, the output behaviour of the neurons in $M$ from the presentation
of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $n_{in}(1)$ |
| 2 | $nvP1_{1}(1),nvP1_{2}(1),\ldots nvP1_{|V|}(1),nvP2_{1}(1),nvP2_{2}(1),\ldots nvP<br>2_{|V|}(1)$ |
| 3 | $nvA_{1}(1),nvA_{2}(1),\ldots nvA_{|V|}(1)$ |
| 4 | $neA_{1}(1),neA_{2}(1),\ldots neA_{|V|}(1)$ |
| 5 | $neN_{1}(0),neN_{2}(0),\ldots neN_{|V|}(0)$ |
| 6 | $n_{out}(0))$ |

Note that, given the 0 (2) connection-weights of P2 (P1) vertex pair
neurons to vertex AND neurons, it is the outputs of P1 vertex pair neurons
in timestep 2 that enables vertex AND neurons to output 1 in timestep 3.

We now need to show the correctness of this reduction by proving that the
answer for the given instance of Min-VC is $k$ if and only if the answer
for the constructed instance of Min-MLCA is $k$. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a minimum-size vertex cover in $G$ of size $k$ and $N^{\prime}$ be the
$k$-sized sized subset of the P1 vertex pair neurons corresponding
to the vertices in $V^{\prime}$. Let $M^{\prime}$ be the version of $M$ in which all
neurons in $N^{\prime}$ are ablated. As each of these vertex pair neurons
previously allowed their associated vertex AND
neurons to output 1,
their ablation now allows these $k$ vertex AND neurons to
output 0. As $V^{\prime}$ is a vertex cover of size $k$,
all edge AND neurons in $M^{\prime}$ receive
inputs of 0 on at least one of their endpoints from the vertex
AND neurons associated with the P1 vertex pair neurons in $N^{\prime}$.
This in turn ensures that all of the edge NOT neurons and the
output neuron produces output 1. Hence, $M(I)=0\neq 1=M^{\prime}(I)$.

: Let $N^{\prime}$ be a minimum-sized subset of $N$ of size $k$
such that for the MLP $M^{\prime}$ induced by ablating all neurons in $N^{\prime}$,
$M(I)\neq M(I^{\prime})$. As $M(I)=0$ and circuit outputs are stepped to
be Boolean, $M^{\prime}(I)=1$. Given the bias of the output neuron, this
can only occur if all $|E|$ edge NOT (AND) neurons in $M^{\prime}$ have
output 1 (0) on input $I$, the latter of which requiring that each
edge AND neuron receives 0 from at least one of its endpoint vertex
AND neurons. These vertex AND neurons can only output 0 if all of
their associated P1 vertex neurons have been ablated. This means
that the vertices in $G$ corresponding to the P1 vertex pair neurons
in $N^{\prime}$ must form a vertex cover of size $k$ in $G$.

As this proves that Min-VC($X$) $=$ Min-MLCA($X^{\prime}$), the reduction above
is a metric reduction from Min-VC to Min-MLCA.
∎

###### Lemma 12 .

Min-MLCA metric reduces to Max-MLCR^∗.

###### Proof.

As MLCA is the complement problem of MLCR^∗ (Observation
3), we already have a trivial reduction from MLCA to
MLCR^∗ on their common input $X=\langle M,I\rangle$. We can then show that
$k$ is the minimum value such that $M$ has a $k$ circuit ablation relative
to $I$ if and only if $k-1$ is the maximum value such that $M$ is
$k-1$-robust relative to $I$:

If $k$ is is the minimum value such that $M$ has a
$k$-sized circuit ablation relative to $I$ then no subset of $M$ of
size $k-1$ can be a circuit ablation of $M$ relative to $I$, and
$M$ is $(k-1)$-robust relative to $I$. Moreover, $M$ cannot be
$k$-robust relative to $I$ as that would contradict the existence
of a $k$-sized circuit ablation for $M$ relative to $I$. Hence,
$k-1$ is the maximum robustness value for $M$ relative to $I$.

If $k-1$ is the maximum value such that $M$ is
$(k-1)$-robust relative to $I$ then there must be a subset $H$ of
$M$ of size $k$ that ensures $M$ is not $k-1$-robust, i.e.,
$(M/H)(I)\neq M(I)$. Such an $H$ is a $k$-sized circuit ablation of
$M$ relative to $I$. Moreover, there cannot be a $(k-1)$-sized
circuit ablation of $M$ relative to $I$ as that would contradict the
$(k-1)$-robustness of $M$ relative to $I$. Hence, $k$ is the
minimum size of circuit ablations for $M$ relative to $I$.

As this proves that Min-MLCA($X$) $=$ Max-MLCR^∗($X$) $+1$, the
reduction above is a metric reduction from Min-MLCA to Max-MLCR^∗.
∎

###### Theorem 76 .

If Max-MLCR^∗has a $c$-additive approximation algorithm for some
$c\in o(poly)$ then $P=NP$.

###### Proof.

The $OptP[O(\log n)]$-hardness of Max-MLCR^∗ follows from the
$OptP[O(\log n)]$-hardness of Min-VC (Gasarch et al., , Theorem Theorem 3.3) and
the metric reductions in Lemmas 11 and
12. The result then follows from
Lemma 3
∎

Let us now consider problem MLCR.

###### Lemma 13 .

MLCR^∗ many-one polynomial-time reduces to MLCR.

###### Proof.

Follows from the trivial reduction in which an instance $\langle M,I,k\rangle$
of MLCR^∗ is transformed into an instance $\langle M,H=M,I,k\rangle$ of
MLCR.
∎

###### Theorem 77 .

If MLCR is polynomial-time tractable then $P=NP$.

###### Proof.

Follows from the $coNP$-hardness of MLCR^∗ (Theorem 72),
the reduction in Lemma 13, and Lemma 6.
∎

###### Theorem 78 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MLCR is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Follows from the $coW[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MLCR^∗ (Theorem 73),
the reduction in Lemma 13, and Lemma 9.
∎

###### Theorem 79 .

$\langle|H|\rangle$-MLCR is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates every possible subset $H^{\prime}$ of size
at most $k$ of the neurons $N$ in $H$ and for each such subset (assuming
$M/H^{\prime}$ is active) checks if $(M/H^{\prime})(I)\neq M(I)$. If such a subset is
found, return “No”; otherwise, return “Yes”. The number of possible
subsets $H^{\prime}$ is at most $k\times|H|^{k}\leq|H|\times|H|^{|H|}$. As any such $M^{\prime}$ can be generated from $M$, checked
or activity, and run on $I$ in time polynomial in the size of the given
instance of MLCR, the above is a fixed-parameter tractable
algorithm for MLCR relative to parameter-set $\{|H|\}$.
∎

###### Theorem 80 .

$\langle cw,cd\rangle$-MLCR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 79 and
the observation that $|H|\leq cw\times cd$.
∎

###### Theorem 81 .

$\langle\#n_{tot}\rangle$-MLCR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 79 and
the observation that $|H|\leq\#n_{tot}$.
∎

###### Theorem 82 .

If Max-MLCR has a $c$-additive approximation algorithm for some
$c\in o(poly)$ then $P=NP$.

###### Proof.

As Max-MLCR^∗ is a special case of Max-MLCR, if Max-MLCR has a
$c$-additive approximation algorithm for some $c$ then so does
Max-MLCR^∗. The result then follows from Theorem 76
∎

###### Theorem 72 .

###### Proof.

###### Theorem 73 .

###### Proof.

###### Theorem 74 .

###### Proof.

###### Theorem 75 .

###### Proof.

###### Lemma 11 .

###### Proof.

###### Lemma 12 .

###### Proof.

###### Theorem 76 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Theorem 77 .

###### Proof.

###### Theorem 78 .

###### Proof.

###### Theorem 79 .

###### Proof.

###### Theorem 80 .

###### Proof.

###### Theorem 81 .

###### Proof.

###### Theorem 82 .

###### Proof.

#### K.2 Results for MGCR-special and MGCR

Consider the following variant of MGCA:

Special Circuit Ablation (SCA)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
and a
positive integer $k$ such that $1\leq k\leq\#n_{tot}$.
Question: Is there a subset $N^{\prime}$, $|N^{\prime}|\leq k$, of the $|N|$ neurons
in $M$ such that for the MLP $M^{\prime}$ induced by $N\setminus N^{\prime}$, $M(I)\neq M^{\prime}(I)$ for some Boolean input
vector $I$ of length $\#n_{in}$?

###### Theorem 83 .

If SCA is polynomial-time tractable then $P=NP$.

###### Proof.

Observe that in the instance of MLCA constructed by the reduction from
Clique in the proof of Theorem 40, the
input-connection weight 0 and bias 1 of the input neuron force this neuron
to output 1 for both of the possible input vectors $(1)$ and $(0)$. This
means that the answer to the given instance of Clique is “Yes” if
and only if the answer to the constructed instance of MLCA relative to any
of its possible input vectors is “Yes”. Hence, with slight modifications
to the proof of reduction correctness, this reduction also establishes the
$NP$-hardness of SCA.
∎

###### Theorem 84 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-SCA is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of SCA constructed in the reduction in the
proof of Theorem 83, $\#n_{in}=\#n_{out}=W_{\max}=1$,
$cd=5$, and $B_{\max}$ and $k$ are function of $k$ in the given instance
of Clique. The result then follows from the fact that
$\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 85 .

$\langle\#n_{tot}\rangle$-SCA is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 41 such
that each created MLP $M$ is checked to ensure that $M(I)\neq M^{\prime}(I)$ for every possible Boolean input vector of length $\#n_{in}$. As the number of such vectors is $2^{\#n_{in}}\leq 2^{\#n_{tot}}$, the above is a fixed-parameter tractable algorithm for SCA relative to parameter-set $\{\#n_{tot}\}$.
∎

###### Theorem 86 .

$\langle cw,cd\rangle$-SCA is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 85 and
the observation that $\#n_{tot}\leq cw\times cd$.
∎

Our results above for SCA above gain importance for us here courtesy of
the following observation.

###### Observation 4 .

MGCR^∗ is the complement of SCA.

###### Proof.

Let $X=\langle M,k\rangle$ be a shared input of MGCR^∗ and SCA. If the
the answer to SCA on input $X$ is “Yes”, this means that there is a
subset $H$ of size $\leq k$ of the neurons of $M$ that can be ablated
such that $M(I)\neq(M/H)(I)$ for some input vector $I$. This implies that
the answer to MGCR^∗ on input $X$ is “No”. Conversely, if the answer to
SCA on input $X$ is “No”, this means that there is no subset $H$ of size
$\leq k$ of the neurons of $M$ that can be ablated such that $M(I)\neq(M/H)(I)$ for any input vector $I$. This
implies that the answer to MGCR^∗ on input $X$ is “Yes’. The
observation follows from the definition of complement problem.
∎

###### Theorem 87 .

If MGCR^∗ is polynomial-time tractable then $P=NP$.

###### Proof.

As MGCR^∗ is the complement of SCA by Observation 4
and SCA is $NP$-hard (Theorem 83), Lemma 5
implies that MGCR^∗ is $coNP$-hard. The result then follows from Lemma
6.
∎

###### Theorem 88 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MGCR^∗ is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

The $coW[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MGCR^∗ follows from the $W[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-SCA (Theorem 84),
Observation 4, and Lemma 7. The result
then follows from Lemma 9.
∎

###### Theorem 89 .

$\langle\#n_{tot}\rangle$-MGCR^∗ is fixed-parameter tractable.

###### Proof.

The result follows from the fixed-parameter tractability of
$\langle\#n_{tot}\rangle$-SCA (Theorem 85), Observation
4, and Lemma 8.
∎

###### Theorem 90 .

$\langle cw,cd\rangle$-MGCR^∗ is fixed-parameter tractable.

###### Proof.

The result follows from the fixed-parameter tractability of
$\langle cw,cd\rangle$-SCA (Theorem 86), Observation
4, and Lemma 8.
∎

Observe that the results in Theorems
88–90
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MGCR^∗
relative to many subsets of the parameters listed in Table 10.

We can derive a polynomial-time additive inapproximability result for
Max-MGCR^∗ using the following chain of metric reductions based on
two evaluation problems:

- •
Min-VC, which asks for the minimum value $k$ such that $G$ has
a vertex cover of size $k$.
- •
Min-SCA, which asks for the minimum value $k$ such that there is
a $k$-size subset $N^{\prime}$ of the $|N|$ neurons in $M$ such that
$M(I)\neq(M/N^{\prime})(I)$ for some Boolean input vector $I$ of
length$\#n_{in}$.

###### Lemma 14 .

Min-VC metric reduces to Min-SCA.

###### Proof.

Observe that in the instance of Min-MLCA constructed by the reduction from
Min-VC in the proof of Theorem 11, the
input-connection weight 0 and bias 1 of the input neuron force this neuron
to output 1 for both of the possible input vectors $(1)$ and $(0)$. This
means that the answer to the constructed instance of Min-MLCA is the
same relative to any of its possible input vectors. Hence, with slight
modifications to the proof of reduction correctness, this reduction is
also a metric reduction from Min-VC to Min-SCA such that for
given instance $X$ of Min-VC and constructed instance $X^{\prime}$ of Min-SCA,
Min-VC($X$) $=$ Min-SCA($X^{\prime}$).
∎

###### Lemma 15 .

Min-SCA metric reduces to Max-MGCR^∗.

###### Proof.

As SCA is the complement problem of MGCR^∗ (Observation
4), we already have a trivial reduction from SCA to
MGCR^∗ on their common input $X=\langle M\rangle$. We can then show that
$k$ is the minimum value such that $M$ has a $k$ circuit ablation relative
to some possible $I$ if and only if $k-1$ is the maximum value such
that $M$ is $k-1$-robust relative to all possible $I$:

If $k$ is is the minimum value such that $M$ has a
$k$-sized circuit ablation relative to some possible $I$ then no
subset of $M$ of size $k-1$ can be a circuit ablation of $M$
relative to any possible $I$, and $M$ is $(k-1)$-robust relative
to all possible $I$. Moreover, $M$ cannot be $k$-robust relative to
all possible $I$ as that would contradict the existence of a
$k$-sized circuit ablation for $M$ relative to some possible $I$.
Hence, $k-1$ is the maximum robustness value for $M$ relative to
all possible $I$.

If $k-1$ is the maximum value such that $M$ is
$(k-1)$-robust relative to all possible $I$ then there must be a
subset $H$ of $M$ of size $k$ that ensures $M$ is not $k-1$-robust
relative to all possible $I$, i.e., $(M/H)(I)\neq M(I)$ for some
possible $I$. Such an $H$ is a $k$-sized circuit ablation of
$M$ relative to that $I$. Moreover, there cannot be a
$(k-1)$-sized circuit ablation of $M$ relative to some possible
$I$ as that would contradict the $(k-1)$-robustness of $M$
relative to all possible $I$. Hence, $k$ is the minimum size of
circuit ablations for $M$ relative to some possible $I$.

As this proves that Min-SCA($X$) $=$ Max-MGCR^∗($X$) $+1$, the
reduction above is a metric reduction from Min-SCA to Max-MGCR^∗.
∎

###### Theorem 91 .

If Max-MGCR^∗has a $c$-additive approximation algorithm for some
$c\in o(poly)$ then $P=NP$.

###### Proof.

The $OptP[O(\log n)]$-hardness of Max-MGCR^∗ follows from the
$OptP[O(\log n)]$-hardness of Min-VC (Gasarch et al., , Theorem Theorem 3.3) and
the metric reductions in Lemmas 14 and
15. The result then follows from
Lemma 3
∎

Let us now consider problem MGCR.

###### Lemma 16 .

MGCR^∗ many-one polynomial-time reduces to MGCR.

###### Proof.

Follows from the trivial reduction in which an instance $\langle M,k\rangle$
of MGCR^∗ is transformed into an instance $\langle M,H=M,k\rangle$ of
MGCR.
∎

###### Theorem 92 .

If MGCR is polynomial-time tractable then $P=NP$.

###### Proof.

Follows from the $coNP$-hardness of MGCR^∗ (Theorem 87),
the reduction in Lemma 16, and Lemma 6.
∎

###### Theorem 93 .

If $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MGCR is
fixed-parameter tractable then $FPT=W[1]$.

###### Proof.

Follows from the $coW[1]$-hardness of $\langle cd,\#n_{in},\#n_{out},W_{\max},B_{\max},k\rangle$-MGCR^∗ (Theorem 88),
the reduction in Lemma 16, and Lemma 9.
∎

###### Theorem 94 .

$\langle\#n_{in},|H|\rangle$-MGCR is fixed-parameter tractable.

###### Proof.

Modify the algorithm in the proof of Theorem 79 such
that each created MLP $M$ is checked to ensure that $M(I)\neq(H/H^{\prime})(I)$
for every possible Boolean input vector of length $\#n_{in}$. As the number
of such vectors is $2^{\#n_{in}}$, the above is a fixed-parameter tractable
algorithm for MGCR relative to parameter-set $\{\#n_{in},|H|\}$.
∎

###### Theorem 95 .

$\langle cw,cd\rangle$-MGCR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 94 and
the observations that $\#n_{tot}\leq cw\times cd$ and
$|H|\leq cw\times cd$.
∎

###### Theorem 96 .

$\langle\#n_{tot}\rangle$-MGCR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 94 and
the observations that $\#n_{tot}\leq\#n_{tot}$ and $|H|\leq\#n_{tot}$.
∎

###### Theorem 97 .

If Max-MGCR has a $c$-additive approximation algorithm for some
$c\in o(poly)$ then $P=NP$.

###### Proof.

As Max-MGCR^∗ is a special case of Max-MGCR, if Max-MGCR has a
$c$-additive approximation algorithm for some $c$ then so does
Max-MGCR^∗. The result then follows from Theorem 91
∎

###### Theorem 83 .

###### Proof.

###### Theorem 84 .

###### Proof.

###### Theorem 85 .

###### Proof.

###### Theorem 86 .

###### Proof.

###### Observation 4 .

###### Proof.

###### Theorem 87 .

###### Proof.

###### Theorem 88 .

###### Proof.

###### Theorem 89 .

###### Proof.

###### Theorem 90 .

###### Proof.

###### Lemma 14 .

###### Proof.

###### Lemma 15 .

###### Proof.

###### Theorem 91 .

###### Proof.

###### Lemma 16 .

###### Proof.

###### Theorem 92 .

###### Proof.

###### Theorem 93 .

###### Proof.

###### Theorem 94 .

###### Proof.

###### Theorem 95 .

###### Proof.

###### Theorem 96 .

###### Proof.

###### Theorem 97 .

###### Proof.

### Appendix L Sufficient Reasons Problem

Minimum sufficient reason (MSR)
Input: A multi-layer perceptron $M$ of depth $cd$ with $\#n_{tot}$
neurons and maximum layer width $cw$, connection-value
matrices $W_{1},W_{2},\ldots,W_{cd}$, neuron bias vector $B$,
a Boolean input vector $I$ of length $\#n_{in}$, and a
positive integer $k$ such that $1\leq k\leq\#n_{in}$.
Question: Is there a $k$-sized subset $I^{\prime}$ of $I$ such that for each
possible completion $I^{\prime\prime}$ of $I^{\prime}$, $I$ and $I^{\prime\prime}$ are
behaviorally equivalent with respect to $M$?

For a graph $G=(V,E)$, we shall assume an ordering on the vertices and edges in $V$
and $E$, respectively. For each vertex $v\in V$, let the complete neighbourhood $N_{C}(v)$ of $v$ be the set
composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$
by a single edge, i.e., $v\cup\{u~{}|~{}u~{}\in V~{}\rm{and}~{}(u,v)\in E\}$.

We will prove various classical and parameterized results for MSR
using reductions from Clique. The
parameterized results are proved relative to the parameters in
Table 11. An additional reduction from DS
(Theorem 103) use specialized ReLU logic
gates described in Barceló et al. , Lemma 13. These gates assume Boolean
neuron input and output values of 0 and 1 and are structured as follows:

- 1.
NOT ReLU gate: A ReLU gate with one input connection weight of value
$-1$ and a
bias of 1. This gate has output 1 if the input is 0 and 0 otherwise.
- 2.
$n$-way AND ReLU gate: A ReLU gate with $n$ input connection weights
of value 1 and a bias of $-(n-1)$. This gate has output 1 if all
inputs have value 1 and 0 otherwise.
- 3.
$n$-way OR ReLU gate: A combination of an $n$-way AND ReLU gate with
NOT ReLU gates on all of its inputs and a NOT ReLU gate on its
output that uses DeMorgan’s Second Law to implement
$(x_{1}\vee x_{2}\vee\ldots x_{n})$ as $\neg(\neg x_{1}\wedge\neg x_{2}\wedge\ldots\neg x_{n})$. This gate has
output 1 if any input has value 1 and 0 otherwise.

**Table 11: Parameters for the minimum sufficient reason problem.**
| Parameter | Description |
| --- | --- |
| $cd$ | # layers in given MLP |
| $cw$ | max # neurons in layer in given MLP |
| $\#n_{tot}$ | total # neurons in given MLP |
| $\#n_{in}$ | # input neurons in given MLP |
| $\#n_{out}$ | # output neurons in given MLP |
| $B_{\max}$ | max neuron bias in given MLP |
| $W_{\max}$ | max connection weight in given MLP |
| $k$ | Size of requested subset of input vector |

#### L.1 Results for MSR

The following hardness results are notable for holding
when the given MLP $M$ has only one hidden layer. As such, they complement and significantly tighten results given in (Barceló et al., ; Wäldchen et al., ), respectively.

###### Theorem 98 .

If MSR is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from Clique to MSR.
Given an instance $\langle G=(V,E),k\rangle$ of Clique, construct the following
instance $\langle M,I,k^{\prime}\rangle$ of MSR:
Let $M$ be an MLP based on $\#n_{tot}=|V|+|E|+1$ neurons spread
across three layers:

- 1.
Input vertex layer: The vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$
(all with bias 0).
- 2.
Hidden edge layer: The edge neurons $ne_{1},ne_{2},\ldots ne_{|E|}$
(all with bias $-1$).
- 3.
Output layer: The single output neuron $n_{out}$ (bias $-(k(k-1)/2-1)$).

Note that this MLP has only one hidden layer.
The non-zero weight connections between adjacent layers are as follows:

- •
Each vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected to each edge neuron
whose corresponding edge has an endpoint $v_{i}$ with weight 1.
- •
Each edge neuron $ne_{i}$, $1\leq i\leq|E|$, is connected to the output neuron
$n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I=(1)$ and $k^{\prime}=k$.
Observe that this instance of MSR can be created in time polynomial in the size of the
given instance of Clique. Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nv_{1}(1),nv_{2}(1),\ldots nv_{|V|}(1)$ |
| 2 | $ne_{1}(1),ne_{2}(1),\ldots ne_{|E|}(1)$ |
| 3 | $n_{out}(|E|-(k(k-1)/2-1))$ |

Note that it is the stepped output of $n_{out}$ in timestep 3 that yields output 1.

We now need to show the correctness of this reduction by proving that the answer
for the given instance of Clique is “Yes” if and only if the answer for the
constructed instance of MSR is “Yes”. We prove the two
directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$
be a clique in $G$ of size $k$ and $I^{\prime}$ be the $k^{\prime}=k$-sized
subset of $I$ corresponding to the vertices in $V^{\prime}$. As $V^{\prime}$ is
a clique of size $k$, exactly $k(k-1)/2$ edge neurons in the
constructed MLP $M$ receive the
requisite inputs of 1 on both of their endpoints from the vertex
neurons associated with $I^{\prime}$. This in turn ensures the output
neuron produces output 1. No other possible inputs to the vertex
neurons not corresponding to elements of $I^{\prime}$ can change the outputs
of these activated edge neurons (and
hence the output neuron as well) from 1 to 0. Hence, all completions
of $I^{\prime}$ cause $M$ to output 1 and are behaviorally equivalent to $I$
with respect to $M$.

: Let $I^{\prime}$ be a $k^{\prime}=k$-sized subset of $I$ such that
all possible completions of $I^{\prime}$ are behaviorally equivalent to
$I$ with respect to $M$, i.e., all such completions cause $M$ to
output 1. Consider the completion $I^{\prime\prime}$ of $I^{\prime}$ in which all non-$I^{\prime}$
elements have value 0. The output of $M$ on $I^{\prime\prime}$ can be 1 (and
hence equal to the output of $M$ on $I$) only if at least
$k(k-1)/2$ edge neurons have output 1. As all non-$I^{\prime}$ elements of
$I^{\prime\prime}$ have value 0, this means that both endpoints of each of these
edge neuron must be connected to elements of $I^{\prime}$ with output 1,
which in turn implies that the $k^{\prime}=k$ vertices in $G$ corresponding
to the elements of $I^{\prime}$ form a clique of size $k$ for $G$.

As Clique is $NP$-hard (Garey & Johnson, ), the reduction above establishes
that MSR is also $NP$-hard. The result follows from the definition of
$NP$-hardness.
∎

###### Theorem 99 .

If $\langle cd,\#n_{out},W_{\max},B_{\max},k\rangle$-MSR is fixed-parameter
tractable then $FPT=W[1]$.

###### Proof.

Observe that in the instance of MSR constructed in the reduction in the
proof of Theorem 98, $\#n_{out}=W_{\max}=1$, $cd=3$, and
$B_{\max}$ and $k$ are function of $k$ in the given instance of
Clique. The result then follows from the fact that
$\langle k\rangle$-Clique is $W[1]$-hard (Downey & Fellows, ).
∎

###### Theorem 100 .

$\langle\#n_{in}\rangle$-MSR is fixed-parameter tractable.

###### Proof.

Consider the algorithm that generates each possible subset $I^{\prime}$ of of $I$
of size $k$ and for each such $I^{\prime}$, checks if all possible completions
of $I^{\prime}$ are behaviorally equivalent to $I$ with respect to $M$. If such an
$I^{\prime}$ is found, return “Yes”; otherwise, return “No”. The number of
possible $I^{\prime}$ is at most $(\#n_{in})^{k}\leq(\#n_{in})^{\#n_{in}}$ and the number of possible
completions of any such $I^{\prime}$ is less than $2^{\#n_{in}}$. Given this, as $M$ can be
run on each completion of $I^{\prime}$ is time polynomial in the size of the given
instance of MSR, the above is a fixed-parameter tractable algorithm for MSR
relative to parameter-set $\{\#n_{in}\}$.
∎

###### Theorem 101 .

$\langle\#n_{tot}\rangle$-MSR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 100 and
the observation that $\#n_{in}\leq\#n_{tot}$.
∎

###### Theorem 102 .

$\langle cw\rangle$-MSR is fixed-parameter tractable.

###### Proof.

Follows from the algorithm in the proof of Theorem 100 and
the observation that $\#n_{in}\leq cw$.
∎

Observe that the results in Theorems 99–102
in combination with Lemmas 1 and 2
suffice to establish the parameterized complexity status of MSR relative
to every subset of the parameters listed in Table 11.

Let us now consider the polynomial-time cost approximability of MSR. As
MSR is a minimization problem, we cannot do this using reductions from a
maximization problem like Clique. Hence we will instead use a
reduction from another minimization problem, namely DS.

###### Theorem 103 .

If MSR is polynomial-time tractable then $P=NP$.

###### Proof.

Consider the following reduction from DS to MSR.
Given an instance $\langle G=(V,E),k\rangle$ of DS, construct the following
instance $\langle M,I,k^{\prime}\rangle$ of MSR:
Let $M$ be an MLP based on $\#n_{tot,g}=3|V|+1$ neurons spread
across four layers:

- 1.
Input layer: The input vertex neurons $nv_{1},nv_{2},\ldots nv_{|V|}$, all of which have bias 0.
- 2.
Hidden vertex neighbourhood layer I: The vertex neighbourhood AND neurons $nvnA_{1},nvnA_{2},\ldots nvnA_{|V|}$, where $nvnA_{i}$ is an $x$-way AND ReLU gates such that $x=|N_{C}(v_{i})|$.
- 3.
Hidden vertex neighbourhood layer II: The vertex neighbourhood NOT neurons $nvnN_{1},nvnN_{2},\ldots nvnN_{|V|}$, all of which are NOT ReLU gates.
- 4.
Output layer: The single output neuron $n_{out}$, which is a
$|V|$-way AND ReLU gate.

The non-zero weight connections between adjacent layers are as follows:

- •
Each input vertex neuron $nv_{i}$, $1\leq i\leq|V|$, is connected
to each vertex neighbourhood AND neuron $nvnA_{j}$ such that $v_{i}\in N_{C}(v_{j})$ with weight 1.
- •
Each vertex neighbourhood AND neuron $nvnA_{i}$, $1\leq i\leq|V|$, is
connected to its corresponding vertex neighbourhood NOT neuron
$nvnN_{i}$ with weight 1.
- •
Each vertex neighbourhood NOT neuron $nvnN_{i}$, $1\leq i\leq|V|$, is
connected to the output neuron $n_{out}$ with weight 1.

All other connections between neurons in adjacent layers have weight 0.
Finally, let $I$ be the $|V|$-length zero-vector and $k^{\prime}=k$. Observe that
this instance of MSR can be created in time polynomial in the size of the
given instance of DS, Moreover, the output behaviour of the neurons in
$M$ from the presentation of input $I$ until the output is generated is as
follows:

| timestep | neurons (outputs) |
| --- | --- |
| 0 | — |
| 1 | $nvN_{1}(0),nvN_{2}(0),\ldots nvN_{|V|}(0)$ |
| 2 | $nvnA_{1}(0),nvnA_{2}(0),\ldots nvnA_{|V|}(0)$ |
| 3 | $nvnN_{1}(1),nvnN_{2}(1),\ldots nvnN_{|V|}(1)$ |
| 4 | $n_{out}(1)$ |

We now need to show the correctness of this reduction by proving that the answer for the given instance of DS is “Yes” if and only if the answer for the constructed instance of MSR is “Yes”.
We prove the two directions of this if and only if separately as follows:

: Let $V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k}\}\subseteq V$ be a dominating set in $G$ of size $k$ and $I^{\prime}$ be the $k^{\prime}=k$-sized subset of $I$ corresponding to the vertices in $V^{\prime}$. As $V^{\prime}$ is
a dominating set, each vertex neighbourhood AND neuron receives
input 0 from at least one input vertex neuron in the set of input
vertex neurons associated with $I^{\prime}$, which in turn ensures that each
vertex neighbourhood AND neuron has output 0. This in turn ensures
that $M$ produces output 1. No other possible inputs to the vertex
neighbourhood AND neurons can change the output of these neurons from
0 to 1. Hence, all completions of $I^{\prime}$ cause $M$ to output 1 and are
behaviorally equivalent to $I$ with respect to $M$.

: Let $I^{\prime}$ be a $k^{\prime}=k$-sized subset of $I$ such that
all possible completions of $I^{\prime}$ are behaviorally equivalent to
$I$ with respect to $M$, i.e., all such completions cause $M$ to
output 1. Consider the completion $I^{\prime\prime}$ of $I^{\prime}$ in which all non-$I^{\prime}$
elements have value 1. The output of $M$ on $I^{\prime\prime}$ can be 1 (and
hence equal to the output of $M$ on $I$) only if
all vertex neighbourhood NOT neurons output 1, which in turn can
happen only if all vertex neighbourhood AND gates output 0. However,
as all non-$I^{\prime}$ elements of $I^{\prime\prime}$ have value 1, this means that
each vertex neighbourhood AND neuron must be connected to
at least one element of $I^{\prime}$, which in turn implies that the
$k^{\prime}=k$ vertices in $G$ corresponding to the elements of $I^{\prime}$ form
a dominating set of size $k$ for $G$.

As DS is $NP$-hard (Garey & Johnson, ), the reduction above establishes that MSR is also $NP$-hard.
The result follows from the definition of $NP$-hardness.
∎

###### Theorem 104 .

If MSR has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then $FPT=W[1]$.

###### Proof.

Recall from the proof of correctness of the reduction in the proof of
Theorem 103 that a given instance of DS has a dominating set
of size $k$ if and only if the constructed instance of $MSR$ has a subset $I^{\prime}$ of $I$ of size $k^{\prime}=k$ such that every possible completion of $I^{\prime}$ is behaviorally equivalent to $I$ with respect to $M$.
This implies that, given a polynomial-time $c$-approximation algorithm $A$ for MSR for some constant $c>0$, we can create a polynomial-time $c$-approximation algorithm for DS by applying the reduction to the given instance $x$ of DS to construct an instance $x^{\prime}$ of MSR, applying $A$ to $x^{\prime}$ to create an approximate solution $y^{\prime}$, and then using $y^{\prime}$ to create an approximate solution $y$ for $x$ that has the same cost as $y^{\prime}$. The result then follows from Chen & Lin , Corollary 2, which implies that if DS has a polynomial-time $c$-approximation algorithm for any constant $c>0$ then $FPT=W[1]$.
∎

Note that this theorem also renders MSR PTAS-inapproximable unless
$FPT=W[1]$.

###### Theorem 98 .

###### Proof.

###### Theorem 99 .

###### Proof.

###### Theorem 100 .

###### Proof.

###### Theorem 101 .

###### Proof.

###### Theorem 102 .

###### Proof.

###### Theorem 103 .

###### Proof.

###### Theorem 104 .

###### Proof.

### Appendix M Probabilistic approximation schemes

Let us now consider three other types of polynomial-time approximability
that may be acceptable in situations where always getting the
correct output for an input is not required:

- 1.
algorithms that always run in polynomial time but are frequently correct in that they
produce the correct output for a given input in all but a small number of
cases (i.e., the number of errors for input size $n$ is bounded by function $err(n)$)
Hemaspaandra & Williams ();
- 2.
algorithms that always run in polynomial time but are frequently correct in that they
produce the correct output for a given input
with high probability Motwani & Raghavan (); and
- 3.
algorithms that run in polynomial time with high probability but are always correct
(Gill, ).

Unfortunately, none of these options are in general open to us, courtesy of the following result.

###### Theorem 105 .

None of the hard problems in Table 4 are polynomial-time approximable in senses
(1–3).

###### Proof.

(Sketch) Holds relative to several strongly-believed or established
complexity-class relation conjectures courtesy of the $NP$-hardness of
the problems and the reasoning in the proof of (Wareham, , Result E).
∎

###### Theorem 105 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: -	What is the valid criticism of zero-ablation? (line 285)
-	Can you add a brief discussion on how your results relate to some computational hardness results known for PAC-learning variants of neural networks. In particular, I’m curious to understand if any of your results follow more directly from some of the hardness reductions considered in these works. Some example works (a non-exhaustive list) are cited below ([1-3]).
-	What happens if we relax the assumption of having a step function at the output layer? Would most of the problems studied continue to remain intractable. (note that now we can also allow for an approximation in the quality of the output. i.e. the sub-circuit doesn’t have to exactly match the behavior of the original circuit, it can be approximately close)


1. On the computational efficient of training neural nets. Livni et. al.
2. On the complexity of learning neural networks. Song et. al.
3. Learning deep neural networks is fixed-parameter tractable. Chen et. al.
soundness: 3
strengths: -	The paper tackles an important conceptual question facing empirical deep learning today. Although its results are theoretical and computational complexity has faced criticism in the past of being overly pessimistic, it is nevertheless a stellar guiding light as to what problems are tractable and might be solvable without requiring any additional assumptions.
-	The paper provides some transformations/additional assumptions with which some of the problems to be solved start becoming tractable.
-	The paper is quite comprehensive in its coverage of different notions and tools used in mechanistic interpretability literature.
- Even if computational hardness for many of the problems being studied is to be expected by theorists, it is important to compile the results and clearly state the message as it might help guide practitioners search for tractable notions of interpretability.
summary: The paper studies the computational challenges surrounding the fields of circuit discovery and mechanistic interpretability. Achieving circuit discovery or accurate and precise interpretability at scale is a major empirical challenge for deep learning today. This paper sheds light on why that goal might be computationally out of reach by showing that many of the tools we use today end up having to solve computationally hard problems. Some of the specific problems the paper studies computational complexity of are:

1. Sufficient circuit – finding a small sub-circuit which reproduces the behavior of the network on a specific input or all inputs.
2. Gnostic neurons – a set of neurons with maximally distant activations of certain subsets of inputs we are trying to classify between.
3. Circuit Ablation and Clamping
4. Circuit patching
5. Circuit robustness
6. Sufficient reasons

For all these different problems, the paper studies the computational hardness of the general problem, fixed-parameter tractability, hardness of approximation (additive, multiplicative and probabilistic).
They show that while some of these problems are solvable in poly time (like gnostic neurons) most remain hard even to approximate. However, some are NP-complete and have reductions from 3SAT which leaves the promise of SAT-solver heuristic being applicable for these problems.
In addition, for some problems the results show a separation between local notion of interpretability (which captures a certain property only on a small set of inputs) and a global notion (which captures the property over the entire input range). Such separations are proposed as a reason for why local explanations of faithfulness in the past have been shown to be at times fickle.
weaknesses: -	Computational complexity of PAC learning MLPs is a well-studied problem by the learning theory community and has connections to many of the results you study here. A comparison to some of the hardness results already known there is in order.
-	The assumption of applying a step function on the output is quite stringent. It is known that being able to see a real-valued output rather than a Boolean output can make some learning problems on neural nets tractable [1]. The results of the paper would be stronger and more significant if they hold without the step function being applied at the end.
-	For most of the interpretability tasks, the notion of approximation considered to measure the quality of the sub-circuit found allows for some amount of flexibility in capturing the output behavior. This axis of approximation doesn’t seem to be addressed in your work (apologize if I missed it). Could the landscape change for any of the problems when considering such an approximation. 


[1] Reliably Learning the ReLU in Polynomial Time. Goel et. al.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: Some proofs rely on step functions being applied to neuron activations. To what extent do these proofs apply to neural networks with only ReLU activation functions? I believe that ReLU MLPs can approximate step functions, but not implement them exactly. Alternatively, could you extend your proofs such they don't rely on step functions?
soundness: 4
strengths: This is the first formal characterization of the complexity of circuit discovery that I am aware of. It is very useful for the field to formalize problems such that they can be reasoned about with clarity. The formal characterization is also useful to clearly enumerate all the types of circuit queries that mechanistic interpretability researchers might want to perform to understand networks.

The paper is extremely thorough in covering a wide range of queries. The proofs that I read in detail (Appendix B on Minimum Locally Sufficient Circuits) appeared to be correct.
summary: The authors frame a large number of circuit discovery problems in mechanistic interpretability as a set of formally defined queries about computational graphs.
They identify and prove the complexity classes for each of these queries. They also find the fixed-parameter complexity classes and the complexity of several types of approximations to the optimal algorithms.
weaknesses: It is unclear to what extent these results should be major considerations for applied circuit discovery in real models. Heuristics such as gradient magnitude may be powerful enough to achieve close to optimal solutions with simple algorithms. The authors should include discussions of this to clarify.

The paper is primarily of use to researchers in mechanistic interpretability. Yet many researchers in the field will struggle to quickly understand much of the paper due to terse explanations of basic concepts in complexity theory. To some extent this is unavoidable as it would be arduous to include extensive tutorials on basic concepts from complexity, but a few well-chosen explanations could go a long way to bridge the gap for researchers who have some background in computer science. For example, more intuitive definitions of fixed parameter complexity, W[1]-hard and $\Sigma^{p}_{2}$-hard could be fairly concise and save many readers from needing to search for external resources.

Further, it would be useful to spell out more explicitly for less familiar readers how each proof connects to real world applications of circuit discovery. For example, since transformers contain MLPs, the proofs of complexities of queries on MLPs also apply to neuron level circuit discovery in transformers. Similarly, since binary vectors are a subset of the possible inputs to a real model, some proofs apply to models which are not constrained to binary inputs.

Since real models do not have binary activations, it is almost impossible for a circuit to achieve perfect faithfulness. In practice, we want our circuits to produce outputs that are sufficiently close to the full model output. But the problems considered by the authors ask for circuits that are perfectly faithful. So the authors should discuss whether their results apply in practice to realistic circuit discovery requirements.

Some smaller nitpicks:
- In Table 2: The notation “ “ is unclear because it looks like it could mean the same value as the previous row. It would be clearer to use a faded font or simply leave the box empty.
 - In Table 2: There is no explanation of "Coverage In" vs "Coverage Out".
 - I don’t understand why the coverage out of local circuits is empty.
 - In Appendix A.3 there is no explanation of function g(k).
 - In Appendix A.4.1 the variable I (instances) should be explained in the first paragraph.
 - In Appendix B, in the definition of MLSC, it’s unclear what the purpose of the constant c is.
 - In Appendix B, in Table 5, the third column is not labeled.
 - In Appendix B.2 make it clear which parts of proofs are being repeated from earlier parts.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. Over what type of input domain are the results defined (binary, discrete, or continuous)? 

2. What non-trivial proofs are presented in the paper?
soundness: 3
strengths: The paper's primary strength lies in bridging two distinct areas of interest: (1) the formal analysis of the computational complexity involved in generating various forms of explanations (as explored in [1] and [2]), which often fall under the sub-domain known as "formal explainable AI," and (2) the more contemporary field of mechanistic interpretability. While prior work has proposed using the computational complexity of post-hoc explanations to shed light on interpretability (e.g., [1], [2]), this paper extends that concept by linking it to mechanistic interpretability queries. I believe this approach has the potential to inspire further research in both domains, facilitating a more rigorous analysis of mechanistic interpretability, an area that is currently somewhat underexplored. Additionally, this work offers a thorough categorization of different mechanistic interpretability queries, providing a solid foundation for future studies.

[1] Model Interpretability through the Lens of Computational Complexity (Barcelo et. al, Neurips 2020)

[2] Local vs. Global Interpretability: A Computational Complexity Perspective (Bassan et. al, ICML 2024)
summary: This paper presents a framework for examining the computational complexity of generating various types of "interpretability queries" within the field of mechanistic interpretability. Unlike previous work that explored the complexity of post-hoc explanations for different ML models, primarily focusing on explanations in the input domain, this paper extends these findings by providing similar forms of explanations (specifically for neural networks) at the neural level rather than the input level. The paper also introduces complexity results for different mechanistic interpretability queries, demonstrating the intractability of some queries while proving that others are tractable, especially under certain relaxations.
weaknesses: 1. The paper does not clearly discuss its limitations. I would be interested in hearing from the authors what they consider to be the main limitations of their work. While the paper focuses on neuron-level explanations, one evident (potential) limitation is the lack of clarity around the definition of the input space domain. From my understanding, it appears to be binary, but is that correct? Or is the input space discrete or continuous? Given that this research centers on neural networks, rather than simpler models where binary or discrete domains are more common, it would be reasonable to also consider more complex domains, such as continuous ones. Additionally, transitioning to continuous input settings could have significant implications for the complexity of the problem. This should (at the very least) be discussed by the authors.

2. Many of the proofs presented in the paper appear to be relatively straightforward, and I’m not fully convinced of the *technical* significance of this work. It would be beneficial to clearly indicate when a proof is trivial versus when it is non-trivial. Additionally, specifying when a result confirms well-known folklore assumptions, and when it is genuinely surprising would enhance clarity. This distinction was not always evident in the paper.


3. Some of the "folklore" concepts that this paper seeks to rigorously prove are somewhat unclear. For instance, the explanation of this idea could be improved:

This result establishes a formal separation
 between local and global query complexity that partly explains ‘interpretability illusions’ (Friedman
 etal.,2024;Yuetal.,2024a) arising in practice due to local but not global faithfulness.

the meaning of "interpretability illusions" is not clearly defined.

4. I'm not entirely convinced by the rigid distinction between "interpretability" as being neuron-level and "explainability" as being input-level. Naturally, the efficiency of providing explanations at the input level is also closely tied to the model's interpretability, not just its neuron-level explanations. Perhaps a more appropriate way to differentiate between the outcomes here and those in previous studies is to describe them as explanations or interpretations at the "input level" versus the "neuron level," both of which contribute to the model’s overall interpretability.

5. The main table is excellent and offers a clear summary of the results. However, a more concise version of this table might be preferable for the main text, with the larger, detailed version included in the appendix.

6. The paper suggests that problems “contained” within NP can be efficiently addressed using SAT solvers. However, this is not always the case—when it comes to neural networks, especially for continuous domains, neural network verification models often serve as more appropriate optimization tools. These are usually not based on SAT solvers, but rather on SMT-based solvers, or branch-and-bound methods.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: The paper is well written and gives nice clean formalization of several problems motivated by interpretability.

In several of the problem formalizations you are trying to find the minimal sub-circuit for a given input x. If the problem is a boolean classification problem then in many circuits there might be some trivial tiny sub-circuits that give the correct output for that given x -- in your reduction you have avoided that by choosing a carefully crafted worst case circuit. Wouldn’t it make more sense to look at a distribution of inputs? I would have expected that one would get a much stronger inapproximability hardness result if you took a set of inputs and insisted that the sub-circuit should output correctly for all inputs which you are doing problem 8.

What is the takeaway here for interpretability in practice? Do you think interpretability is essentially intractable? Please expand on potential practical approaches to interpretability in light of these hardness results with scenarios and reasons as to why interpretability might still be feasible despite the worst-case intractability.
soundness: 4
strengths: Interpreting formalization and complexity study of several problems motivated by interpretability of deep networks.
summary: The paper formalizes several problems along the lines of finding the minimal subcircuit in a deep network that matches its computation; this is motivated by finding a small interpretable subcircuit. They show that this and several variants of this problem are intractable (either NP-hard or \Sigma_2^2. For several variants they all show that there is no PTAS.
weaknesses: The hardness results are not surprising. The area of finding small circuits is in general very hard (see for example: https://www.cs.uwyo.edu/~jhitchco/papers/npcmcsp.pdf even though it is a related but very different problem). The reduction from CLIQUE is simple.

The worst case hardness may not capture the average case complexity for real world distributions. I do understand proving hardness results for probabilistic settings is more difficult. But the impossibility results may not imply hardness of interpretability in practice.

Meta-review: This paper presents a framework for examining the computational complexity of generating various types of "interpretability queries" within the field of mechanistic interpretability. Unlike previous work that explored the complexity of post-hoc explanations for different ML models, primarily focusing on explanations in the input domain, this paper extends these findings by providing similar forms of explanations (specifically for neural networks) at the neural level rather than the input level. The paper also introduces complexity results for different mechanistic interpretability queries, demonstrating the intractability of some queries while proving that others are tractable, especially under certain relaxations.

All reviewers believe this paper made meaningful contributions. The AC agrees and thus recommends acceptance.

Decision: Accept (Spotlight)