PaperlayerView exact revision on arXiv

Source-linked AI summary

Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime

Olivier Bournez, Johanne Cohen, Laura Cohen, Adrian Wurm

arXiv:2610.06092v1cs.CC

TL;DR

ReLU verification is well understood for unrestricted width, but existing SAT reductions do not determine the complexity of deep, narrow networks. The paper uses a width-2 fractal preprocessing gadget to connect continuous inputs with a finite discrete encoding. It proves NP-completeness at width 4 for arbitrary inputs and at width 3 on the encoding set, while leaving specified widths and extensions open.

  • Problem

    Existing ReLU verification hardness reductions use unrestricted width, leaving the complexity of verification for deep, narrow networks unresolved.

    Source: §1 · p. 2

  • Method

    A width-2 fractal preprocessing map has iterates that vanish near a finite Cantor-like encoding set, allowing continuous verification to be reduced to that discrete set.

    Source: §1 · p. 3, §2.2 · p. 5

  • Results

    Width 4 gives NP-completeness for arbitrary inputs in [0, 1], while width 3 gives NP-completeness on the encoding set and supports further width-3 hardness results there.

    Source: §1 · p. 4, §6 · p. 29

  • Takeaways & Limitations

    The classification leaves only width 2 open on the encoding set and widths 2 and 3 open for arbitrary inputs in [0, 1].

    Source: §6 · p. 29

    Lifting the counting and majority results to [0, 1], and lifting the results at width 3, remain open.

    Source: §5.3 · p. 27, §6 · p. 30

Abstract

from arXiv · show

We study the verification problem for deep narrow ReLU neural networks: given a network of bounded width computing a piecewise-affine map on [0,1], does some input satisfy a prescribed output constraint? Classical NP-hardness proofs for ReLU verification use one neuron per Boolean variable and say nothing about networks of small constant width, while width-1 networks are easy to verify. We show that verification of ReLU networks is NP-complete at width 4 for arbitrary inputs in [0,1]. When inputs are restricted to a natural discrete encoding set, NP-completeness already holds at width 3. Together with polynomial-time decidability at width 1, this leaves open only width 2 on the encoding set, and widths 2 and 3 on [0,1]. The technical core is a fractal preprocessing gadget: a width-2 ReLU subnetwork whose iterate vanishes precisely near a finite Cantor-like subset of [0,1] with 2^n points. It reduces verification of a continuous function on [0,1] to verification on 2^n discrete points without increasing the width, and is the missing ingredient for width-bounded hardness reductions. The same construction yields further results at width 3 on the encoding set: the universal problem is coNP-complete, counting zeros is #P-complete, a majority variant is PP-complete, and approximating the minimum output within a constant gap inherited from Max-3Sat is NP-hard. The NP, coNP and inapproximability results lift to all of [0,1] at width 4; lifting counting and majority, and lifting at width 3, remain open.

1 Introduction

The paper studies how verification complexity changes when ReLU networks are deep but have bounded width, where existing SAT reductions using unrestricted width do not settle the narrow regime. It establishes hardness at width 3 on a discrete encoding set and width 4 for arbitrary inputs, using fractal preprocessing to bridge discrete and continuous verification.

Main contribution

  • Width 4 makes verification NP-complete on arbitrary inputs in [0, 1], while width 3 is NP-complete on the encoding set.The paper also leaves widths 2 and 3 open on [0, 1], and width 2 open on the encoding set.Source: §1 · p. 3

Why the narrow regime

  • Width-1 verification is polynomial-time decidable, whereas classical SAT reductions use one neuron per variable and therefore leave constant-width complexity unresolved.The paper frames width as a space-like resource: a bounded-width, unbounded-depth network iterates a constant-dimensional state.Source: §1 · pp. 2–3

