Cuando hay más palomas que palomares, algunas aves deben agruparse. Esta afirmación obvia, y su inversa, tiene profundas conexiones con muchas áreas de las matemáticas y la informática.

Un artículo de Ben Brubaker. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

Dicen que más vale pájaro en mano que ciento volando, pero para los informáticos, dos pájaros en un agujero es mucho mejor. Esto se debe a que esas aves que cohabitan son las protagonistas de un teorema matemático engañosamente simple llamado el principio del palomar. Es fácil de resumir en una frase corta: si diez palomas se acurrucan en nueve palomares, al menos dos de ellas deben compartir un agujero. Ahí está, eso es todo.

«El principio del palomar es un teorema que provoca una sonrisa», comenta Christos Papadimitriou, informático teórico de la Universidad de Columbia. «Es un tema de conversación fantástico».

Pero el principio del palomar no es solo cosa de pájaros. Aunque suene dolorosamente simple, se ha convertido en una potente herramienta para los investigadores dedicados al proyecto central de la informática teórica: mapear las conexiones ocultas entre diferentes problemas.

El principio del palomar se aplica a cualquier situación en la que objetos se asignan a categorías y el número de objetos supera al de categorías. Por ejemplo, implica que, en un estadio de fútbol abarrotado con 30.000 asientos, algunos asistentes deben tener la misma contraseña de cuatro dígitos, o PIN, para sus tarjetas bancarias. En este caso, las palomas son los aficionados al fútbol y los agujeros son los 10.000 PIN posibles, del 0000 al 9999. Esto representa que hay menos posibilidades que el número total de personas, por lo que algunas deben tener los mismos dígitos.

Esta demostración destaca no solo por su simplicidad, sino también por lo que omite. Muchos métodos matemáticos para demostrar la existencia de algo son «constructivos», lo que significa que también muestran cómo encontrarlo. Las demostraciones «no constructivas», como las basadas en el principio del palomar, carecen de esta propiedad. En el ejemplo del estadio de fútbol, ​​saber que algunas personas deben tener el mismo PIN no indica cuáles son. Siempre se puede recorrer la grada preguntando a cada persona por turno. Pero, ¿existe una manera más sencilla?

Preguntas como esta, sobre la manera más eficiente de resolver problemas, son fundamentales en la rama de la informática conocida como teoría de la complejidad computacional. Los teóricos de la complejidad estudian estas cuestiones agrupando los problemas en clases según ciertas propiedades compartidas. A veces, el primer paso hacia un avance es simplemente definir una nueva clase para agrupar problemas que los investigadores no habían estudiado previamente.

Eso fue lo que ocurrió en la década de 1990, cuando Papadimitriou y otros teóricos de la complejidad comenzaron a estudiar nuevas clases de problemas, en los que el objetivo es encontrar algo que debe existir debido al principio del palomar u otra demostración no constructiva. Esta línea de trabajo ha propiciado importantes avances en diversos campos de la informática, desde la criptografía hasta la teoría de juegos algorítmica.

Para enero de 2020, Papadimitriou llevaba 30 años reflexionando sobre el principio del palomar. Así que se sorprendió cuando, bromeando con un colaborador frecuente, les llevó a una enfoque simple del principio que nunca habían considerado: ¿Y si hay menos palomas que agujeros? En ese caso, cualquier disposición de las palomas debe dejar algunos agujeros vacíos. De nuevo, parece obvio. Pero ¿invertir el principio del palomar tiene alguna consecuencia matemática interesante?

Puede parecer que este principio del «palomar vacío» es simplemente el original con otro nombre. Pero no es así, y su carácter sutilmente diferente lo ha convertido en una herramienta nueva y fructífera para clasificar problemas computacionales.

Para comprender el principio del palomar vacío, volvamos al ejemplo de la tarjeta bancaria, transpuesto de un estadio de fútbol a una sala de conciertos con 3000 asientos, un número menor que el total de PIN posibles de cuatro dígitos. El principio del palomar vacío dicta que algunos PIN posibles no están representados en absoluto. Sin embargo, si se desea encontrar uno de estos PIN que faltan, no parece haber mejor manera que simplemente preguntarle a cada persona su PIN. Hasta ahora, el principio del casillero vacío es igual que su contraparte más famosa.

