By January 2020, Papadimitriou had considered the Pigonhole principle for 30 years. So, when the playful conversation with the frequent collaborators made them a simple twist on the principle they had never considered: What if there were fewer pigeons than the holes? In this case, any arrangement of pigeons must leave some holes. Again, this seems obvious. But are there any interesting mathematical consequences of the inversion principle?
It sounds like this “empty foot-pedal hole” principle is just another principle of name. But this is not, its clever features make it a new tool for classifying computational problems.
To understand the empty foot hole principle, let’s go back to the bank card example, transferring from the football field to a 3,000-seat concert hall, which is less than possible four-digit pins. The empty long hole principle shows that there are no possible pins at all. However, if you want to find one of the missing pins, then there seems to be nothing better than simply asking everyone’s pins. So far, the principle of empty transhole is like its more famous counterpart.
The difference is that it is difficult to check the solution. Imagine that someone said they had found two people with the same pins in the football field. In this case, corresponding to the original pigeon hole scene, there is an easy way to verify the claim: just check with two people. But in the case of the concert hall, imagine someone asserting that no one has a pin of 5926. Here, it is impossible to verify without asking everyone in the audience about the pins. This makes the principle of hollow hole even more annoyed for complexity theorists.
Papadimitriou began to think about the empty foot-step principle two months later, he proposed this principle in a conversation with potential graduate students. He remembered it vividly because it turned out to be the last conversation he had with anyone before the Covid-19 lockdown. Over the next few months, he mastered the impact of this issue on the theory of complexity at home. Eventually, he and his colleagues published a paper about search questions that guaranteed a solution due to the principle of empty holes. They are particularly interested in the problem of a rich pore of pigeons, that is, they far outweigh pigeons. To fit the tradition of clumsy acronyms in complexity theory, they call this type of problem APEPP with a “rich polynomial empty hole principle.”
One of the problems with this lesson was inspired by the proof of the famous 70-year history of groundbreaking computer scientist Claude Shannon. Shannon demonstrated that most computational problems must be solved inherently, and the argument relies on the principle of empty holes (although he did not call it). However, for decades, computer scientists have tried and failed to prove that a particular problem is indeed difficult. Just like pins with missing bank cards, even if we can’t recognize them, there must be hard problems.
Historically, researchers have never considered the process of finding hard problems as a search problem, which itself can be analyzed mathematically. Papadimitriou’s method grouped this process with other search questions related to the principle of empty cone, which has the flavor of self-fingering of many of the latest works in the theory of complexity, and it provides a new way of reasoning for the difficulty of calculating difficulties.
