By January 2020, Papadimitriou had been desirous about the pigeonhole precept for 30 years. So he was stunned 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 go away some empty holes. Once more, it appears apparent. However does inverting the pigeonhole precept have any fascinating mathematical penalties?
It could sound as if this “empty-pigeonhole” precept is simply the unique one by one other title. Nevertheless it’s not, and its subtly completely 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 potential four-digit PINs. The empty-pigeonhole precept dictates that some potential PINs aren’t represented in any respect. If you wish to discover considered one of these lacking PINs, although, there doesn’t appear to be any higher manner than merely asking every particular person their PIN. To date, the empty-pigeonhole precept is rather like its extra well-known counterpart.
The distinction lies within the issue 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, akin to the unique pigeonhole situation, there’s a easy technique to confirm that declare: Simply test with the 2 folks in query. However within the live performance corridor case, think about that somebody asserts that no particular person has a PIN of 5926. Right here, it’s unimaginable 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 desirous about the empty-pigeonhole precept, he introduced it up in a dialog with a potential graduate scholar. 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 principle. Ultimately he and his colleagues printed a paper about search issues which might be assured to have options due to the empty-pigeonhole precept. They had been particularly all for issues the place pigeonholes are considerable—that’s, the place they far outnumber pigeons. Consistent with a practice of unwieldy acronyms in complexity principle, 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 pc scientist Claude Shannon. Shannon proved that the majority computational issues should be inherently laborious to unravel, utilizing an argument that relied on the empty-pigeonhole precept (although he didn’t name it that). But for many years, pc scientists have tried and didn’t show that particular issues are really laborious. Like lacking bank-card PINs, laborious issues should be on the market, even when we will’t establish them.
Traditionally, researchers haven’t thought in regards to the technique of in search of laborious issues as a search downside that might itself be analyzed mathematically. Papadimitriou’s strategy, which grouped that course of with different search issues related to the empty-pigeonhole precept, had a self-referential taste attribute of a lot current work in complexity principle—it provided a brand new technique to cause in regards to the issue of proving computational issue.
