MIP ^* =RE no es un error tipográfico. Es un descubrimiento pionero y el título pegadizo de un artículo reciente en el campo de la teoría de la complejidad cuántica. La teoría de la complejidad es un zoológico de "clases de complejidad" —colecciones de problemas computacionales— de las cuales MIP ^* y RE son solo dos.

El documento de 165 páginas muestra que estas dos clases son iguales. Eso puede parecer un detalle insignificante en una teoría abstracta sin ninguna aplicación en el mundo real. Pero físicos y matemáticos están acudiendo en masa para visitar el zoológico, aunque probablemente no lo entiendan todo. Porque resulta que el descubrimiento tiene consecuencias asombrosas para sus propias disciplinas.

En 1936, Alan Turing demostró que el problema de la detención (decidir algorítmicamente si un programa de computadora se detiene o se repite para siempre) no se puede resolver. Nació la informática moderna. Su éxito dio la impresión de que pronto todos los problemas prácticos cederían al tremendo poder de la computadora.

Pero pronto se hizo evidente que, mientras que algunos problemas se pueden resolver algorítmicamente, el cálculo real durará mucho después de que nuestro Sol haya engullido a la computadora que realiza el cálculo. Descubrir cómo resolver un problema algorítmicamente no era suficiente. Era vital clasificar las soluciones por eficiencia. La teoría de la complejidad clasifica los problemas según la dificultad de resolverlos. La dureza de un problema se mide en términos de cuánto dura el cálculo.

RE significa problemas que pueden resolverse con una computadora. Es el zoológico. Echemos un vistazo a algunas subclases.

La clase P consta de problemas que un algoritmo conocido puede resolver rápidamente (técnicamente, en tiempo polinomial). Por ejemplo, multiplicar dos números pertenece a P ya que la multiplicación larga es un algoritmo eficiente para resolver el problema. No se sabe que el problema de encontrar los factores primos de un número esté en P; El problema ciertamente puede ser resuelto por una computadora, pero ningún algoritmo conocido puede hacerlo de manera eficiente. Un problema relacionado, decidir si un número dado es primo, estuvo en un limbo similar hasta 2004 cuando un algoritmo eficiente mostró que este problema está en P.

Otra clase de complejidad es NP. Imagina un laberinto. "¿Hay alguna forma de salir de este laberinto?" es una pregunta de sí / no. Si la respuesta es sí, entonces hay una forma sencilla de convencernos:simplemente danos las instrucciones, los seguiremos, y encontraremos la salida. Si la respuesta es no, sin embargo, tendríamos que atravesar todo el laberinto sin encontrar una salida para convencernos.

Tales problemas de sí / no para los que, Si la respuesta es sí, podemos demostrar de manera eficiente que, pertenecen a NP. Cualquier solución a un problema sirve para convencernos de la respuesta, y entonces P está contenido en NP. Asombrosamente, una pregunta de un millón de dólares es si P =NP. Nadie lo sabe.

Confía en las máquinas

Las clases descritas hasta ahora representan problemas que enfrenta una computadora normal. Pero las computadoras están cambiando fundamentalmente:se están desarrollando computadoras cuánticas. Pero si aparece un nuevo tipo de computadora y pretende resolver uno de nuestros problemas, ¿Cómo podemos confiar en que es correcto?

Imagina una interacción entre dos entidades, un interrogador y un probador. En un interrogatorio policial, el probador puede ser un sospechoso que intenta probar su inocencia. El interrogador debe decidir si el probador es suficientemente convincente. Hay un desequilibrio; en cuanto al conocimiento, el interrogador se encuentra en una posición inferior.

En la teoría de la complejidad, el interrogador es la persona, con potencia computacional limitada, tratando de resolver el problema. El prover es la nueva computadora, que se supone que tiene un inmenso poder computacional. Un sistema de prueba interactivo es un protocolo que el interrogador puede utilizar para determinar, al menos con alta probabilidad, si el prover debe ser creído. Por analogia, estos son delitos que la policía tal vez no pueda resolver, pero al menos los inocentes pueden convencer a la policía de su inocencia. Esta es la clase IP.

Si se pueden interrogar varios probadores, y los probadores no pueden coordinar sus respuestas (como suele ser el caso cuando la policía interroga a varios sospechosos), luego llegamos a la clase MIP. Tales interrogatorios, mediante el contrainterrogatorio de las respuestas de los probadores, proporcionar al interrogador mayor poder, por lo que MIP contiene IP.

La comunicación cuántica es una nueva forma de comunicación realizada con qubits. Entrelazamiento:una característica cuántica en la que los qubits se entrelazan de manera espeluznante, incluso si está separada, hace que la comunicación cuántica sea fundamentalmente diferente a la comunicación ordinaria. Permitir que los probadores de MIP compartan un qubit entrelazado conduce a la clase MIP ^*.

Parece obvio que la comunicación Entre los probadores sólo pueden servir para ayudar a los probadores a coordinar las mentiras en lugar de ayudar al interrogador a descubrir la verdad. Por esta razón, nadie esperaba que permitir más comunicación haría que los problemas computacionales fueran más confiables y resolubles. Asombrosamente, ahora sabemos que MIP ^* =RE. Esto significa que la comunicación cuántica se comporta de manera muy diferente a la comunicación normal.

Implicaciones de gran alcance

En los 1970s, Alain Connes formuló lo que se conoció como el problema de la incrustación de Connes. Muy simplificado, se preguntó si las matrices infinitas pueden aproximarse mediante matrices finitas. Este nuevo artículo ha demostrado ahora que esto no es posible, un hallazgo importante para los matemáticos puros.

En 1993, mientras tanto, Boris Tsirelson señaló un problema de física que ahora se conoce como Problema de Tsirelson. Se trataba de dos formalismos matemáticos diferentes de una sola situación en mecánica cuántica:hasta la fecha, una teoría increíblemente exitosa que explica el mundo subatómico. Al ser dos descripciones diferentes del mismo fenómeno, era de esperar que los dos formalismos fueran matemáticamente equivalentes.

Pero el nuevo documento ahora muestra que no lo son. Se desconoce exactamente cómo ambos pueden producir los mismos resultados y ambos describen la misma realidad física, pero es por eso que los físicos también se interesan de repente.

El tiempo dirá qué otras preguntas científicas sin respuesta darán lugar al estudio de la complejidad. Indudablemente, MIP ^* =RE es un gran paso adelante.

Este artículo se ha vuelto a publicar de The Conversation con una licencia de Creative Commons. Lea el artículo original.