A weather forecaster who says “30% chance of rain” should be wrong 70% of the time on those predictions. Calibration measures this: how closely predicted probabilities match observed frequencies. Calibration distance, introduced by Błasiok et al. (STOC 2023), quantifies the gap between prediction and reality as a single number — the earth mover's distance between the predicted distribution and the calibrated ideal.
Dagan and Kur (arXiv:2603.18391) prove that computing this distance is NP-hard. But the hardness appears only under specific conditions. When the marginal distribution of predictions is uniform and labels are noiseless, an efficient exact algorithm exists. Remove either assumption — allow non-uniform prediction distributions or noisy labels — and the problem becomes intractable.
The transition is abrupt. Uniform marginals with noise: NP-hard. Non-uniform marginals without noise: NP-hard. Uniform without noise: polynomial. The cliff between tractable and intractable sits at the intersection of two mild assumptions, neither of which is individually sufficient for hardness.
For estimation rather than computation, the picture is equally precise: Θ(1/ε³) samples are necessary and sufficient to estimate calibration distance to accuracy ε, regardless of the domain size. This cubic dependence is tight — you cannot do better with fewer samples, and you don't need more.
The practical consequence: evaluating whether a predictor is well-calibrated is fundamentally harder than making the predictions. A machine learning model can output probabilities in milliseconds, but certifying that those probabilities mean what they claim requires either restrictive assumptions or computational resources that scale with the problem's complexity. The scorecard is harder to read than the exam is to take.