betaFeedback

WorksComputer Science

The Complexity of ReLU Network Synthesis from a Parameter Multiset

Abstract

We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, and a bound on the number of neurons (output included). The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture. Matching two labeled examples exactly is already NP\mathsf{NP}-complete, so we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is Σ2PΣ_2^{\mathsf P}-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in DP\mathsf{DP} for every fixed neuron bound and is DP\mathsf{DP}-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is Σ2PΣ_2^{\mathsf P}-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is NPPP\mathsf{NP}^{\mathsf{PP}}-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess.

Introduction

Knowing every parameter value of a neural network does not yet determine the network. One must still decide which values become weights and which become biases, which neurons each weight connects, and which computed values later neurons share. This paper asks how hard these decisions are when the required behavior of the network is given by a compact specification.

An instance consists of a multiset WW of rational numbers, called the inventory, a cap on the number of computational neurons, and a target. A repeated value supplies separate occurrences: three copies of 1 permit three uses. A candidate is a network built from the inventory: each of its edges consumes one occurrence, and so does each neuron’s bias, which may also be absent. We study two rules for the inventory: at-most-once use, which may leave occurrences unused, and exactly-once use, which must consume every occurrence; every problem below has a version for each rule.

Within the cap, the graph may have any depth, width, skip connections and fan-out, and its scalar output is affine. The cap counts the output neuron, but it does not bound the input dimension or the size of the target. When the target is itself a network, its parameters need not belong to WW and do not consume occurrences.

The model separates which numbers are available from how the network is built. Related formulations constrain the structure more. In permutation training, Cai, Chen, and Qiao [4] rearrange the output coefficients over a prescribed univariate hinge basis. Arithmetic expression construction [1] assigns supplied numbers to the positions of an expression tree. Here one inventory supplies every weight and bias, and computed values may be shared. The simplest specification, a list of labeled examples, is already hard: two explicit samples give an NP-complete feasibility problem with positive integer parameters (Theorem 3.3). Our main question is how specifications that constrain the behavior on all inputs, or on average over a probability distribution, change this baseline.

The specifications we study ask for different kinds of agreement. Exact reproduction of a Boolean circuit requires agreement on every Boolean input, and exact reproduction of a supplied ReLU network requires agreement on every real input. Uniform approximation requires agreement within a tolerance on a box. A population-risk specification instead compares the mean squared error with a rational threshold, under the uniform distribution on the Boolean cube, the uniform distribution on the unit cube, or the standard Gaussian distribution. In each case the candidate’s graph is part of the witness. Hardness for a prescribed graph therefore does not give hardness here, because another legal placement of the same numbers may meet the same specification. Excluding every such alternative graph and placement is the central difficulty in our reductions.

Even an elementary change of realization can violate the inventory constraint. Write ρ(t)=max⁡{0,t}\rho(t)=\max\{0,t\}. The identity ρ(x)=12ρ(2x)\rho(x)=\frac{1}{2}\rho(2x) rescales one hidden neuron without changing its function. The left side uses two occurrences of 1, one on the input edge and one on the output edge. The right side uses 2 and 1/21/2 instead, which the inventory W=(1,1)W=(1,1) does not supply. A functional identity therefore need not preserve a legal assignment of occurrences. Our reductions must control every realization that the actual inventory permits, including graphs different from the one used to encode a source witness.

The existential-universal verification pattern behind our second-level upper bounds is established. Existential choice followed by universal verification already arises in succinct circuit minimization [2], and it underlies the second-level completeness results for formula minimization [3 Jaa26]. Equivalence of ReLU networks has a standard coNP verification procedure based on activation patterns and linear constraints [Wur24]. Our contribution is to determine how a consumable numerical inventory interacts with these verification requirements, and with the counting that population risk involves. The hardness results distinguish these sources of complexity at small caps: every synthesis hardness result holds with at most four computational neurons, except the exactly-once versions of Boolean risk, whose cap is the size of the inventory.

Two findings organize the classifications below. The first concerns exact agreement with a ReLU network on all real inputs. For a fixed cap, a polynomial-size set of test inputs separates all candidates that compute different functions, which gives a DP upper bound, tight at cap three, instead of only the general existential-universal bound. Uniform approximation on a compact box behaves differently: even one affine candidate with identical positive inventory values gives second-level completeness. In both comparisons the input dimension and the target size are unrestricted. The second finding concerns population risk, where the main issue is to preserve a numerical choice through an average. Exact continuous synthesis must retain the sign of a rational weighted sum even when that sum is zero. The construction achieves this by canceling a source-dependent second moment, without assuming a positive accuracy gap.

