By January 2020, Papadimitriou had been fascinated about the pigeonhole precept for 30 years. So he was shocked when a playful dialog with a frequent collaborator led them to a easy twist on the precept that they’d by no means thought-about: What if there are fewer pigeons than holes? In that case, any association of pigeons should depart some empty holes. Once more, it appears apparent. However does inverting the pigeonhole precept have any attention-grabbing mathematical penalties?
It might sound as if this “empty-pigeonhole” precept is simply the unique one by one other identify. But it surely’s not, and its subtly totally different character has made it a brand new and fruitful device for classifying computational issues.
To know the empty-pigeonhole precept, let’s return to the bank-card instance, transposed from a soccer stadium to a live performance corridor with 3,000 seats—a smaller quantity than the entire attainable four-digit PINs. The empty-pigeonhole precept dictates that some attainable PINs aren’t represented in any respect. If you wish to discover one in every of these lacking PINs, although, there doesn’t appear to be any higher approach than merely asking every individual their PIN. To date, the empty-pigeonhole precept is rather like its extra well-known counterpart.
The distinction lies within the problem of checking options. Think about that somebody says they’ve discovered two particular folks within the soccer stadium who’ve the identical PIN. On this case, similar to the unique pigeonhole situation, there’s a easy approach to confirm that declare: Simply verify with the 2 folks in query. However within the live performance corridor case, think about that somebody asserts that no individual has a PIN of 5926. Right here, it’s unattainable to confirm with out asking everybody within the viewers what their PIN is. That makes the empty-pigeonhole precept way more vexing for complexity theorists.
Two months after Papadimitriou started fascinated about the empty-pigeonhole precept, he introduced it up in a dialog with a potential graduate pupil. He remembers it vividly, as a result of it turned out to be his final in-person dialog with anybody earlier than the Covid-19 lockdowns. Cooped up at house over the next months, he wrestled with the issue’s implications for complexity idea. Ultimately he and his colleagues revealed a paper about search issues which are assured to have options due to the empty-pigeonhole precept. They had been particularly considering issues the place pigeonholes are considerable—that’s, the place they far outnumber pigeons. In line with a practice of unwieldy acronyms in complexity idea, they dubbed this class of issues APEPP, for “considerable polynomial empty-pigeonhole precept.”
One of many issues on this class was impressed by a well-known 70-year-old proof by the pioneering laptop scientist Claude Shannon. Shannon proved that the majority computational issues should be inherently arduous to resolve, utilizing an argument that relied on the empty-pigeonhole precept (although he didn’t name it that). But for many years, laptop scientists have tried and didn’t show that particular issues are actually arduous. Like lacking bank-card PINs, arduous issues should be on the market, even when we are able to’t establish them.
Traditionally, researchers haven’t thought in regards to the strategy of on the lookout for arduous issues as a search downside that might itself be analyzed mathematically. Papadimitriou’s strategy, which grouped that course of with different search issues linked to the empty-pigeonhole precept, had a self-referential taste attribute of a lot current work in complexity idea—it supplied a brand new approach to purpose in regards to the problem of proving computational problem.
