A 35-year-old math puzzle has finally been solved, proving that certain types of scheduling are mathematically impossible to do perfectly.
April 16, 2026
Original Paper
NP-Hardness and a PTAS for the Pinwheel Problem
arXiv · 2604.13974
The Takeaway
The 'pinwheel problem' has been open since 1989, and this paper finally proves it is NP-hard. This isn't just an academic win; it proves that a whole class of real-world problems in scheduling, resource allocation, and signal processing cannot be solved optimally in reasonable time. It provides the definitive mathematical 'no' to engineers who have been trying to optimize these systems for decades. Now, the focus must shift to approximation algorithms rather than perfect solutions. It closes a long chapter in complexity theory and resets the expectations for high-end logistics optimization.
From the abstract
In the pinwheel problem, one is given an $m$-tuple of positive integers $(a_1, \ldots, a_m)$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_m$ such that every interval of length $a_i$ has non-empty intersection with $C_i$, for $i = 1, 2, \ldots, m$. It was a long-standing open question whether the pinwheel problem is NP-hard. We affirm a prediction of Holte et al. (1989) by demonstrating, for the first time, NP-hardness of the pinwheel problem. This enable