Our Results

Table 1 summarizes the classifications, with all numbers encoded in binary and running times measured in the binary input length.

SpecificationGuarantee
Two explicit samplesNP-complete with positive integer inventory and cap one (Theorem 3.3).
Boolean-circuit equalityΣ2P\Sigma^P_2-complete with cap four, even for monotone threshold targets (Theorem 4.12).
Full-space ReLU equalityIn DP for every fixed cap; cap three is DP-complete; cap two is coNP-complete under at-most-once use (Theorems 5.3, 5.4 and 5.9).
Exact Boolean squared riskNPPP^{\mathrm{PP}}-complete: integer inventory, cap two for at-most-once use, cap ∣W∣|W| for exactly-once use (Theorem 7.1).
Uniform approximation on a boxΣ2P\Sigma^P_2-complete with cap one and identical positive inventory values (Theorem 6.2).
Exact continuous uniform squared riskComplete for the discrete existential closure of exact rational weighted counting; integer-inventory cap-two hardness under both inventory rules (Theorem 8.8).
Continuous uniform or standard Gaussian squared risk with a binary gapNPPP^{\mathrm{PP}}-complete with integer inventory and cap two (Theorems 8.6 and 9.5).

Table 1. Synthesis from a parameter multiset. Caps count the affine output. Both inventory rules are included unless stated otherwise.

SpecificationGuarantee
Standard Gaussian squared risk with fixed absolute gap 1/41/4NPPP\mathrm{NP}^{\mathrm{PP}}-complete with integer inventory and cap two; unbounded loss and a variable threshold (Corollary 9.6).

Table 2.

The first row is the numerical baseline. Its two-sample construction excludes every hidden graph, even when a larger cap is permitted. Our main results concern the implicit specifications in the remaining rows. We first treat the universal requirements and then ask how averaging changes their verification.

Universal specifications. The Boolean target in the next theorem is a monotone threshold function with positive coefficients, which is simple to realize when real weights may be chosen freely. Its difficulty arises from the prescribed occurrences and their possible placements.

Theorem 1.1 (Informal; restated as Theorem 4.12). Boolean-circuit exact synthesis is Σ2P\Sigma^P_2-complete under either inventory rule. Hardness holds with four computational neurons, including the affine output, even when the target is a monotone threshold with positive coefficients.

A target defined on all real inputs changes the classification at a fixed cap. In the next theorem the candidate cap is constant, while the rational ReLU target and the input dimension remain part of the input.

Theorem 1.2 (Informal; restated as Theorem 5.4; see also Theorems 5.3 and 5.9). Full-space ReLU-target synthesis lies in DP for every fixed computational cap under either inventory rule. Cap three is DP-complete under both rules. Under at-most-once use, cap two is coNP-complete.

A problem belongs to DP when it is the conjunction of an NP condition and a coNP condition. The upper bound comes from finitely many separating evaluations, not from listing all candidate functions in polynomial time.

The two conditions have separate sources in the hardness proof. An explicit affine target already gives NP-completeness at cap three (Theorem 5.8), and requiring equality with an arbitrary ReLU target adds the universal condition. When the cap grows with the input, the full-space problem lies between the DP lower bound and the second-level upper bound, and its exact classification is open. The Boolean theorem does not resolve it, because agreement at the vertices of the cube need not extend to agreement on all real inputs.

Uniform approximation on a compact domain. Changing the domain and the error requirement yields a different fixed-cap classification.

Theorem 1.3 (Informal; restated as Theorem 6.2). Uniform approximation of a supplied rational ReLU target on the unit box is Σ2P\Sigma^P_2-complete, under either inventory rule, already at tolerance one with one affine computational neuron and an inventory of identical positive rational occurrences.

The construction first establishes completeness for explicitly listed multilinear polynomial targets of degree at most five and affine candidates, and a Lovász extension then turns these targets into ReLU targets. The domain and the error requirement therefore matter even when the candidate has no hidden neuron.

Population-risk specifications. The risk results keep the same occurrence constraint, but replace universal agreement by a threshold on an average. For Boolean inputs, verifying a candidate means summing over a finite cube. For continuous inputs, the risk becomes a weighted count whose terms may have different rational denominators. Exact rational weighted counting, the counting model used for continuous inputs, sums a rational weight over all binary strings of a polynomially bounded length. Each weight is a short rational computed exactly in polynomial time, and different weights may have different denominators. The associated decision class asks whether this sum is at least a rational threshold, also computed exactly in polynomial time. Its discrete existential closure allows one polynomial-length binary choice before a single such comparison; it does not allow arbitrary adaptive oracle access. The formal definitions appear in Sections 8 and 8.3.

