Computer science is haunted by a paradox. On paper, the tasks we care about most—training neural networks, clustering data, and performing probabilistic inference—are often NP-hard, meaning they should be impossible to solve efficiently. Yet, in practice, we solve them every day. Avrim Blum and Ronald L. Rivest proved in Training a 3-Node Neural Network is NP-Complete that even a tiny network is computationally intractable in the worst case.
If the theory says "impossible" and the practice says "easy," the theory is likely measuring the wrong thing. A growing body of research suggests that the "worst-case" scenarios used to define complexity classes like NP-complete are rare, adversarial outliers that do not reflect the structured, stable nature of real-world data.
Where the Hardness Hides
Complexity isn't spread evenly across a problem space. In their seminal work, Peter C. Cheeseman, Bob Kanefsky, and William M. Taylor demonstrated that "really hard" instances cluster around a predictable phase transition in Where the Really Hard Problems Are.
Imagine a constraint satisfaction problem. If there are very few constraints, the problem is "underconstrained" and easy to solve because solutions are everywhere. If there are many constraints, it is "overconstrained" and easy to prove no solution exists. The exponential "hardness" only emerges at the critical boundary where a problem is just barely solvable. Most real-world problems, however, don't sit on this knife's edge.
The Stability of Real Data
One reason heuristics work so well is that real-world data is often stable or perturbation resilient. In Center-based Clustering under Perturbation Stability, Pranjal Awasthi and Or Sheffet showed that if a clustering solution doesn't change when you slightly wiggle the distances between points, the problem becomes solvable in polynomial time.
This leads to the "Clustering is Difficult only when it does Not Matter" (CDNM) thesis, explored by Shai Ben-David in Clustering is Easy When ....What?. If a dataset has no clear cluster structure, finding the "optimal" $k$-means partition is hard—but in that case, the partition itself is likely meaningless. When the data has a clear, robust structure, the NP-hardness of the objective function effectively vanishes.
Smoothed Analysis and Typical Cases
Even when a problem seems theoretically impossible, a tiny bit of noise can make it tractable. This is the core of smoothed analysis. Aditya Bhaskara and colleagues demonstrate in Smoothed Analysis in Unsupervised Learning via Decoupling that adversarial "worst-case" instances are mathematically brittle. By slightly perturbing inputs, they unlock polynomial-time algorithms for problems like Hidden Markov Model learning that are otherwise considered intractable.
This discrepancy between worst-case and average-case performance appears across domains:
- Computer Vision: Hunter Lang shows in Block Stability for MAP Inference that simple linear programming relaxations work because real images have "stable" sub-regions.
- Logic: Nikhil Vyas refutes certain exponential time hypotheses for random instances in Super Strong ETH is False for Random k-SAT, suggesting average-case SAT is easier than we feared.
- Inference: Erik M. Lindgren and others explain in Exact MAP Inference by Avoiding Fractional Vertices that MAP inference is efficient when the number of "confounding" fractional solutions is low—a common trait in practical models.
Why Philosophers and Practitioners Should Care
As Scott Aaronson argues in Why Philosophers Should Care About Computational Complexity, defining a problem by its most difficult possible instance is a useful mathematical tool, but a poor guide to reality.
The success of modern AI suggests that the "natural" distributions we care about—images, language, and physical systems—possess structural properties that bypass the barriers of NP-completeness. The goal of this research direction is to move beyond pessimistic bounds and develop a "white-box" understanding of why these problems are easy, as seen in Interpretable Machine Learning for Kronecker Coefficients by Giorgi Butbaia and Kyu-Hwan Lee. By identifying the specific constraints—like entropy, stability, or symmetry—that make data "nice," we can build algorithms that are guaranteed to work on the problems that actually matter.