Theoretical Limits of Neural Networks for Combinatorial Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 25 papers16 conceptsfrozen 2026-10-04

Neural networks are often used as powerful heuristics for solving NP-hard combinatorial problems like the Knapsack Problem or the Traveling Salesperson Problem. However, a fundamental tension exists between the fixed, polynomial-time nature of a neural network's forward pass and the inherent complexity of the problems they aim to solve. Recent research has begun to map the rigorous boundaries of this relationship, revealing that the "magic" of deep learning is strictly governed by the laws of computational complexity.

The Complexity Ceiling

The most direct way to understand why neural networks cannot easily "solve" NP-hard problems is to look at their architecture. A standard neural network with a fixed number of layers and parameters performs a sequence of operations that finishes in polynomial time.

In On the Power of Neural Networks for Solving Hard Problems, Jehoshua Bruck and Joseph W. Goodman provided a theoretical "reality check" for this approach. They proved that if a polynomial-sized neural network could consistently find the global optimum for NP-hard problems, it would imply that $NP = co-NP$. Since computer scientists widely believe this equality is false, the implication is clear: a neural network of manageable size is fundamentally susceptible to getting trapped in local maxima when faced with the landscape of a hard combinatorial problem.

The Parameter Scaling Wall

If a small network cannot solve these problems, can we simply build larger ones? This is the core question of "scalability" in neural combinatorial optimization.

Research by Sumedh Pendurkar, Taoan Huang, Sven Koenig, and Guni Sharon in The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems suggests that "scaling up" is an unsustainable strategy. They demonstrate that for NP-hard search problems, the number of parameters required to maintain a high level of precision in a heuristic function grows exponentially with the problem size.

This creates a "scaling wall." While a neural network might learn to solve small instances of a problem efficiently, the model capacity required to maintain that same accuracy on larger instances explodes. This suggests that the success of deep learning in this field is often limited to specific problem distributions or sizes, rather than representing a general-purpose solver.

The Precision Width Tradeoff

Despite these hard limits, neural networks can still be "provably good" if we shift our goal from exact solutions to guaranteed approximations.

In Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size, Christoph Hertrich and Martin Skutella bridge the gap between empirical success and theoretical guarantees. They focus on the Knapsack Problem and show that Recurrent Neural Networks (RNNs) can indeed solve it, but with a strict tradeoff:

  1. Exact Solutions: To find the exact optimum, the network width must be "pseudo-polynomial" (scaling with the values of the items).
  2. Approximation Guarantees: To achieve a specific approximation ratio (an FPTAS), the network width must scale as a polynomial function of both the problem size and the desired precision ($1/\epsilon$).

This work provides a constructive proof that neural architectures can mirror the behavior of classical approximation algorithms. It reframes the neural network not as a black box that "guesses" the answer, but as a structured computation whose width is a direct resource cost paid for precision.

Summary of the Intuition

The research direction across these papers suggests that neural networks are not exempt from the rules of P vs NP.

  • If the network is small (polynomial size), it cannot be guaranteed to find the global optimum of an NP-hard problem without collapsing the complexity hierarchy.
  • If we demand high precision on large problems, the network size must grow at an unsustainable, exponential rate.
  • If we accept a bounded error, we can design networks where the size (width) is mathematically linked to the quality of the approximation.

Ultimately, the power of neural networks in this domain is not in bypassing complexity, but in providing a differentiable, learnable framework for implementing known algorithmic strategies like dynamic programming or heuristic search.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 4 papers
  2. Version 1 · 2026-10-04 · 5 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_super_polynomial_model_scaling_ab011e8c,
  title = {super-polynomial model scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/super-polynomial-model-scaling/rdr_ab011e8c002b47fe8ab08487d845a3f1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_theoretical_limits_of_neural_networks_fo_ab011e8c_v1,
  title = {Theoretical Limits of Neural Networks for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/theoretical-limits-of-neural-networks-for-combinatorial-optimization/rdr_ab011e8c002b47fe8ab08487d845a3f1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}