Theorem 1.4 (Informal; restated as Theorem 7.1; see also Theorems 8.2 and 8.8). *Under uniform Boolean inputs, exact squared-risk synthesis is NPPP\mathrm{NP}^{\mathrm{PP}}-complete under either inventory rule. Hardness

uses an integer inventory and target labels in {−1,+1}\{-1,+1\}, with cap two for at-most-once use and cap ∣W∣|W| for exactly-once use. Under continuous uniform inputs on the unit cube, comparing the squared risk between two supplied networks with a threshold is complete for exact rational weighted counting, even in one dimension when one of the two networks is zero. Synthesis is complete for its discrete existential closure, with integer-inventory cap-two hardness under either inventory rule.

For Boolean inputs, target labels in {0,1}\{0,1\} also give NPPP\mathrm{NP}^{\mathrm{PP}}-completeness when the inventory consists of integers and exactly one occurrence of 1/21/2 (Corollary 7.4).

Exact continuous risk also has an obstruction of a different kind, concerning the size of the risk value itself. Some bounded one-dimensional dyadic targets have descriptions of length O(nlog⁡n)O(n\log n), yet their exact risk denominators require Ω(2n)\Omega(2^n) bits (Theorem 8.4). This shows only that the exact value can be too long to print; it does not separate classes of threshold decision problems. Neither exact-risk classification asserts hardness at a fixed bounded-loss accuracy.

Accuracy gaps and Gaussian inputs. The remaining risk results relax the exact threshold by a gap. In the binary-gap version, in YES instances some legal candidate has risk at most τ\tau, and in NO instances every legal candidate has risk at least τ+δ\tau+\delta, where δ>0\delta>0 is supplied in binary and may be exponentially small. For such a promise problem, membership means that some problem in the stated class, a total separator, accepts every YES instance and rejects every NO instance. Hardness is under deterministic polynomial-time many-one promise reductions, which map YES and NO instances of the source to YES and NO instances, respectively.

Theorem 1.5 (Informal; restated as Theorem 8.6; see also Theorem 9.5). For continuous uniform inputs and for standard Gaussian inputs, binary-gap squared-risk synthesis is NPPP\mathrm{NP}^{\mathrm{PP}}-complete under either inventory rule, with integer inventory and cap two.

For Gaussian inputs, the exact positive-threshold problem has the corresponding lower bound, but Theorem 9.5 supplies no upper bound for it.

Scaling the inventory and the target keeps the Gaussian node cap and enlarges the absolute gap to the fixed value 1/41/4, while retaining NPPP\mathrm{NP}^{\mathrm{PP}}-completeness under both rules (Corollary 9.6). This consequence uses unbounded squared loss and a supplied positive threshold that may be numerically large. It gives no classification for a fixed threshold, a relative gap, or a clipped loss.

Our Techniques

Because the graph is chosen together with the placement of the numbers, each reduction must control every network that the inventory can build, not only the intended one. The paragraphs below describe the device each reduction uses for this purpose.

Controlling every occurrence placement. The finite-sample reduction adds a large common positive offset to every source number. An all-ones sample then excludes every path that multiplies two parameters, so all occurrences must lie in a single affine output. A second sample, through its zero and one coordinates, selects a subset of prescribed cardinality. This establishes the numerical baseline without prescribing the graph.

The Boolean reduction needs a stronger converse. Its source problem asks for a small set of forbidden occurrences that intersects every subset with a specified sum. We prove this restricted blocker problem complete by a quantified-CNF construction, together with congruence and nonpower promises that the network proof uses. Two shifted ReLUs implement a threshold ramp, an established representation [35]. With threshold PP, width w>0w>0, and shared affine score SS, the intended output is

ρ(S−(P−w))−ρ(S−P)w.\frac{\rho(S-(P-w))-\rho(S-P)}{w}.

It is zero when S≤P−wS\le P-w and one when S≥PS\ge P. Small changes to the score encode forbidden source occurrences. The challenge is to force every successful candidate with four computational neurons into this common-score form, with the two copies of each coefficient paid for by distinct supplied occurrences. An alternative placement of a gain as a bias, or an extra path through a shared vertex, would otherwise invalidate extraction of the source choice.