Technical core

  • A width-2 ReLU map has an iterate vanishing near a finite Cantor-like set, reducing continuous verification to 2^n discrete points without increasing width.The reduction encodes 3-Sat using width-2 digit-extraction and clause-evaluation subnetworks, with one additional register for the fractal error in the width-4 construction.Source: §1 · p. 3
  • The gadget must preserve an exact zero set and a gap through clause layers with exponentially growing Lipschitz constants, while its calibrated slope is produced in polynomial time.The self-similar structure permits this error amplification to be handled with polynomial-size weights.Source: §1 · p. 3

A spectrum of width-3 hardness results

  • On the encoding set, width-3 verification also has coNP-complete universal, #P-complete counting, PP-complete majority, and NP-hard constant-gap approximation variants.The NP, coNP, and inapproximability results lift to arbitrary inputs at width 4; counting and majority lifting remain open.Source: §1 · pp. 3–4

Technical highlights

  • The {1, 3} digit encoding supports robust base-4 digit extraction, shifting, and testing, while a truncation gadget repairs near-miss encodings.The encoding uses a shared two-register state for digit processing and clause evaluation, with an extra register for the fractal error in the continuous-input reduction.Source: §1 · p. 4

2 Definition

The section fixes the rational ReLU network model and describes how discrete assignments are encoded as real inputs. The {1, 3} base-4 encoding leaves gaps that permit continuous digit extraction, while its Cantor-like geometry creates the preprocessing challenge addressed later.

2.1 Neural network model

  • A width-k feedforward ReLU network composes rational affine input and output maps with hidden layers of k ReLU neurons, and its encoding size counts the binary lengths of its rational entries.A ReLU neuron applies ReLU(t) = max(t, 0) to a rational affine function.Source: §2.1 · p. 4

2.2 Encoding discrete information into a real input: the digit-gap principle

  • Restricting base-4 digits to {1, 3} creates gaps that permit continuous digit extraction, unlike binary leading-bit encoding, whose intervals prevent a continuous extractor.The encoding set is Cantor-like, so arbitrary real inputs need preprocessing to certify membership or proximity before clause evaluation.Source: §2.2 · p. 5
  • The {1, 3}-quadradic encoding bijects Boolean assignments with a uniformly separated finite subset of [0, 1], and the same encoding can carry auxiliary flags and errors.Distinct length-n encodings differ by at least 2 · 4^-n.Source: §2.2 · p. 5

3 Auxiliary Results

The section develops width-disciplined ReLU gadgets for arithmetic and digit-level operations, building from efficient width-2 compilation of nested min/max expressions. These gadgets support leading-digit extraction, base-4 shifting, conditional tests, counting, and truncation or filtering.

Compilation of nested min/max expressions

  • Nested min/max expressions over rational affine forms compile efficiently into width-2 ReLU networks, with one layer per level while preserving the input register.The construction has depth at most the expression depth and polynomial bit-size weights.Source: §3 · p. 6

Leading-digit extraction

  • Nlead recovers the first base-4 digit when it is 1 or 3, and returns 1 when that digit is 0.The leading-digit map is continuous, piecewise affine, and realizable by a width-2, depth-2 network.Source: §3 · p. 7

Base-4 digit shift

  • Nshift outputs both x and shift(x), where shift removes the leading admissible base-4 digit by computing ReLU(4x − lead(x)).For inputs whose first digit is 1 or 3, the output shift(x) is the remaining base-4 expansion and lies in [0, 1].Source: §3 · p. 7

Conditional flag

  • Ntest composes a one-neuron affine preprocessing step with a width-2 network for g to compute the conditional test function.The proof checks the composition across cases for e and the allowed ranges of p.Source: §3 · pp. 7–8

Counting the 3s

  • NCount(n) adds the number of 3s among the first n base-4 digits from {0, 1, 3} to its input p, using an overall width of 3.Its state tracks the shifted input and count; each iteration increments the count only when the current digit is 3.Source: §3 · p. 9

Truncation and 0-digit filtering

  • NT(n) outputs a truncated value and shifted input; when the first n digits are 1 or 3, the truncated value is their base-4 prefix.With digits drawn from {0, 1, 3}, a zero digit sends the shifted state to zero, so later iterations retain only the earlier nonzero prefix.Source: §3 · p. 10