La diferencia radica en la dificultad de comprobar las soluciones. Imaginemos que alguien dice haber encontrado dos personas específicas en el estadio de fútbol con el mismo PIN. En este caso, correspondiente al planteamiento del palomar original, existe una forma sencilla de verificar dicha afirmación: simplemente comprobar con las dos personas en cuestión. Pero en el caso de la sala de conciertos, imaginemos que alguien afirma que ninguna persona tiene el PIN 5926. En este caso, es imposible verificarlo sin preguntar a todos los presentes cuál es su PIN. Esto hace que el principio del palomar vacío sea mucho más complejo para los teóricos de la complejidad.

Dos meses después de que Papadimitriou comenzara a reflexionar sobre el principio del palomar vacío, lo mencionó en una conversación con un futuro estudiante de posgrado. Lo recuerda vívidamente, porque resultó ser su última conversación en persona con alguien antes de los confinamientos por la COVID-19. Encerrado en casa durante los meses siguientes, se enfrentó a 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 con soluciones garantizadas gracias al principio del palomar vacío. Estaban especialmente interesados ​​en problemas donde abundan los palomares, es decir, donde superan con creces a las palomas. Siguiendo la tradición de acrónimos complicados en la teoría de la complejidad, denominaron a esta clase de problemas APEPP, por sus siglas en inglés, «principio del palomar vacío polinomial abundante».

Uno de los problemas de esta clase se inspiró en una famosa demostración de hace 70 años del pionero de la informática Claude Shannon. Shannon demostró que la mayoría de los problemas computacionales deben ser inherentemente difíciles de resolver, utilizando un argumento basado en el principio del palomar vacío (aunque no lo llamó así). Sin embargo, durante décadas, los informáticos han intentado, sin éxito, demostrar que ciertos problemas específicos son realmente difíciles. Al igual que los PIN de tarjetas bancarias que faltan, los problemas difíciles deben existir, incluso si no podemos identificarlos.

Históricamente, los investigadores no han considerado el proceso de búsqueda de problemas complejos como un problema de búsqueda que pudiera analizarse matemáticamente. El enfoque de Papadimitriou, que agrupó este proceso con otros problemas de búsqueda relacionados con el principio del palomar vacío, tenía un matiz autorreferencial característico de gran parte del trabajo reciente en teoría de la complejidad: ofrecía una nueva forma de razonar sobre la dificultad de demostrar la complejidad computacional.

“Estás analizando la tarea de la teoría de la complejidad utilizando la teoría de la complejidad”, explica Oliver Korten, investigador de Columbia.

Korten es el futuro estudiante con quien Papadimitriou había discutido el principio del palomar vacío justo antes de la pandemia. Llegó a Columbia para trabajar con Papadimitriou y, durante su primer año de posgrado, demostró que la búsqueda de problemas computacionales complejos estaba íntimamente ligada a todos los demás problemas de APEPP. En un sentido matemático específico, cualquier progreso en este problema se traducirá automáticamente en progreso en muchos otros que los informáticos y matemáticos han estudiado durante mucho tiempo, como la búsqueda de redes que carecen de una subestructura simple.

El artículo de Korten atrajo inmediatamente la atención de otros investigadores. «Me sorprendió bastante cuando lo vi», cuenta Rahul Santhanam, teórico de la complejidad de la Universidad de Oxford. «Es increíblemente emocionante». Desde entonces, él y otros investigadores han aprovechado el avance de Korten para demostrar una serie de nuevos resultados sobre las conexiones entre la dificultad computacional y la aleatoriedad.

«Esto tiene una riqueza asombrosa», dijo Papadimitriou. «Aborda la esencia de importantes problemas de complejidad».

El artículo original, How a Problem About Pigeons Powers Complexity Theory, se publicó el 4 de abril de 2025 en Quanta Magazine.

Traducido por César Tomé López