The target’s inputs include several query blocks, groups of coordinates that are repeated so that some block stays free of unintended parameters. The proof begins with an obstruction visible on one two-coordinate face of the target restricted to a query block. On this face the target is an OR: its four values are 0,1,1,10,1,1,1, so the mixed difference is 1−1−1+0=−11 - 1 - 1 + 0 = -1. Helmbold and Long’s supermodularity property [21 Lemma 12] implies that a ReLU network with nonnegative edge weights has nonnegative mixed differences on Boolean inputs, even with arbitrary biases (Lemma A.4). It therefore cannot realize this face.

This obstruction alone does not identify the candidate, and two separated numerical scales give stronger restrictions: Boolean output equalities become formal identities under each witness’s actual activation masks. Replication leaves an uncontaminated query block, on which these identities exclude all unintended gain and negative-parameter positions. The full target then identifies the shared score, and anchor inputs recover a source blocker. Section A gives a structural map and the complete case analysis.

Separating finitely many candidate behaviors. For a fixed cap, a disagreement between two candidates has a witness supported on a constant number of input coordinates. The bound counts their hidden preactivations and one output difference. Enumerating local graphs on those subspaces yields a polynomial set of separating inputs. All legal candidates consistent with the target on the separating inputs compute the same function on the full space. Synthesis therefore requires a consistent candidate and the absence of any consistent candidate that disagrees with the target elsewhere. Existence of a consistent candidate is one NP condition; existence of a consistent disagreeing candidate is a second NP condition. Taking the first condition and the complement of the second gives the DP upper bound.

For the matching lower bound at cap three, shifted numerical matching forces the two output gains to be unit occurrences. The remaining required positions exhaust the inventory and exclude an internal hidden edge. A separate target slice encodes unsatisfiability, supplying the second conjunct of DP hardness.

Uniform error through covering. For compact approximation, a one-node candidate chooses feature coordinates for a succinct set cover. Two selector coordinates calibrate all possible bias and nonfeature placements away. Local circuit constraints form a multilinear penalty, whose consistent Boolean vertices require the chosen sets to cover every input. Multilinearity extends the inequalities to the entire box. The standard Lovász extension [19] produces a rational ReLU target with the same vertex values and the same uniform-error test against each affine candidate.

Preserving choice in an average. For Boolean risk, parity blocks hide source random bits from every candidate reading only the number of coordinates its inventory permits. We use the parity device of Koriche, Lagniez, and Tran [25] with existential-majority satisfiability [28]. An integer-valued pointwise quadratic inequality excludes all unintended candidates.

For the upper bound on continuous risk, activation masks and complete flags of polytope faces write the risk as a sum of simplex integrals, each a short rational summand of a counting problem. For the lower bound, tent folding [33] decodes words into dyadic intervals, and narrow triangular payloads realize reciprocal denominators and numerator multiplicities. Balanced occurrence pairs restrict low-risk candidates with two computational neurons to corner functions encoding existential strings. A continuous modular-sharing construction, based on the uniform sharing of Chor and Kushilevitz [6 Section 4], keeps a virtual uniform coordinate independent of every affordable raw-coordinate observation. The exact construction must do more than the binary-gap reduction. Smoothing an encoded bit perturbs the risk, and such a perturbation can reverse a comparison in which the source sum equals zero. Writing TT for the target and NN for a legal candidate, expand the loss as

E[(T−N)2]=E[T2]+E[N2]−2E[NT].\mathbb{E}\left[(T-N)^2\right] = \mathbb{E}\left[T^2\right] + \mathbb{E}\left[N^2\right] - 2\mathbb{E}\left[NT\right].

The aim is to keep the source sum in the cross term while the target energy E[T2]\mathbb{E}[T^2] stays independent of that sum. For a fixed nonnegative envelope height UU, the payload BB, integrated over its hidden uniform coordinate, satisfies

3∫B2=2U∫B.3\int B^2 = 2U\int B.

Two positive copies on zero background and one negative copy on background UU, each occupying an interval of length λ\lambda, change the energy by λ(3∫B2−2U∫B)=0\lambda(3\int B^2 - 2U\int B) = 0. Their first-moment change is still λ∫B\lambda\int B. Conditional independence makes this retained mean available against every permitted candidate; the numerical separation argument then excludes all candidates except those encoding source choices.

Thus the threshold comparison preserves the sign of the source sum, including equality, rather than replacing it by a promised gap (Theorem 8.8).

For Gaussian inputs, a sign decoder and an independent homogeneous amplitude give the forced-zero counting lower bound. The use of Boolean-to-Gaussian lifting follows earlier learning-hardness constructions [12, 5]. To encode existential choice, opposite unit occurrences on paired coordinates define rare hinges. Their small cross moments preserve the source signal, while a second Hermite coefficient excludes every competing cap-two placement. Uniform growth, tail and Lipschitz bounds turn continuous risk with a binary gap into a polynomial-time fair-bit counting experiment. Finally, scaling all inventory occurrences and the target enlarges the Gaussian absolute gap; the proof separately controls the candidates’ affine skip terms.