4 Results for inputs restricted to DD1,3

For inputs restricted to DD1,3, the section establishes complexity results for width-3 ReLU networks, including NP-completeness of zero verification, zero-counting and majority results, and gap-based hardness for approximating the minimum output. It also relates Dyadic-Uniform-Zero instances to unsatisfiability of the encoded formula.

4 Results for inputs restricted to DD1,3

  • Verification{1,3} is NP-complete at width 3 for {1,3}-quadradic inputs of length n, with polynomial-size rational weights and exact rational evaluation.A length-n digit sequence is a polynomial-size certificate: its encoded input can be evaluated in polynomial time.Source: §4 · p. 11

4.1 Reduction from 3-Sat

  • The width-3 reduction scans the encoded assignment digits clause by clause, and its output is zero exactly when the assignment satisfies the 3-CNF formula.Each clause subnetwork preserves the input register while updating a cumulative clause flag.Source: §4 · p. 11, §4.1 · p. 12

4.2 Correctness of the reduction

  • Correctness follows from invariants preserving the input register and encoding clause satisfaction in the base-4 digits of the output flag.The final flag is zero if and only if every clause is satisfied.Source: §4.2 · pp. 12–13

4.3 NP-hardness of Verification{1,3}

  • The polynomial-time reduction from 3-SAT, together with digit-sequence certificates for NP membership, establishes NP-completeness of Verification{1,3}.Completeness maps satisfying assignments to zero-output encodings; soundness maps any such encoding back to a satisfying assignment.Source: §4 · p. 11, §4.3 · p. 14

4.4 Variants and consequences

  • On DD1,3, width-3 variants include coNP-complete universal-gap and uniform-distance problems, #P-complete counting, PP-complete majority, and Max-3Sat inapproximability.The master construction outputs the number of unsatisfied clauses, equivalently m minus the number satisfied, linking these problems to 3-SAT and Max-3Sat.Source: §4.4 · pp. 15–16
  • Dyadic-Uniform-Zero is YES for the constructed instance exactly when the encoded formula is unsatisfiable.The supremum over DD1,3(n) is 0 for an unsatisfiable formula and 1 otherwise.Source: §4.4 · p. 16
  • A width-3 network’s zeros on DD1,3(n) correspond bijectively to satisfying assignments, making Counting-Zeros{1,3} #P-complete.The reduction from #3-Sat is parsimonious.Source: §4.4 · p. 16
  • Majority-Zero{1,3} is PP-complete for width-3 ReLU networks on DD1,3(n).The construction preserves the assignment count, so a strict majority of zero points corresponds to a strict majority of satisfying assignments.Source: §4.4 · p. 16
  • For every constant η > 0, approximating the minimum network output on DD1,3(n) within additive error (1/16 − η)m is NP-hard, via Håstad’s Max-3Sat gap.The YES case has minimum 0; the NO case has minimum at least (1/8 − η)m.Source: §4.4 · p. 17

5 The fractal gadget: Filtering from R to DD1,3

This section develops an iterated width-2 fractal filter that focuses inputs on a 2^n-point encoding set and uses it to lift discrete-assignment hardness to width-4 networks on [0,1], with a zero-versus-1/2 output gap. It also notes that width-1 verification remains polynomial-time decidable, while lifting the hardness result to width 3 remains open.

5 The fractal gadget: Filtering from R to DD1,3

  • Composing the approximation with the filter lifts the single-quantifier decision results to [0, 1] at the cost of one additional unit of width.The construction uses robustness parameter ε = 2^−O(m(m+n)) and preprocessing depth O(n).Source: §5 · p. 17, §5.3 · p. 22

5.1 Ideal discontinuous F

  • The ideal discontinuous map’s n-fold iterate vanishes exactly on DD1,3(n), with 2^n zeros, and each iteration refines the encoding’s Cantor-like structure.A single fixed map is reused at every iteration, enabling recognition at arbitrary levels without increasing the width.Source: §5 · p. 17, §5.1 · pp. 18–19

