Average-case complexity

Average-case complexity is the study of how difficult computational problems are on typical inputs, as opposed to the worst-case inputs that dominate classical complexity theory. A problem may be NP-complete — hard in the worst case — yet efficiently solvable on almost all inputs that arise in practice. The average-case perspective is essential for cryptography, where a scheme must be hard to break not on contrived inputs but on randomly generated keys, and for machine learning, where the relevant question is whether a model generalizes to the distribution of real-world data.

The central open problem in average-case complexity is the relationship between worst-case and average-case hardness. The Direct Product Theorem and hardness amplification provide partial answers: if a problem is slightly hard on average, it can be transformed into one that is extremely hard on average. But whether worst-case hardness implies average-case hardness — the so-called worst-case to average-case reduction — remains open for many complexity classes, and its resolution would transform both cryptography and complexity theory.