Other Related Work

We compare our results with three further lines of work: circuit minimization and neural verification, numerical resource constraints and training, and integration and counting.

Minimization and neural verification. Circuit minimization from truth tables [31] differs from a succinctly supplied target; the latter already leads to existential-universal verification [2]. Buchfuhrer and Umans [3] and Jaakkola [Jaa26] establish second-level completeness for Boolean formula minimization. Their formula-tree occurrence constraints do not identify the possible sharing and numerical placements of a ReLU graph. Williams’s exact Boolean representation results [35] concern freely chosen real coefficients and therefore do not impose the supplied numerical resource constraint.

Wurm’s neural verification framework [Wur24] includes equivalence via activation patterns and linear constraints. His finite-alphabet universal-trigger problem is Σ2P\Sigma^{P}_{2}-complete [Wur26, Theorem 5.2], so second-level neural decision problems precede this work. Those choices modify inputs of a fixed network; ours consume weight and bias occurrences while choosing a graph with a constant computational cap. Lee [27] studies minimizing the hidden-neuron count under positive-tolerance LpL^{p} approximation with freely chosen real parameters and two hidden layers. Its approximation guarantee and numerical freedom differ from full-space exact synthesis with a fixed inventory.

Parameter symmetries give a different tractable equivalence regime. Gegenfurtner, Grillo, and Montúfar [15 Proposition 14] give a polynomial-time equivalence test for two generic parameter choices in the same three-layer bottleneck architecture. In their architecture, the first hidden layer is no wider than the input. Our fixed-cap synthesis theorem searches over occurrence placements and arbitrary permitted graphs, allows degenerate parameters, and leaves the target size unrestricted.

Numerical resources and training. Permutation training [4] assigns output coefficients over a prescribed hinge basis, whereas our single inventory governs every parameter position. Arithmetic expression construction [1] uses expression trees and supplied occurrences, rather than shared ReLU graphs. Doron-Arad and Mossel [DAM26] prove NP-completeness for finite-sample ReLU training with polynomial-bit rational parameters on a supplied architecture. Our finite-sample theorem restricts all parameters to an input multiset and permits alternative architectures; the higher classifications concern implicit specifications. Subset-sum interdiction fits the general blocking framework of Grüne and Wulf [20]; our source lemma proves the additional arithmetic promises directly. The distinct-number numerical matching premise for cap-three hardness is due to Hulett, Will, and Woeginger [22 Appendix, Corollary 8].

Integration and counting. We use the exact polynomial-time rational-weight model of de Campos, Stamatopoulos, and Weyland [10], and distinguish it from their broader approximation-defined model. The general arithmetic upper bound we quote is Meiburg’s recent preprint [29]. Feischl, Gräßle, and Zehetgruber already use folding to establish fixed-dimensional ReLU quadrature hardness [14]. Morettin, Passerini, and Sebastiani formulate probabilistic neural verification through weighted model integration [30]. Our exact continuous classification gives reciprocal rational-weight realization and then preserves existential numerical choice in synthesis. Lawrence’s long polytope-volume denominators [26] precede the output-size phenomenon; our example uses one real coordinate and dyadic network parameters.

The Gaussian counting reduction concerns threshold comparison, whereas Rannen-Triki et al. [32] study whether a supplied ReLU realization has zero norm. Gaussian agnostic learning of a freely chosen ReLU [16] has sample access and a different output requirement. Neither that learning problem nor smooth perturbations of Boolean data replace the single standard Gaussian probability distribution used here.

Discussion

The same finite-inventory model accommodates four different requirements: universal Boolean agreement, agreement as piecewise-affine functions on all real inputs, uniform approximation on a compact box, and an average squared loss. In each case the proof must combine the verification mechanism with a numerical choice that survives every alternative architecture. The resulting classes are not ordered by neuron count alone. The input domain, the target representation and the promise guarantee change the class to which our results assign the problem, and the inventory rule changes the caps at which our hardness proofs apply. For example, the Boolean-risk hardness uses cap two only under at-most-once use, and cap ∣W∣|W| under exactly-once use. Two-neuron hardness under both inventory rules holds for the continuous uniform and Gaussian results.

The exact continuous classification and the binary-gap classifications answer different questions. A binary gap may be exponentially small, and the fixed absolute Gaussian gap allows both unbounded squared loss and growing thresholds. Neither result establishes hardness of bounded-loss approximation at a fixed accuracy. Nor can one decide whether a Gaussian risk equals a rational threshold by enumerating candidates and approximating each risk, since approximations do not certify equality.