5.2 A continuous approximation Fε

  • The continuous width-2 approximation preserves zeros on DD1,3(n), while every spurious zero lies within ε·4^−(s−1) of a shorter encoding in DD1,3(s).This localization controls the zeros introduced by continuity and lets the filter repair them.Source: §5.2 · pp. 20–21

5.3 Lifting the hardness results from DD1,3 to [0, 1]

  • A width-4 ReLU network has an NP-complete zero test on [0, 1], obtained by combining the fractal gadget with a filter and clause subnetworks.The additional width carries the gadget’s error through the clause stages; only single-quantifier results transfer cleanly, not counting or majority results.Source: §5.3 · p. 22
  • The proof controls perturbations from the discrete encoding using Lipschitz bounds for the filter, clause cascade, and counter.The component bounds allow the construction to preserve the unsatisfiable output gap even when the input is near, rather than on, an encoded point.Source: §5.3 · pp. 24–25
  • Width-4 ReLU verification on [0,1] is NP-complete, and deciding whether every input has output at least 1/2 is coNP-complete.The reductions follow from the correctness theorem for the constructed network.Source: §5.3 · p. 26
  • A separate corollary gives a uniform-distance decision result on [0,1] for width-4 networks while preserving width 4.Source: §5.3 · p. 26
  • Width-4 verification on [0, 1] is NP-hard for a constant-gap promise, via a Max-3Sat gap reduction that scales the fractal error by the number of clauses.The construction preserves width, and its minimum is zero when the formula is satisfiable; the gap reduction gives a positive lower bound in the unsatisfiable case.Source: §5.3 · p. 27
  • Lifting the hardness results to width 3 remains open because the network has no room to carry the fractal error through clause stages without breaking correctness on some repaired orbits.Using the error as the first clause stage’s flag fails for inputs whose orbit enters the repair region from the side producing digit-2 prefixes.Source: §5.3 · p. 27

5.4 The other end of the scale: width 1

  • Width-1 ReLU networks decide both zero verification on [0, 1] and on DD1,3(n) in polynomial time, since they compute monotone piecewise-affine functions with at most 2L + 2 pieces.Their zero set on [0, 1] is an interval; intersection with DD1,3(n) can be checked by greedy digit-by-digit descent in base 4.Source: §5.4 · p. 28
  • Unary-time reachability for iterated width-1 ReLU networks is decidable in polynomial time by propagating reachable sets as unions of intervals.For m affine pieces, each time step uses O(m log m) time and maintains at most O(m) intervals; unary encoding of the time bound makes the total runtime polynomial.Source: §5.4 · pp. 28–29

6 Summary and open problems

The paper classifies verification complexity for deep narrow ReLU networks and identifies a width-2 fractal preprocessing gadget as the core of its lifting results. Width 2 remains open on the encoding set, while widths 2 and 3 remain open for arbitrary inputs in [0,1].

Complexity classification

  • At width 3 on the encoding set, verification is NP-complete, with coNP-, #P-, and PP-completeness and Max-3Sat-gap inapproximability also established.At width 4, the NP, coNP, and inapproximability results lift to arbitrary inputs in [0,1].Source: §6 · p. 29

Open problems

  • Width 1 is tractable, leaving only width 2 open on the encoding set and widths 2 and 3 open for arbitrary inputs in [0,1].The paper also leaves open whether counting and majority completeness lift to [0,1], which would require an injective filter, and whether the lift can be done at width 3.Source: §6 · pp. 29–30

Fractal preprocessing

  • The width-2 map Fε has an iterate that vanishes precisely near the 2^n-point discrete encoding set, a Cantor-like level refined at each iteration.This fractal preprocessing encodes an exponential-size discrete search space using only two units of width.Source: §6 · pp. 29–30
  • The authors expect the fractal technique to transfer to other width-constrained continuous-computation models that reduce discrete problems to continuous verification without increasing state dimension.Source: §6 · p. 30
Loading 2610.06092v1…