The Practical Tractability of Theoretically Hard Problems

This direction is merged into another direction: worst-case complexity gap. Its last version stays readable and citable here.

Version 1 of 142 papers42 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_practical_tractability_of_theoretica_807762d8,
  title = {The Practical Tractability of Theoretically Hard Problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-practical-tractability-of-theoretically-hard-problems/rdr_807762d814b0476d9b85ecf9758bbc35},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_practical_tractability_of_theoretica_807762d8_v1,
  title = {The Practical Tractability of Theoretically Hard Problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-practical-tractability-of-theoretically-hard-problems/rdr_807762d814b0476d9b85ecf9758bbc35/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}