---
title: "The Complexity of ReLU Network Synthesis from a Parameter Multiset"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.04074v1"
permalink: "https://feed.astralor.com/items/itm_8af2c1d357b76fed4e3c6cbc"
published: "2026-11-02T23:37:14.000Z"
score: 61
channel: "ai"
tags: ["RAG","The Complexity","ReLU Network Synthesis","Parameter Multiset","ReLU","Matching","Agreeing"]
---

# The Complexity of ReLU Network Synthesis from a Parameter Multiset

## 速览

We ask how hard it is to build a neural network when its parameter values are given in advance. An instance supplies a multiset of rational numbers, a target behavior, and a bound on the number of neurons, output includ…

## 关键点

- We ask how hard it is to build a neural network when its parameter values are given in advance.
- An instance supplies a multiset of rational numbers, a target behavior, 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.

## 全文

We ask how hard it is to build a neural network when its parameter values are given in advance. An instance supplies a multiset of rational numbers, a target behavior, 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; permutation training instead fixes the hidden units and only rearranges the output weights. Matching two labeled examples exactly is already $\mathsf{NP}$-complete; 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 $Σ_2^{\mathsf P}$-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in $\mathsf{DP}$ for every fixed neuron bound and is $\mathsf{DP}$-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is $Σ_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 $\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. Since the graph is chosen too, the reductions must rule out every other network built from the same numbers.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_8af2c1d357b76fed4e3c6cbc