Average-Case Complexity

Average-case complexity is the study of computational problems not by their worst-case behavior but by their typical behavior under natural input distributions. Where worst-case complexity asks how hard a problem is for the most adversarial instance, average-case complexity asks how hard it is for instances drawn from distributions that arise in practice. The distinction matters profoundly: a problem can be NP-hard in the worst case yet solvable in polynomial time on almost all instances, or — more troublingly — easy in the worst case yet hard on the instances we actually encounter.

The framework was formalized by Leonid Levin in 1986 with the definition of distNP, the distributional analogue of NP. A problem is average-case hard if every efficient algorithm fails on a non-negligible fraction of instances drawn from a samplable distribution. This definition connects cryptography to complexity: one-way functions exist if and only if certain problems are hard on average. The field provides the rigorous foundation for understanding why some machine learning problems resist efficient algorithms even when more data is available — a phenomenon known as the statistical-computational gap.