Los dispositivos hipotéticos que pueden responder preguntas con rapidez y precisión se han convertido en una potente herramienta en la teoría de la complejidad computacional.
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.
Haz una pregunta a una Bola 8 Mágica, y te responderá con un sí, un no, o algo exasperantemente impreciso. La consideramos un juguete para niños, pero los teóricos de la computación emplean una herramienta similar. A menudo imaginan que pueden consultar dispositivos hipotéticos llamados oráculos, que pueden responder instantáneamente y de manera correcta a preguntas específicas. Estos experimentos mentales fantásticos han inspirado nuevos algoritmos y ayudado a los investigadores a mapear el paisaje de la computación.
Los investigadores que invocan oráculos trabajan en un subcampo de la informática llamado teoría de la complejidad computacional. Se ocupan de la dificultad inherente de problemas como determinar si un número es primo o encontrar el camino más corto entre dos puntos en una red. Algunos problemas son fáciles de resolver, otros parecen mucho más difíciles pero tienen soluciones que son fáciles de verificar, mientras que otros son fáciles para los ordenadores cuánticos pero aparentemente difíciles para los ordenadores ordinarios.
Los teóricos de la complejidad buscan entender si estas diferencias aparentes en dificultad son fundamentales. ¿Hay algo intrínsecamente difícil en ciertos problemas, o simplemente no somos lo suficientemente ingeniosos para encontrar una buena solución? Los investigadores abordan estas preguntas clasificando los problemas en «clases de complejidad» —todos los problemas fáciles van en una clase, por ejemplo, y todos los problemas fáciles de verificar van en otra— y demostrando teoremas sobre las relaciones entre estas clases.
Lamentablemente, mapear el paisaje de la dificultad computacional ha resultado ser, bueno, difícil. Así que, a mediados de la década de 1970, algunos investigadores comenzaron a estudiar qué pasaría si las reglas de la computación fueran diferentes. Ahí es donde entran los oráculos.
Al igual que las Bolas 8 Mágicas, los oráculos son dispositivos que responden inmediatamente preguntas de sí o no sin revelar nada sobre su funcionamiento interno. A diferencia de las Bolas 8 Mágicas, siempre responden sí o no, y siempre tienen razón: una ventaja de ser ficticios. Además, cualquier oráculo dado solo responderá un tipo específico de pregunta, como «¿Es este número primo?».
¿Qué hace que estos dispositivos ficticios sean útiles para entender el mundo real? En resumen, pueden revelar conexiones ocultas entre diferentes clases de complejidad.
Tomemos las dos clases de complejidad más famosas. Está la clase de problemas que son fáciles de resolver, que los investigadores llaman «P», y la clase de problemas que son fáciles de verificar, que llaman «NP». ¿Son todos los problemas fáciles de verificar también fáciles de resolver? Si así fuera, eso significaría que NP sería igual a P, y toda la encriptación sería fácil de romper (entre otras consecuencias). Los teóricos de la complejidad sospechan que NP no es igual a P, pero no pueden probarlo, aunque llevan más de 50 años intentando precisar la relación entre ambas clases.
Los oráculos les han ayudado a entender mejor con qué están lidiando. Los investigadores han inventado oráculos que responden preguntas que ayudan a resolver muchos problemas diferentes. En un mundo donde cada ordenador tuviera una conexión directa con uno de estos oráculos, todos los problemas fáciles de verificar también serían fáciles de resolver, y P sería igual a NP. Pero otros oráculos menos útiles tienen el efecto opuesto. En un mundo poblado por estos oráculos, P y NP serían demostrablemente diferentes.
Los investigadores han utilizado este conocimiento para obtener una mejor comprensión del problema P contra NP. Los primeros intentos para determinar la relación entre P y NP utilizaron un truco elegante llamado diagonalización, que había sido esencial para otros resultados importantes en la informática. Pero los investigadores pronto se dieron cuenta de que cualquier prueba basada en diagonalización también se aplicaría a cualquier mundo donde cada ordenador pudiera consultar el mismo oráculo. Esto resultó ser un problema, ya que los oráculos cambian la respuesta a la pregunta de P frente a NP. Si los investigadores pudieran usar la diagonalización para probar que P y NP son diferentes en el mundo real, la misma prueba implicaría que P y NP son diferentes en un mundo con oráculos, donde claramente son equivalentes. Esto significa que cualquier solución basada en diagonalización al problema de P contra NP sería autocontradictoria. Los investigadores concluyeron que necesitarían nuevas técnicas para avanzar.
Los oráculos también han sido útiles en el estudio de la computación cuántica. En las décadas de 1980 y 1990, los investigadores descubrieron formas de aprovechar la física cuántica para resolver rápidamente ciertos problemas que parecían difíciles para los ordenadores «clásicos» ordinarios. Pero, ¿estos problemas solo parecen difíciles o realmente lo son? Demostrarlo de una manera u otra requeriría técnicas matemáticas radicalmente nuevas.
Por ello, los investigadores han estudiado cómo los ordenadores cuánticos abordan los problemas que involucran oráculos. Estos esfuerzos pueden proporcionar evidencia indirecta de que los ordenadores cuánticos realmente son más poderosos que los clásicos, y pueden ayudar a los investigadores a explorar tareas cualitativamente nuevas en las que los ordenadores cuánticos podrían destacar. A veces, incluso pueden tener aplicaciones prácticas. En 1994, el matemático aplicado Peter Shor se inspiró en un reciente resultado sobre oráculos para desarrollar un algoritmo cuántico rápido para factorizar números grandes, una tarea cuya aparente dificultad sustenta los sistemas criptográficos que mantienen segura nuestra información en línea. El descubrimiento de Shor dio inicio a una carrera para construir ordenadores cuánticos potentes que continúa hasta el día de hoy.
Es difícil predecir el futuro de la teoría de la complejidad, pero no todas las preguntas sobre la trayectoria del campo son igualmente difíciles de responder. ¿Seguirán los investigadores consultando oráculos? Las señales apuntan a que sí.
El artículo original, Why Computer Scientists Consult Oracles, se publicó el 16 de enero de 2025 en Quanta Magazine.
Traducido por César Tomé López