Open Problems

We close with four open questions. The first concerns exact synthesis on the full space when the cap grows with the input; the other three concern risk synthesis and arise from the distinctions just drawn between the exact and the gap classifications.

Unrestricted full-space exact synthesis. Fixed-cap membership in DP and cap-three hardness leave open how the complexity changes when the cap grows with the input. With the cap part of the input, the problem is DP-hard by Theorem 5.9 and belongs to Σ2P\Sigma_{2}^{\mathrm{P}} by Theorem 5.2; the paper does not determine where it lies between these bounds.

Open Problem 1. Determine the exact deterministic polynomial-time many-one reduction complexity of full-space synthesis for a supplied rational ReLU target, a rational inventory used at most once, arbitrary permitted graphs, and an affine output. In particular, determine whether it is Σ2P\Sigma_{2}^{\mathrm{P}}-complete.

Clipped risk with an inverse-polynomial gap. For uniform Boolean inputs, define the clipped risk by

R‾T(N)=E[min⁡{1,(N(X)−T(X))2}].\overline{R}_{T}(N)=\mathbb{E}[\min\{1,(N(X)-T(X))^{2}\}].

The input supplies 0<δ≤10<\delta\le1, 0≤τ≤1−δ0\le\tau\le1-\delta, and a unary string of length ⌈1/δ⌉\lceil1/\delta\rceil, so the gap is at least inverse-polynomial in the input length. In YES instances some legal candidate has clipped risk at most τ\tau; in NO instances every candidate has clipped risk at least τ+δ\tau+\delta.

Open Problem 2. Determine the deterministic polynomial-time many-one promise-reduction complexity of this clipped-risk synthesis problem for a rational inventory used at most once, an independent rational ReLU target and an affine output. In particular, determine whether it is complete for MA.

Here MA permits a polynomial certificate followed by a randomized polynomial-time check. The exact-risk reductions may distinguish only an exponentially rare assignment fiber; clipping does not amplify its probability.

Exact standard-Gaussian comparison. The binary-gap theorem gives no algorithm for deciding exact equality with a positive threshold.

Open Problem 3. Determine whether standard-Gaussian squared-risk synthesis is decidable for an independent rational ReLU target, a rational inventory used at most once, a node cap, an explicitly listed dimension and a positive rational threshold. If it is, determine its deterministic polynomial-time many-one reduction complexity.

Theorem 9.5 already gives an NPPP\mathrm{NP}^{\mathrm{PP}} lower bound with integer inventory and cap two.

Fixed Gaussian thresholds. Scaling to a fixed absolute gap changes the threshold; it does not settle the following normalized question.

Open Problem 4. Determine the exact deterministic polynomial-time many-one promise-reduction complexity of standard-Gaussian squared-risk synthesis, with YES risk at most one and NO risk at least 5/45/4, an independent rational ReLU target, a rational inventory, an explicitly listed dimension and an affine output. Treat both inventory rules. In particular, determine whether it is Σ2P\Sigma_{2}^{\mathrm{P}}-complete.

AI Disclosure

This work was developed with substantial assistance from Codex and Claude Code. These tools were used to discover almost all of the proofs in this work, find relevant literature, and write parts of the prose; the author wrote the rest. The author posed the problem, guided the development, and is responsible for any errors.

Paper Organization

Section 2 defines the network and inventory conventions, and Section 3 proves the finite-sample baseline. Section 4 proves the Boolean exact classification, with its complete placement converse in Section A. Section 5 treats exact ReLU targets on all real inputs and the fixed-cap classifications. Section 6 treats uniform approximation on a compact box. Sections 7 to 9 treat population squared risk under the three input probability distributions.

Preliminaries

We write R,Q,Z\mathbb{R},\mathbb{Q},\mathbb{Z} for the real numbers, rational numbers and integers. Unless another encoding is explicitly specified, integer inputs are encoded in binary, and a rational input is encoded by a signed integer numerator and a positive integer denominator. The binary input length is the total number of bits in these encodings and the explicitly supplied graphs and coordinate lists. For a nonnegative integer rr, write [r]={1,…,r}[r]=\{1,\ldots,r\}, with [0]=∅[0]=\varnothing. The symbols ⌊t⌋,⌈t⌉\lfloor t\rfloor,\lceil t\rceil denote the greatest integer at most tt and the least integer at least tt, respectively. For an integer r≥0r\ge0, r!=∏i=1rir!=\prod_{i=1}^{r}i, with 0!=10!=1; empty sums and products have values zero and one, respectively. An expression poly⁡(L)\operatorname{poly}(L) denotes a fixed polynomial bound in the input length LL. For nonnegative functions of an integer variable, f=O(g)f=O(g) means f≤Cgf\le Cg eventually for a constant C>0C>0, while f=Ω(g)f=\Omega(g) means f≥cgf\ge cg eventually for a constant c>0c>0. Logarithms are natural unless a base is displayed.

