In the daily practice of deep learning, we treat training as a continuous optimization problem solved by gradient descent. However, a parallel lineage of research treats training as a discrete "loading problem": given a fixed architecture and a dataset, does there exist a set of weights that perfectly maps the inputs to the outputs?
Theoretical work over the last three decades has revealed that this loading problem is not just difficult, but fundamentally intractable across multiple complexity classes. Understanding why training is hard requires looking past the smooth loss curves of backpropagation and into the combinatorial and algebraic geometry of the weight space.
The Loading Problem and the NP-Hardness Floor
The foundational framing of this area is the "loading problem," a term popularized by the work of J. Stephen Judd. It asks whether a specific network can "load" a specific set of data. In 1988, Avrim Blum and Ronald L. Rivest proved in Training a 3-Node Neural Network is NP-Complete that even a minimal network with just two hidden nodes and one output node is NP-complete to train.
The intuition behind this hardness is the "hidden unit credit assignment problem" identified by Eric B. Baum and Kevin J. Lang in Constructing Hidden Units Using Examples and Queries. To solve a task like parity or the "two-spirals" problem, the learner must decide exactly what each internal neuron should represent. Because the neurons are interdependent, choosing the "wrong" role for one neuron can make the entire problem unsolvable for the others. This creates a combinatorial explosion of possible configurations that a learner must navigate.
The Geometry of Data Partitioning
One might assume that the difficulty of training stems from high-dimensional data or deep architectures. However, Vincent Froese and Christoph Hertrich showed in Training Neural Networks is NP-Hard in Fixed Dimension that training a two-layer ReLU network remains NP-hard even when the input data is restricted to just two dimensions.
The hardness arises from the geometric boundaries created by activation functions. Each ReLU neuron acts as a hyperplane that partitions the input space. Training is essentially the task of finding a global arrangement of these hyperplanes that correctly categorizes the data points. As Mert Pilanci and Yifei Wang 0005 explain in Polynomial-Time Solutions for ReLU Network Training, this is equivalent to a combinatorial search over "activation patterns"—the set of which neurons are "on" or "off" for each data point. This links neural network optimization to classical hard problems in graph theory like Max-Cut.
Beyond NP: The Existential Theory of the Reals
While NP-hardness is the standard benchmark for "hard," recent work suggests that training neural networks belongs to an even more difficult class: the Existential Theory of the Reals ($\exists\mathbb{R}$).
In Training Fully Connected Neural Networks is ∃R-Complete, Christoph Hertrich and colleagues, along with Mikkel Abrahamsen in Training Neural Networks is ER-complete, proved that finding optimal weights is equivalent to solving systems of polynomial equations over real numbers.
The distinction is subtle but vital: NP-complete problems can be verified in polynomial time using a discrete "certificate" (like a string of bits). $\exists\mathbb{R}$-complete problems often require weights that are irrational numbers, meaning they cannot be easily represented or verified by a standard computer. This places the optimization of even simple architectures beyond the reach of traditional combinatorial solvers and explains why we must rely on continuous approximations like gradient descent.
When Training Becomes Undecidable
The complexity of training is also a function of the activation function's mathematical properties. Teemu Hankala, Miika Hannula, and others demonstrated in Complexity of Neural Network Training and ETR that while ReLU networks are $\exists\mathbb{R}$-complete, using periodic functions like sines makes the training problem formally undecidable.
Because sinusoidal functions can encode Diophantine equations (polynomial equations where only integer solutions are sought), there is no general algorithm that can determine if a valid set of weights exists for such a network. A similar result was found for Recurrent Neural Networks (RNNs) by Herbert Wiklicky in On the Non-Existence of a Universal Learning Algorithm for Recurrent Neural Networks. The dynamic feedback loops in RNNs allow them to simulate Turing machines, meaning that determining if an RNN can solve a specific task is equivalent to the Halting Problem.
Why Empirical Success Persists
If training is so theoretically difficult, why does it work in practice? The research suggests several "escape hatches":
- Fixed Size: Wolfgang Maass 0001 showed in Agnostic PAC-Learning of Functions on Analog Neural Nets that if the number of weights is fixed, polynomial-time algorithms can exist. Hardness often emerges only as we scale the architecture.
- Tensor Methods: Majid Janzamin and Animashree Anandkumar have shown in Beating the Perils of Non-Convexity that global convergence can be guaranteed if we move away from gradient descent toward tensor decomposition methods.
- Overparameterization: As noted by Mert Pilanci, having more neurons than data points simplifies the combinatorial search over activation patterns, effectively smoothing the optimization landscape.