networks
Frequencies without interference
It is 1970, and the FCC's problem is a graph wearing a radio disguise: hundreds of transmitters, each pair that overlaps in range forbidden from sharing a frequency, and spectrum too scarce to waste. Model it as graph coloring — vertices as transmitters, edges as conflicts, colors as channels — and find the minimum number of channels. Then face what the theory says: coloring is among the problems for which no efficient exact algorithm is likely to exist, so the real craft is knowing when the instance's structure lets you color optimally and when to certify a good-enough answer with a provable bound. Get it wrong and either broadcasts interfere in a dozen cities, or the agency licenses half the spectrum it actually had.
Who this problem belongs to
The two figures whose methods fit it best, out of 43 in contention.
Karp's landmark 1972 paper '21 NP-complete problems' explicitly includes graph coloring among the foundational problems shown to be NP-complete, formalizing precisely this scenario's mathematical core: transmitters as vertices, interference as edges, channels as colors, and minimum-channel-count as the chromatic number. His broader career establishing which combinatorial problems admit efficient exact algorithms versus which require approximation gives him unmatched authority on this problem's central craft, knowing when an instance's structure permits optimal coloring and when to certify a good-enough bound instead. His Berkeley theory group also worked extensively on approximation algorithms for exactly this class of resource-allocation problems. No other career on this card maps this specifically onto the problem's precise mathematical formalization and its NP-hardness framing, which is why his score sits at the maximum.
Cook's 1971 theorem establishing NP-completeness, with graph coloring among the problems subsequently shown NP-complete by Karp using Cook's reduction framework, is the direct theoretical foundation for this problem's central claim: that no efficient exact algorithm is likely to exist for minimum channel assignment in general, so the FCC's engineers must instead exploit structure or accept certified approximation. His framework for classifying computational difficulty gives rigorous backing for exactly the tradeoff this problem names between exact optimality and provable good-enough bounds. He did not personally prove graph coloring's NP-completeness, that specific reduction came from Karp building on his machinery, which is the only reason his score sits fractionally below Karp's for this precise problem despite being its deeper theoretical origin.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
43 figures are scored on this problem. Draw it in a battle to see where you land.