Let d≥1d\ge1 be an integer, the input dimension, and write x=(x1,…,xd)∈Rdx=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d} for an input. For vectors a,x∈Rda,x\in\mathbb{R}^{d}, their dot product is a⋅x=∑j=1dajxja\cdot x=\sum_{j=1}^{d}a_{j}x_{j}. The vector eje_{j} has coordinate one at jj and zero elsewhere; 1\mathbf{1} denotes the all-ones vector in the stated dimension. The support of a vector is the set of coordinates where it is nonzero. Write ∥x∥2=(∑jxj2)1/2\lVert x\rVert_{2}=(\sum_{j}x_{j}^{2})^{1/2} for its Euclidean length and ∥x∥∞=max⁡j∣xj∣\lVert x\rVert_{\infty}=\max_{j}|x_{j}| for its infinity norm.

An affine form is b+a⋅xb+a\cdot x, where a∈Rda\in\mathbb{R}^{d} and b∈Rb\in\mathbb{R}; it is linear when b=0b=0. An affine hyperplane is {x:a⋅x=b}\{x:a\cdot x=b\} with a≠0a\ne0. The vector aa is a normal vector to this hyperplane. The corresponding closed and open affine halfspaces are {x:a⋅x≤b}\{x:a\cdot x\le b\} and {x:a⋅x<b}\{x:a\cdot x<b\}. An open ball with center xx and radius ε>0\varepsilon>0 is {y:∥y−x∥2<ε}\{y:\lVert y-x\rVert_{2}<\varepsilon\}. A set is open if each of its points has an open ball contained in the set. The interior of any set consists of all points with such a ball contained in the set.

Write ρ(t)=max⁡{0,t}\rho(t)=\max\{0,t\} for the ReLU function. A function f:R→Rf:\mathbb{R}\to\mathbb{R} is convex if

f(λu+(1−λ)v)≤λf(u)+(1−λ)f(v)(u,v∈R,0≤λ≤1).f(\lambda u+(1-\lambda)v)\le\lambda f(u)+(1-\lambda)f(v)\qquad(u,v\in\mathbb{R},0\le\lambda\le1).

For f=ρf=\rho, the right side is both nonnegative and at least λu+(1−λ)v\lambda u+(1-\lambda)v, so it is at least their maximum ρ(λu+(1−λ)v)\rho(\lambda u+(1-\lambda)v), the left side; hence ρ\rho is convex.

Write W=(w1,…,wm)W=(w_{1},\ldots,w_{m}) for the inventory, an explicitly listed multiset of m≥1m\ge1 rational numbers, where mm is an integer, and let nmax⁡≥1n_{\max}\ge1 be an integer, the cap on the number of computational vertices (also called the computational-node budget). A multiset permits repeated values, and its indices distinguish their occurrences. The operation ⊎\uplus joins multisets while retaining every occurrence.

A directed graph consists of vertices and edges (u,v)(u,v) pointing from uu to vv. A directed path follows a sequence of such edges; a directed cycle is a nonempty path returning to its starting vertex. A graph is acyclic when it has no directed cycle. A topological order lists its vertices so every edge points forward. The empty graph has the empty order. Every nonempty finite acyclic graph has a vertex with no incoming edge, since otherwise repeatedly following incoming edges would revisit a vertex and give a cycle. Removing that vertex and repeating lists the vertices of the graph in a topological order. A predecessor of vv is a vertex uu with an edge (u,v)(u,v).

