Para enero de 2020, Papadimitriou había estado pensando en el principio de paloma durante 30 años. Así que se sorprendió cuando una conversación lúdica con un colaborador frecuente los llevó a un simple toque del principio que nunca habían considerado: ¿y si hay menos palomas que agujeros? En ese caso, cualquier disposición de palomas debe dejar algunos agujeros vacíos. De nuevo, parece obvio. ¿Pero el principio invertir el principio de paloma tiene alguna consecuencia matemática interesante?
Puede sonar como si este principio de “Pigeonhole vacío” sea solo el original por otro nombre. Pero no lo es, y su carácter sutilmente diferente lo ha convertido en una herramienta nueva y fructífera para clasificar los problemas computacionales.
Para comprender el principio vacío-pigeonhole, volvamos al ejemplo de la tarjeta de banco, se transpone de un estadio de fútbol a una sala de conciertos con 3.000 asientos, un número menor que el total de pasadores de cuatro dígitos posibles. El principio vacío-pigeonhole dicta que algunos pines posibles no están representados en absoluto. Sin embargo, si desea encontrar uno de estos alfileres faltantes, no parece haber una mejor manera que simplemente preguntarle a cada persona su PIN. Hasta ahora, el principio vacío de pigeonhole es como su contraparte más famosa.
La diferencia radica en la dificultad de verificar las soluciones. Imagine que alguien dice que ha encontrado dos personas específicas en el estadio de fútbol que tienen el mismo pin. En este caso, correspondiente al escenario original de palomas, hay una manera simple de verificar esa afirmación: simplemente consulte con las dos personas en cuestión. Pero en el caso de la sala de conciertos, imagine que alguien afirma que ninguna persona tiene un PIN de 5926. Aquí, es imposible verificar sin preguntar a todos en la audiencia cuál es su PIN. Eso hace que el principio vacío de pigeonhole sea mucho más irritante para los teóricos de la complejidad.
Dos meses después de que Papadimitriou comenzó a pensar en el principio vacío de pigeonhole, lo mencionó en una conversación con un posible estudiante graduado. Lo recuerda vívidamente, porque resultó ser su última conversación en persona con cualquiera antes de los bloqueos Covid-19. Empogó en casa durante los siguientes meses, luchó con las implicaciones del problema para la teoría de la complejidad. Finalmente, él y sus colegas publicaron un artículo sobre problemas de búsqueda que garantizan que tendrá soluciones debido al principio vacío de pigeonhole. Estaban especialmente interesados en los problemas donde los cilindros son abundantes, es decir, donde superan en número a las palomas. De acuerdo con una tradición de acrónimos difíciles en la teoría de la complejidad, denominaron esta clase de problemas apePP, para “abundante principio de pigeonhole vacío polinomial”.
Uno de los problemas en esta clase se inspiró en una famosa prueba de 70 años por el pionero científico informático Claude Shannon. Shannon demostró que la mayoría de los problemas computacionales deben ser inherentemente difíciles de resolver, utilizando un argumento que se basó en el principio de vacío-pigeonhole (aunque no lo llamó así). Sin embargo, durante décadas, los informáticos han intentado y no han podido demostrar que los problemas específicos son realmente difíciles. Al igual que los pasadores de tarjetas bancarias faltantes, los problemas difíciles deben estar ahí afuera, incluso si no podemos identificarlos.
Históricamente, los investigadores no han pensado en el proceso de buscar problemas difíciles como un problema de búsqueda que podría analizarse matemáticamente. El enfoque de Papadimitriou, que agrupó ese proceso con otros problemas de búsqueda relacionados con el principio vacío de pigeonhole, tenía un sabor autorreferencial característico de mucho trabajo reciente en la teoría de la complejidad; ofreció una nueva forma de razonar sobre la dificultad de probar la dificultad computacional.
