Deep learning has proven remarkably adept at discovering compressed, generalized representations of complex functions. Naturally, this success has inspired researchers to apply neural networks to combinatorial optimization and NP-hard search problems. A common strategy is to train a neural network to act as an "informed heuristic" (for example, predicting the distance to a goal state to guide algorithms like A* search). If a neural network can accurately predict these distances in a single forward pass, it could theoretically bypass the exponential time complexity of traditional search algorithms.
However, a fundamental theoretical wall prevents this approach from scaling. By bridging computational complexity theory with deep learning, recent literature demonstrates that neural networks cannot escape the inherent hardness of these problems: to maintain accuracy as problem sizes grow, the size of the network itself must scale super-polynomially or exponentially.
The Core Conflict: Polynomial Inference vs. NP-Hardness
To understand why neural heuristics face a scalability wall, we must look at the computational nature of a neural network's forward pass.
When a neural network processes an input, it executes a sequence of matrix multiplications and non-linear activations. If the network's architecture is bounded to a polynomial number of parameters relative to the input size, then computing the forward pass is fundamentally a polynomial-time operation.
This creates an immediate contradiction when dealing with NP-hard problems. If a polynomial-sized neural network could perfectly compute or approximate the optimal heuristic distance to a goal, we could use that network to solve NP-hard problems in polynomial time. As Pendurkar et al. point out, complexity theory dictates that a network with a polynomial number of parameters cannot perfectly represent the optimal heuristic for NP-hard problems unless $P = NP$.
The Complexity Theoretical Foundation
This tension between neural network capacity and problem hardness is a long-standing theoretical reality. Early work by Bruck et al. established that if a polynomial-sized neural network could consistently find the global optimum for NP-hard optimization problems, it would imply that $NP = co-NP$—a collapse of standard complexity hierarchies that computer scientists widely believe to be impossible.
Furthermore, Bruck et al. demonstrated that this barrier is not solved by simply settling for an approximation. For certain combinatorial problems, ensuring that a polynomial-sized network finds a solution within a fixed percentage of the optimum is just as difficult as finding the exact solution, meaning that reliable approximation guarantees face the exact same complexity walls.
The Scaling Wall: Super-Polynomial Growth
When modern architectures attempt to learn these complex heuristic functions, what happens in practice? If the network cannot perfectly represent the function using a polynomial number of parameters, it must scale.
To formalize this, Pendurkar et al. connected neural network architectures to circuit complexity. Because NP-hard problems cannot be solved by polynomial-sized circuits, the authors proved that any neural network attempting to accurately estimate a perfect heuristic must grow at a super-polynomial rate relative to the problem size. If a compact, polynomial-sized model could maintain high precision, it would cause a collapse of the polynomial-time hierarchy.
Consequently, as problem instances scale, the model complexity required to solve the problem eventually mirrors the complexity of the problem itself.
The Lookup Table Phenomenon
When a neural network is forced to learn a function that exceeds its capacity for meaningful compression, it stops generalizing. Instead, it begins to function as an over-parameterized lookup table (Pendurkar et al.). To maintain high precision across an expanding search space, the network is forced to dedicate its parameter capacity to memorizing the exponentially growing state space.
Crucially, this is not a flaw that can be engineered away with better tuning or different architectures. As Pendurkar et al. demonstrated, this exponential growth in required parameters remains consistent regardless of whether model capacity is increased through width or depth. Similarly, altering the loss function or training objectives fails to mitigate this fundamental scaling limitation.
Ultimately, while deep learning remains a powerful tool for finding clever heuristics for small or average-sized problem instances, it cannot cheat the laws of computational complexity. For NP-hard search problems, scaling the model to maintain accuracy eventually negates the very computational efficiency the heuristic was designed to provide.
Key Foundational Work
The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems (2022) — contributed 5 concept elements to this direction.
On the Power of Neural Networks for Solving Hard Problems (1987) — contributed 4 concept elements to this direction.
A Discussion on the Scalability of Heuristic Approximators (Extended Abstract) (2022) — contributed 3 concept elements to this direction.