References

  1. [1]Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang. Arithmetic expression construction. In 31st International Symposium on Algorithms and Computation, volume 181 of Leibniz International Proceedings in Informatics, pages 12:1–12:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2011.11767
  2. [2]Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469–496, 2017.
  3. [3]David Buchfuhrer and Christopher Umans. The complexity of Boolean formula minimization. Journal of Computer and System Sciences, 77(1):142–153, 2011.
  4. [4]Yongqiang Cai, Gaohang Chen, and Zhonghua Qiao. Neural networks trained by weight permutation are universal approximators. Neural Networks, 187:107277, 2025.
  5. [5]Sitan Chen, Aravind Gollakota, Adam R. Klivans, and Raghu Meka. Hardness of noise-free learning for two-hidden-layer neural networks. In Advances in Neural Information Processing Systems, volume 35, 2022.arxiv.org/abs/2202.05258
  6. [6]Benny Chor and Eyal Kushilevitz. Secret sharing over infinite domains. Journal of Cryptology, 6:87–95, 1993.
  7. [7]Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, pages 151–158. ACM, 1971.DOI
  8. [10]Cassio P. de Campos, Georgios Stamoulis, and Dennis Weyland. A structured view on weighted counting with relations to counting, quantum computation and applications. Information and Computation, 275:104627, 2020.
  9. [11]Pierre Dusart. Estimates of some functions over primes without R.H. arXiv:1002.0442v1, 2010.
  10. [12]Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1358–1394. PMLR, 2021.arxiv.org/abs/2101.08303
  11. [13]Pál Erdős. Beweis eines satzes von Tschebyschef. Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum, 5:194–198, 1932.
  12. [14]Michael Feischl, Benedikt Gräßle, and Fabian Zehetgruber. Computational math with neural networks is hard. arXiv:2505.17751v2, 2026.arxiv.org/abs/2505.17751
  13. [15]Johanna Marie Gegenfurtner, Moritz Grillo, and Guido Montúfar. The symmetries of three-layer ReLU networks. arXiv:2605.18319v1, 2026.arxiv.org/abs/2605.18319
  14. [16]Surbhi Goel, Sushrut Karmalkar, and Adam R. Klivans. Time/accuracy tradeoffs for learning a ReLU with respect to Gaussian marginals. In Advances in Neural Information Processing Systems, volume 32, 2019.
  15. [17]Peter Gács and László Lovász. Khachian’s algorithm for linear programming. Technical Report STAN-CS-79-750, Stanford University, Department of Computer Science, 1979.
  16. [18]Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981.DOI
  17. [19]Michel Grabisch, Jean-Luc Marichal, and Marc Roubens. Equivalent representations of set functions. Mathematics of Operations Research, 25(2):157–178, 2000. Cited Section 4 in the revised author version.
  18. [20]Christoph Grüne and Lasse Wulf. The complexity of blocking all solutions. Theoretical Computer Science, 1069:115820, 2026.
  19. [21]David P. Helmbold and Philip M. Long. Surprising properties of dropout in deep networks. Journal of Machine Learning Research, 18(200):1–28, 2018.
  20. [22]Heather Hulett, Todd G. Will, and Gerhard J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Operations Research Letters, 36(5):594–596, 2008. Cited Section 2 and Appendix, Corollary 8, in the accepted manuscript.DOI
  21. [25]Frédéric Koriche, Jean-Marie Lagniez, and Chi Tran. Probabilistic linear explanations. arXiv:2609.19077v1, 2026.arxiv.org/abs/2609.19077
  22. [26]Jim Lawrence. Polytope volume computation. Mathematics of Computation, 57(195):259–271, 1991.
  23. [27]Sangrock Lee. NP-hardness of minimizing neurons in two-hidden-layer ReLU neural networks. arXiv:2610.11313v1; IEEE Transactions on Pattern Analysis and Machine Intelligence 48(11), 2026.
  24. [28]Michael L. Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilistic planning. Journal of Artificial Intelligence Research, 9:1–36, 1998.DOI
  25. [29]Alex Meiburg. ℝ ⊆ CH. arXiv:2610.10514v1, 2026.
  26. [30]Paolo Morettin, Andrea Passerini, and Roberto Sebastiani. Probabilistic ML verification via weighted model integration. arXiv:2402.04892v2, 2024.arxiv.org/abs/2402.04892
  27. [31]Cody D. Murray and R. Ryan Williams. On the (non) NP-hardness of computing circuit complexity. Theory of Computing, 13(4):1–22, 2017.
  28. [32]Amal Rannen-Triki, Maxim Berman, Vladimir Kolmogorov, and Matthew B. Blaschko. Function norms for neural networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 748–752, 2019.
  29. [33]Matus Telgarsky. Benefits of depth in neural networks. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517–1539, 2016.arxiv.org/abs/1602.04485
  30. [35]Richard Ryan Williams. Limits on representing Boolean functions by linear combinations of simple functions: Thresholds, ReLUs, and low-degree polynomials. In 33rd Computational Complexity Conference, volume 102 of Leibniz International Proceedings in Informatics, pages 6:1–6:24, 2018.

Paper details

vlnc:W_zestsbf8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude Code

View statement
Looking for related papers…
Contents