En la primera semana del semestre de otoño de 2007, Marco Carmosino se arrastró a una clase de matemáticas requerida para todas las carreras de informática en la Universidad de Massachusetts, Amherst. Carmosino, estudiante de segundo año, estaba considerando abandonar la universidad para diseñar videojuegos. Luego, el profesor planteó una pregunta simple que cambiaría el curso de su vida: ¿Cómo sabes que las matemáticas realmente funcionan?

“Eso me hizo sentarme y prestar atención”, recordó Carmosino, ahora científico informático teórico en IBM. Se inscribió en un seminario opcional sobre el trabajo de Kurt Gödel, cuyos vertiginosos argumentos autorreferenciales expusieron por primera vez los límites del razonamiento matemático y sentaron las bases para todo el trabajo futuro sobre los límites fundamentales de la computación. Fue mucho para asimilar.

“Yo 100% no entendí”, dijo Carmosino. “Pero sabía que quería hacerlo”.

Hoy en día, incluso los investigadores experimentados encuentran que la comprensión escasea cuando se enfrentan a la pregunta central abierta en la informática teórica, conocida como el problema P versus NP. En esencia, esa pregunta indaga si muchos problemas computacionales que durante mucho tiempo se consideraron extremadamente difíciles pueden resolverse fácilmente (a través de un atajo secreto que aún no hemos descubierto), o si, como sospechan la mayoría de los investigadores, realmente son difíciles. Lo que está en juego es nada menos que la naturaleza de lo que se puede conocer.

A pesar de décadas de esfuerzo por parte de los investigadores en el campo de la teoría de la complejidad computacional, el estudio de tales preguntas sobre la dificultad intrínseca de diferentes problemas, la resolución de la pregunta P versus NP sigue siendo difícil de alcanzar. Y ni siquiera está claro dónde debería comenzar una posible prueba.

“No hay hoja de ruta”, dijo Michael Sipser, un teórico veterano de la complejidad del Instituto Tecnológico de Massachusetts que pasó años lidiando con el problema en la década de 1980. “Es como si estuvieras adentrándote en el desierto”.

Parece que demostrar que los problemas computacionales son difíciles de resolver es en sí mismo una tarea difícil. Pero ¿por qué es tan difícil? ¿Y qué tan difícil es? Carmosino y otros investigadores en el subcampo de la metacomplejidad reformulan preguntas como esta como problemas computacionales, impulsando el campo hacia adelante al volver la lente de la teoría de la complejidad sobre sí misma.

“Puedes pensar, 'Está bien, eso es genial. Tal vez los teóricos de la complejidad se han vuelto locos'”, dijo raul ilango, un estudiante de posgrado del MIT que ha producido algunos de los resultados recientes más emocionantes en el campo.

Al estudiar estas preguntas introspectivas, los investigadores han aprendido que la dificultad de probar la dureza computacional está íntimamente ligada a preguntas fundamentales que al principio pueden parecer no relacionadas. ¿Qué tan difícil es detectar patrones ocultos en datos aparentemente aleatorios? Y si existen problemas verdaderamente difíciles, ¿con qué frecuencia son difíciles?

“Ha quedado claro que la metacomplejidad está cerca del corazón de las cosas”, dijo De Scott Aaronson, un teórico de la complejidad de la Universidad de Texas, Austin.

Esta es la historia del largo y sinuoso camino que condujo a los investigadores desde el problema P versus NP hasta la metacomplejidad. No ha sido un viaje fácil: el camino está plagado de giros falsos y obstáculos, y vuelve sobre sí mismo una y otra vez. Sin embargo, para los investigadores de la metacomplejidad, ese viaje a un paisaje inexplorado es su propia recompensa. Comience a hacer preguntas aparentemente simples, dijo Kabanets de San Valentín, un teórico de la complejidad de la Universidad Simon Fraser en Canadá, y “no tienes idea de a dónde vas a ir”.

Incógnitas conocidas

El problema P versus NP debe su nombre mediocre al hábito de los teóricos de la complejidad de clasificar los problemas computacionales en amplios “clases de complejidad” con etiquetas que sugieren los símbolos de cotización de Nasdaq. Un problema computacional es aquel que, en principio, puede resolverse mediante un algoritmo: una lista de instrucciones especificada con precisión. Pero no todos los algoritmos son igualmente útiles, y la variación entre algoritmos sugiere diferencias fundamentales entre problemas en diferentes clases. El desafío para los teóricos de la complejidad es convertir estas sugerencias en teoremas rigurosos sobre las relaciones entre las clases de complejidad.

Estas relaciones reflejan verdades inmutables sobre la computación que van mucho más allá de cualquier tecnología específica. “Esto es como descubrir las leyes del universo”, dijo Kabanets.

“P” y “NP” son los dos miembros más famosos de una creciente colección de animales de cientos de clases de complejidad. En términos generales, P es la clase de problemas que se pueden resolver fácilmente, como ordenar alfabéticamente una lista. NP es la clase de problemas con soluciones fácilmente comprobables, como los sudokus. Dado que todos los problemas fácilmente resolubles también son fáciles de verificar, los problemas en P también están en NP. Pero algunos problemas de NP parecen difíciles de resolver: no puedes intuir de inmediato la solución a un sudoku sin antes probar muchas posibilidades. ¿Podría ser que esta aparente dureza sea solo una ilusión, que haya un solo truco simple para resolver todos los problemas fácilmente verificables?

Si es así, entonces P = NP: Las dos clases son equivalentes. Si ese es el caso, debe haber algún algoritmo que haga que sea trivial resolver enormes sudokus, optimizar las rutas de envío globales, romper el cifrado de última generación y automatizar las pruebas de teoremas matemáticos. Si P ≠ NP, entonces muchos problemas computacionales que en principio son solucionables permanecerán en la práctica para siempre fuera de nuestro alcance.

Los investigadores se preocuparon por los límites del razonamiento matemático formal mucho antes de que se articulara por primera vez el problema P versus NP; de hecho, mucho antes del comienzo de la informática moderna. En 1921, luchando con la misma pregunta que captaría la atención de Carmosino casi un siglo después, el matemático David Hilbert propuso un programa de investigación para fundamentar las matemáticas en una certeza absoluta. Esperaba partir de unas pocas suposiciones simples, llamadas axiomas, y derivar una teoría matemática unificada que cumpliera con tres criterios clave.

La primera condición de Hilbert, la consistencia, era el requisito esencial de que las matemáticas estuvieran libres de contradicciones: si dos enunciados contradictorios pudieran probarse a partir de los mismos axiomas, toda la teoría sería insalvable. Pero una teoría podría estar libre de contradicciones y aún limitada en su alcance. Esa fue la motivación de la segunda condición de Hilbert, la completitud: el requisito de que todos los enunciados matemáticos sean demostrablemente verdaderos o demostrablemente falsos. Su tercer criterio, la decidibilidad, exigía un procedimiento mecánico inequívoco para determinar si un enunciado matemático era verdadero o falso. Dirigiéndose a una conferencia en 1930, Hilbert declaró: “Nuestro lema será 'Debemos saber, sabremos'”.

Solo un año después, Gödel asestó el primer golpe al sueño de Hilbert. Él demostrado que una declaración contraproducente como "esta declaración no se puede probar" podría derivarse de cualquier conjunto apropiado de axiomas. Si tal afirmación es realmente indemostrable, la teoría está incompleta, pero si es demostrable, la teoría es inconsistente, un resultado aún peor. En el mismo artículo, Gödel también demostró que ninguna teoría matemática podría probar su propia consistencia.

Los investigadores aún albergaban la esperanza de que una futura teoría de las matemáticas, aunque necesariamente incompleta, pudiera resultar decidible. Tal vez podrían desarrollar procedimientos que identificarían todas las afirmaciones demostrables mientras se alejaban de proposiciones desconcertantes como la de Gödel. El problema era que nadie sabía razonar sobre estos procedimientos hipotéticos.

Luego, en 1936, un estudiante graduado de 23 años llamado Alan Turing reformuló la condición de decidibilidad de Hilbert en el entonces desconocido lenguaje de la computación y le asestó un golpe fatal. Turing formuló un modelo matemático, ahora conocido como el Máquina de Turing — que podría representar todos los algoritmos posibles, y mostró que si existiera el procedimiento de Hilbert, encajaría dentro de este modelo. Luego usó métodos autorreferenciales como el de Gödel para la existencia de declaraciones indecidibles o, de manera equivalente, problemas no computables que ningún algoritmo podría resolver.

El programa de Hilbert estaba en ruinas: siempre habría límites fundamentales sobre lo que se podía demostrar y lo que se podía calcular. Pero a medida que las computadoras evolucionaron de abstracciones teóricas a máquinas reales, los investigadores se dieron cuenta de que la simple distinción de Turing entre problemas solucionables e irresolubles dejaba muchas preguntas sin respuesta.

En la década de 1960, los informáticos habían desarrollado algoritmos rápidos para resolver algunos problemas, mientras que para otros los únicos algoritmos conocidos eran insoportablemente lentos. ¿Qué pasaría si la pregunta no fuera solo si los problemas tienen solución, sino qué tan difíciles son de resolver?

“Surge una rica teoría, y ya no sabemos las respuestas”, dijo Carmosino.

Caminos divergentes

Para ilustrar cuán desconcertantes pueden ser las preguntas sobre la dureza, consideremos un par de problemas estrechamente relacionados que involucran gráficos. Estas son redes de puntos, llamados nodos, conectados por líneas, llamados aristas. Los informáticos las utilizan para modelar todo, desde computación cuántica En el correo electrónico “Su Cuenta de Usuario en su Nuevo Sistema XNUMXCX”. flujo de tráfico.

Suponga que le dan un gráfico y le piden que encuentre algo llamado ruta hamiltoniana, una ruta que pasa por cada nodo exactamente una vez. Este problema es claramente solucionable en principio: solo hay un número finito de rutas posibles, por lo que si todo lo demás falla, puede verificar cada una. Eso está bien si solo hay unos pocos nodos, pero incluso para gráficos un poco más grandes, la cantidad de posibilidades se sale de control, lo que convierte rápidamente a este algoritmo simple en inútil.

Hay algoritmos de ruta hamiltoniana más sofisticados que ofrecen una mejor batalla, pero el tiempo que requieren los algoritmos para resolver el problema invariablemente crece exponencialmente con el tamaño del gráfico. Los gráficos no tienen que ser muy grandes antes de que incluso los mejores algoritmos que los investigadores hayan descubierto no puedan encontrar un camino "en un período de tiempo razonable", dijo russell impagliazzo, un teórico de la complejidad de la Universidad de California, San Diego. “Y por 'cantidad de tiempo razonable', me refiero a 'antes de que termine el universo'”.

El problema del camino hamiltoniano tiene otra propiedad interesante. Si alguien afirma haber encontrado una ruta hamiltoniana en un gráfico en particular, puede verificar rápidamente si la solución es válida, incluso si el gráfico es muy grande. Todo lo que necesita hacer es seguir la ruta y marcar los nodos uno por uno, verificando que no haya marcado ningún nodo dos veces. Si no faltan nodos al final, entonces el camino es hamiltoniano.

El tiempo requerido para ejecutar este algoritmo de verificación de soluciones es proporcional al tamaño del gráfico. Eso lo coloca en la categoría más amplia de algoritmos polinómicos, cuyos tiempos de ejecución aumentan como funciones polinómicas del tamaño del gráfico. El crecimiento polinómico es moderado en comparación con el crecimiento exponencial, por lo que los algoritmos polinómicos siguen siendo viables incluso en gráficos grandes. “Es dramáticamente más eficiente”, dijo Carmosino.

El problema de la ruta hamiltoniana tiene una marcada asimetría: puede verificar una solución correcta utilizando un algoritmo polinomial rápido, pero para encontrar una solución necesitará un algoritmo exponencial lento. Esa asimetría puede no parecer sorprendente: es más fácil reconocer una obra maestra artística que crear una, más fácil verificar una prueba matemática que probar un nuevo teorema, pero no todos los problemas computacionales tienen este carácter asimétrico. De hecho, un problema muy similar a encontrar caminos hamiltonianos se comporta de manera bastante diferente.

Suponga que nuevamente le dan un gráfico, pero ahora se le pide que encuentre un "camino euleriano" que cruce cada borde exactamente una vez. De nuevo, hay un algoritmo polinomial para comprobar posibles soluciones, pero esta vez también hay un algoritmo polinomial para resolver el problema. No hay asimetría aquí. En la teoría de la complejidad, algunos caminos parecen más fáciles de encontrar que otros.

Tanto el problema de la ruta hamiltoniana como el problema de la ruta euleriana están en la clase de complejidad NP, definida para incluir todos los problemas cuyas soluciones pueden verificarse mediante algoritmos polinómicos. El problema de la ruta euleriana también cae en la clase P porque un algoritmo polinomial puede resolverlo, pero aparentemente, eso no es cierto para el problema de la ruta hamiltoniana. ¿Por qué estos dos problemas de gráficas, tan superficialmente similares, deberían diferir tan dramáticamente? Esa es la esencia del problema P versus NP.

Universalmente duro

Al principio, las clases de complejidad parecían categorías convenientes para clasificar problemas que eran similares pero no estaban directamente relacionados; nadie sospechaba que encontrar caminos hamiltonianos tuviera algo que ver con otros problemas computacionales difíciles.

Luego, en 1971, un año después de mudarse a la Universidad de Toronto después de que se le negara la titularidad en los Estados Unidos, el teórico de la complejidad Stephen Cook una publicación resultado extraordinario. Identificó un problema NP particular con una característica extraña: si hay un algoritmo polinomial que puede resolver ese problema, también puede resolver cualquier otro problema en NP. El problema “universal” de Cook, al parecer, era una columna solitaria que apuntalaba la clase de problemas aparentemente difíciles, separándolos de los problemas fáciles que se encontraban debajo. Resuelva ese problema y el resto de NP se derrumbará.

Cook sospechaba que no había un algoritmo rápido para su problema universal, y lo dijo a la mitad del artículo, y agregó: "Creo que vale la pena dedicar un esfuerzo considerable a tratar de probar esta conjetura". "Esfuerzo considerable" resultaría ser un eufemismo.

Casi al mismo tiempo, un estudiante graduado en la Unión Soviética llamado Leonid Levin demostró ser un resultado similar, excepto que identificó varios problemas universales diferentes. Además, el teórico estadounidense de la complejidad ricardo karpe demostrado que la propiedad de universalidad identificada por Cook (y Levin, aunque Karp y Cook no conocieron el trabajo de Levin hasta años después) era en sí misma casi universal. Casi todos los problemas de NP sin un algoritmo polinomial conocido, es decir, casi todos los problemas fáciles de verificar que parecían difíciles, tenían la misma propiedad, que se conoció como NP-completo.

Esto significa que todos los problemas NP-completos: el problema del camino hamiltoniano, sudoku y miles de otros — son en un sentido preciso equivalentes. “Tienes todas estas diferentes tareas naturales, y todas mágicamente resultan ser la misma tarea”, dijo Ilango. “Y todavía no sabemos si esa misma tarea es posible o no”.

Resolver la dificultad de cualquier problema NP-completo sería suficiente para resolver la pregunta P versus NP. Si P ≠ NP, la distinción entre problemas fáciles y difíciles se sustenta en miles de columnas que son todas igualmente sólidas. Si P = NP, todo el edificio está al borde del colapso, esperando que caiga una sola pieza.

Cook, Levin y Karp habían unificado lo que parecían ser muchos problemas no relacionados. Ahora todo lo que tenían que hacer los teóricos de la complejidad era resolver un problema: ¿P = NP o no?

Cincuenta años después, la pregunta sigue sin respuesta. Kabanets comparó el razonamiento sobre los límites de la computación con la inspección de un vasto territorio sin ningún sentido del panorama general. Un ser con un poder computacional ilimitado podría mirar hacia abajo desde la cima de una montaña y abarcar todo el paisaje a la vez, pero los simples mortales no pueden contar con ese tipo de ventaja. “Aquellos de nosotros en la parte inferior de la montaña podemos intentar tal vez saltar hacia arriba y hacia abajo para tener una mejor vista”, dijo.

Suponga que P = NP. Para probarlo, los investigadores tendrían que encontrar un algoritmo rápido para un problema NP-completo, que podría estar escondido en algún rincón oscuro de ese vasto paisaje. No hay garantía de que lo encontrarán pronto: los teóricos de la complejidad ocasionalmente descubierto CRISPR algoritmos ingeniosos para problemas aparentemente difíciles (aunque no NP-completos) solo después de décadas de trabajo.

Ahora suponga que P ≠ NP. Probar eso parece aún más difícil. Los teóricos de la complejidad tendrían que establecer que no podría existir ningún algoritmo rápido, anticipando y frustrando efectivamente los mejores esfuerzos de todos los futuros investigadores.

No saber por dónde empezar es parte del problema. Pero no es que los investigadores no lo hayan intentado. A lo largo de las décadas, han atacado el problema desde muchos ángulos y han encontrado el camino bloqueado a cada paso. “Es una de las verdades más flagrantes de la informática teórica”, dijo Carmosino. “Cuando tienes un fenómeno que es tan duradero, quieres alguna explicación”.

Para el último año de Carmosino en la universidad, su curiosidad lo llevó de Gödel a un curso de posgrado en teoría de la complejidad. Se sorprendió al darse cuenta de que dedicaba más tiempo a la tarea que a su proyecto de pasión, un programa de computadora que aprendería la estructura narrativa de los cuentos de hadas y generaría otros nuevos.

“Pensé, 'Vaya, necesito tomarme esto en serio'”, recordó Carmosino. Al poco tiempo, estaba tan absorto en el tema que su mentor le sugirió gentilmente que reconsiderara sus planes posteriores a la graduación.

“Me dijo: 'Sabes, si quieres seguir haciendo esto, si quieres seguir haciendo informática teórica y teoría de la complejidad, puedes: se llama escuela de posgrado'”, dijo Carmosino. Después de obtener su maestría, se mudó a San Diego en 2012 para trabajar en un doctorado supervisado por Impagliazzo.

El principal objetivo de Carmosino, en un principio, era comprender mejor una papel de referencia de dos décadas antes que había capturado su imaginación. Ese artículo, de los teóricos de la complejidad Aleksandr Razborov y steven rudich, había demostrado que cierta estrategia "natural" para demostrar que P ≠ NP fallaría casi con certeza, porque el éxito tendría un alto costo, el colapso total de la criptografía, que los investigadores consideraban muy poco probable. Los investigadores interpretaron el resultado de Razborov y Rudich como una barrera para este enfoque popular para probar P ≠ NP.

Esta "barrera de pruebas naturales" es solo una de las muchas barreras conocidas para resolver problemas abiertos en la teoría de la complejidad. Cada uno actúa como un obstáculo, advirtiendo que un camino aparentemente prometedor es en realidad un callejón sin salida. Juntas, estas barreras indican que cualquier prueba que resuelva el problema de P versus NP tendría que ser radicalmente diferente a todo lo que se usó en el pasado; es por eso que la mayoría de los investigadores creen que la solución aún está lejos. Pero al menos las barreras les dicen dónde no mirar.

“La teoría de la complejidad está maldita y bendecida con tantas barreras”, dijo Ilango.

Cuando Carmosino encontró la barrera de las pruebas naturales, tenía casi 20 años. Pero sospechaba que tenía más lecciones para los investigadores. Ese sentimiento sería reivindicado algún día cuando él y tres colegas demostraron un resultado sorprendente al examinar la barrera de las pruebas naturales desde la perspectiva de la metacomplejidad. Su prueba fue uno de los pocos resultados importantes que despertaron un nuevo interés en la metacomplejidad, lo que llevó a una ráfaga de progreso en los últimos años.

Pero para seguir el camino desde la barrera de las pruebas naturales hasta la metacomplejidad, tendremos que retroceder hasta donde dejamos a los investigadores en la década de 1970, cuando comenzaron a abordar el problema de P versus NP. ¿Qué hizo que fuera tan difícil demostrar que los problemas eran difíciles?

Un camino tortuoso

Al principio, los investigadores intentaron demostrar que P ≠ NP, es decir, probar que algunos problemas de NP no se pueden resolver con ningún algoritmo polinomial posible, utilizando variaciones de las técnicas que Turing había usado para demostrar que algunos problemas no se pueden resolver con ningún algoritmo. . pero rápidamente descubierto CRISPR una prueba de que esos métodos no funcionarían: la primera barrera importante para resolver la pregunta P versus NP. Entonces comenzaron a buscar otro enfoque, y pronto encontraron uno en el trabajo del contemporáneo de Turing. Claude Shannon.

Shannon, quien creció en un pequeño pueblo en el norte de Michigan, parecía una figura improbable para marcar el comienzo de la era de la información. Sin embargo, ejemplificó la naturaleza interdisciplinaria de la disciplina emergente de la informática, sintiéndose igualmente a gusto en la ingeniería eléctrica y la lógica matemática. En su tesis de maestría, Shannon mostró cómo los circuitos hechos de interruptores electromecánicos podrían representar expresiones lógicas que involucran variables booleanas, cantidades que pueden tomar solo dos valores (como verdadero o falso, o 1 y 0).

En estas expresiones, las variables booleanas están unidas entre sí por las "puertas lógicas" AND, OR y NOT. La expresión elemental A AND B, por ejemplo, es verdadera cuando tanto A como B son verdaderas, y falsa en caso contrario; A OR B, por otro lado, es verdadero si al menos una de las dos variables es verdadera. Una puerta NOT es aún más simple: invierte el valor de una sola variable. Con suficientes de estos bloques de construcción básicos, puede realizar cualquier cálculo.

“Cuando miras tu computadora, al final del día, ¿qué está haciendo? Está corriendo un circuito”, dijo Ilango.

El trabajo de Shannon sugirió a los teóricos una nueva forma de pensar sobre la dificultad de los problemas computacionales, llamada "complejidad de circuitos", aunque los circuitos en cuestión son solo abstracciones matemáticas. Durante un tiempo, los investigadores pensaron que este enfoque podría ser la forma de resolver P versus NP, pero finalmente el camino se topó con la barrera de las pruebas naturales.

El marco de la complejidad del circuito requiere repensar los conceptos más básicos en el modelo de computación de Turing. Aquí, en lugar de problemas computacionales y los algoritmos que los resuelven, los investigadores consideran funciones booleanas y los circuitos que las calculan. Una función booleana toma variables booleanas (verdaderos y falsos, 1 y 0) y genera verdadero o falso, 1 o 0. Y como un algoritmo, un circuito describe un procedimiento para producir una salida dada cualquier entrada.

“Tengo entendido que la gente comenzó a trabajar en la complejidad de los circuitos porque decidieron que las máquinas de Turing eran demasiado complicadas”, dijo. Ryan Williams, un teórico de la complejidad en el MIT. “Podemos estudiar los circuitos puerta por puerta”.

Así como puede haber muchos algoritmos para resolver cualquier problema computacional dado, algunos más rápidos que otros, muchos circuitos diferentes pueden calcular cualquier función booleana dada, algunos con menos puertas que otros. Los investigadores definen la complejidad del circuito de una función como el número total de puertas en el circuito más pequeño que la calcula. Para una función con un número fijo de variables de entrada, la complejidad del circuito también es un número fijo, mayor para algunas funciones que para otras.

Pero en muchos casos, puede considerar versiones más complicadas de la misma función al aumentar el número de variables de entrada, al igual que puede hacer que el problema de la ruta hamiltoniana sea más difícil al considerar gráficos más grandes. Luego, los investigadores consideran la misma pregunta que hacen cuando estudian los tiempos de ejecución de los algoritmos: ¿el número mínimo de puertas necesarias para calcular una función booleana crece polinomial o exponencialmente a medida que aumenta el número de variables de entrada? Los investigadores llaman a estas dos categorías de funciones "fáciles de calcular" y "difíciles de calcular", respectivamente.

Una función booleana fácil de calcular es similar a un problema computacional de la clase P, uno que puede resolverse mediante un algoritmo que se ejecuta en tiempo polinomial. Pero también hay funciones análogas a los problemas NP duros, donde la mejor manera que los investigadores han descubierto para calcular versiones progresivamente más grandes requiere un número exponencialmente mayor de puertas, pero la respuesta se puede verificar fácilmente. Si los teóricos de la complejidad pudieran probar que realmente no hay mejor manera de calcular tal función, eso implicaría que P ≠ NP.

Esta fue la estrategia que siguieron la mayoría de los teóricos de la complejidad en la década de 1980. Y las probabilidades estaban de su lado. Shannon tenía demostrado en 1949 que casi todas las tablas de verdad booleanas (que no son más que una larga lista de todas las posibles entradas y salidas de una función booleana de tamaño fijo) tienen una complejidad de circuito prácticamente tan alta como sea posible. Usó un argumento sorprendentemente simple: hay muchas menos formas de combinar un pequeño número de puertas que formas de combinar muchas puertas.

“Simplemente no hay suficientes circuitos pequeños para todos”, dijo Aaronson.

Así que los teóricos de la complejidad se encontraron en una situación curiosa. Si casi todas las tablas de verdad tienen circuitos de alta complejidad, entonces casi todas las funciones booleanas deben ser difíciles de calcular. Los investigadores solo tenían que identificar una sola función de este tipo que también se supiera que estaba en la clase NP. ¿Qué tan difícil puede ser?

Cripto hermanos

Al principio, el progreso fue rápido. En 1981, Sipser y dos colaboradores demostrado que cierta función booleana era definitivamente difícil de calcular si usaban circuitos con ciertas restricciones sobre cómo se podían organizar las puertas.

“La fantasía era que podrías probar cosas sobre estos modelos restringidos y luego construir sobre lo que has aprendido para trabajar con menos y menos restricciones”, dijo Sipser.

En 1985, Razborov dio el siguiente gran paso. Acababa de comenzar la escuela de posgrado en Moscú y se unió al esfuerzo accidentalmente mientras abordaba un problema en una rama diferente de las matemáticas, donde resultó que resolver el problema P versus NP era un requisito previo.

“Simplemente tuve suerte de no saber cuán difícil era este problema”, dijo Razborov. “De lo contrario, tal vez ni siquiera habría comenzado”.

Razborov analizó circuitos que contenían solo compuertas AND y OR, y demostrado que una función en particular era difícil de calcular usando tales circuitos, sin importar cómo estuvieran dispuestas las puertas; además, se sabía que esa función era NP-completa. Todo lo que los investigadores tuvieron que hacer para resolver P versus NP fue extender las técnicas de Razborov a circuitos con puertas NOT.

“Había una especie de sentimiento universal de que un paso más, un golpe más, y lo conseguiremos”, dijo Razborov. Pero eso no es lo que pasó. El propio Razborov demostró que su método fallaría si NO se añadieran puertas a la mezcla, y nadie podría encontrar otra forma de avanzar. A medida que pasaban los años, comenzó a preguntarse por qué el rastro se había desvanecido.

En Estados Unidos, Rudich se planteaba la misma pregunta. Él e Impagliazzo eran compañeros de universidad que se habían graduado juntos en la escuela de posgrado. Su amistad había sido provocada por una fascinación compartida por las pruebas autorreferenciales de Gödel y Turing y sus implicaciones para los fundamentos de las matemáticas y la informática.

“Nuestra broma era que íbamos a tener un botón que decía 'autoreferencia'”, dijo Impagliazzo.

Como estudiantes de posgrado, tanto Rudich como Impagliazzo trabajaron en los fundamentos teóricos de la complejidad de la criptografía, un tema que ofrece quizás la mejor motivación práctica para intentar probar P ≠ NP. Los criptógrafos ocultan los mensajes secretos encubriéndolos con "pseudoaleatoriedad": un mensaje cifrado de esta manera se verá como un revoltijo aleatorio de números para cualquier intruso, pero aún puede ser descifrado por el destinatario previsto. Pero, ¿cómo puede estar seguro de que a un posible intruso le resultará demasiado difícil descifrar el código?

Ahí es donde entra en juego la teoría de la complejidad. Los métodos de encriptación más utilizados en la actualidad se basan en problemas de NP aparentemente difíciles: para desencriptar el mensaje, un atacante necesitaría un algoritmo rápido aún no descubierto para resolver el problema. Para establecer que estos métodos son realmente seguros, una cosa que debe hacer es demostrar que P ≠ NP. Sin una prueba, dijo Sipser, todo lo que puedes hacer es "esperar que quienquiera que estés tratando de ocultar el secreto no sea mejor matemático que tú".

Aunque fascinante por derecho propio, la criptografía parecía muy alejada de los argumentos autorreferenciales que habían atraído por primera vez a Rudich e Impagliazzo al campo. Pero mientras Rudich luchaba por comprender por qué se había estancado el enfoque de la complejidad del circuito, comenzó a darse cuenta de que, después de todo, los dos temas no estaban tan separados. La estrategia que los investigadores habían adoptado en sus intentos de demostrar que P ≠ NP tenía un carácter contraproducente que recordaba la famosa proposición de Gödel "esta afirmación no se puede probar", y la criptografía podría ayudar a explicar por qué. En Rusia, Razborov descubrió una conexión similar casi al mismo tiempo. Estas fueron las semillas de la barrera de las pruebas naturales.

La tensión en el corazón de la barrera de las pruebas naturales es que la tarea de distinguir funciones de alta complejidad de las de baja complejidad es similar a la tarea de distinguir la verdadera aleatoriedad de la seudoaleatoriedad utilizada para cifrar mensajes. Nos gustaría mostrar que las funciones de alta complejidad son categóricamente diferentes de las funciones de baja complejidad, para demostrar que P ≠ NP. Pero también nos gustaría que la pseudoaleatoriedad sea indistinguible de la aleatoriedad, para tener confianza en la seguridad de la criptografía. Tal vez no podamos tenerlo en ambos sentidos.

una broma cruel

En 1994, Razborov y Rudich se dieron cuenta de que habían encontrado ideas similares y comenzaron a trabajar juntos para combinar sus resultados. Primero observaron que todos los intentos anteriores de probar P ≠ NP utilizando la complejidad del circuito habían adoptado la misma estrategia general: identificar una propiedad especial de una función booleana NP-completa, luego demostrar que ninguna función fácil de calcular podría compartir esa propiedad. Eso mostraría que la función NP-completa elegida fue realmente difícil de calcular, demostrando que P ≠ NP.

Sipser, Razborov y otros habían utilizado esta misma estrategia con éxito para demostrar sus resultados más limitados y, en todos los casos, la propiedad especial que identificaron los investigadores fue compartida por la mayoría de las funciones booleanas. Razborov y Rudich acuñaron el término “prueba natural” para referirse a este caso en el que la propiedad estaba ampliamente compartida, simplemente porque no había otra alternativa conocida. Si las pruebas "antinaturales" fueran posibles, tendrían que ser muy contrarias a la intuición y merecedoras de ese nombre.

Luego, Razborov y Rudich demostraron su resultado principal: una prueba natural de P ≠ NP requeriría una comprensión muy completa de cómo difieren las funciones fáciles de calcular y las difíciles de calcular, y ese conocimiento también podría impulsar un algoritmo rápido para detectar funciones fáciles de calcular. -para calcular funciones incluso si son superficialmente complicadas. Si los teóricos de la complejidad hubieran tenido éxito en una prueba natural de P ≠ NP, habrían descubierto una forma casi infalible de echar un vistazo a una tabla de verdad arbitraria y determinar si la función correspondiente tenía una complejidad de circuito alta o baja, un resultado mucho más fuerte y más general que se habían propuesto probar.

“Casi no puedes evitar obtener más de lo que esperabas”, dijo Carmosino.

Es como si intentara verificar una declaración específica, pero cada intento se convirtió en un modelo para un detector de mentiras de uso general: parecería demasiado bueno para ser verdad. Para los teóricos de la complejidad, el sorprendente poder de las pruebas naturales también hizo que el éxito pareciera menos probable. Pero si tal prueba hubiera tenido éxito, las consecuencias inesperadas serían malas noticias para la criptografía, debido a la conexión entre la complejidad del circuito y la pseudoaleatoriedad.

Para comprender esta conexión, imagine mirar la columna de salida en la tabla de verdad de una función booleana con muchas variables de entrada y reemplazar cada "verdadero" con 1 y cada "falso" con 0:

Si la función booleana tiene un circuito de alta complejidad, esa larga lista de salidas será, en principio, indistinguible de una cadena verdaderamente aleatoria de 0 y 1, que se obtiene lanzando repetidamente una moneda, por ejemplo. Pero si la función tiene un circuito de baja complejidad, la cadena debe tener una descripción simple y sucinta, incluso si parece complicada. Eso lo hace muy similar a las cadenas pseudoaleatorias utilizadas en criptografía, cuya sucinta descripción es el mensaje secreto enterrado en esa aparente aleatoriedad.

Entonces, el resultado de Razborov y Rudich mostró que cualquier prueba natural de P ≠ NP también produciría un algoritmo rápido que podría distinguir cadenas pseudoaleatorias que contienen mensajes ocultos de cadenas verdaderamente aleatorias. La criptografía segura sería imposible, precisamente lo contrario de lo que los investigadores esperaban establecer al demostrar que P ≠ NP.

Por otro lado, si la criptografía segura es posible, las pruebas naturales no son una estrategia viable para probar P ≠ NP, un requisito previo para la criptografía segura. Esa es la barrera de las pruebas naturales en pocas palabras. Parecía como si los teóricos de la complejidad fueran los receptores de una broma cruel.

“Si crees en la dureza, entonces debes creer que es difícil probar la dureza”, dijo Kabanets.

En el metaverso

Esa conexión entre las implicaciones de la conjetura P ≠ NP y la dificultad de probarla era intrigante, pero difícil de precisar. Por un lado, la barrera de las pruebas naturales solo bloqueó un enfoque para probar P ≠ NP. Por otro lado, vinculó la dificultad de probar P ≠ NP no a P ≠ NP en sí mismo, sino a la existencia de criptografía segura, un problema estrechamente relacionado pero no del todo equivalente. Para comprender verdaderamente la conexión, los investigadores tendrían que sentirse cómodos con la metacomplejidad.

“Existe esta intuición de que 'oh, debido a que P ≠ NP, es difícil probar que P ≠ NP'”, dijo Williams. "Pero para que esta intuición tenga sentido, debes comenzar a pensar en la tarea de probar algo como P ≠ NP como un problema computacional".

Eso es lo que hizo Kabanets como estudiante de posgrado. Había crecido en Ucrania y terminó sus estudios universitarios en informática dos años después de la caída de la Unión Soviética. En la confusión que siguió, tuvo pocas oportunidades de dedicarse a los temas teóricos que más le interesaban.

“Quería hacer algo más académico”, recordó Kabanets. “Y también tenía curiosidad por ver el mundo”. Se mudó a Canadá para realizar sus estudios de posgrado y allí fue donde aprendió sobre la barrera de las pruebas naturales. Al igual que Carmosino, Kabanets quedó prendado del resultado. “Parecía muy profundo que tuvieras esta conexión”, dijo.

En 2000, hacia el final de su tiempo en la escuela de posgrado, descubrió que la barrera de las pruebas naturales seguía surgiendo en sus conversaciones con Jin Yi Cai, un teórico de la complejidad que visitaba Toronto en un año sabático en ese momento. Comenzaron a ver la barrera no como un obstáculo sino como una invitación, una oportunidad para investigar con precisión lo difícil que era demostrar que los problemas eran difíciles. El en el que expusieron esta nueva perspectiva se convertiría en uno de los primeros trabajos más influyentes en el campo naciente de la metacomplejidad.

El artículo de Kabanets y Cai destacó un problema computacional implícito en la formulación de la barrera de las pruebas naturales de Razborov y Rudich: Dada la tabla de verdad de una función booleana, determine si tiene una complejidad de circuito alta o baja. Llamaron a esto el problema del tamaño mínimo del circuito, o MCSP.

MCSP es un problema de metacomplejidad por excelencia: un problema computacional cuyo tema no es la teoría de grafos u otro tema externo, sino la teoría de la complejidad en sí misma. De hecho, es como una versión cuantitativa de la pregunta que llevó a los teóricos de la complejidad a abordar P versus NP utilizando el enfoque de complejidad de circuitos en la década de 1980: ¿Qué funciones booleanas son difíciles de calcular y cuáles son fáciles?

“Si se nos ocurriera un algoritmo MCSP, sería como una forma de automatizar lo que estamos haciendo en la teoría de la complejidad”, dijo Impagliazzo. “Al menos debería darnos una gran perspectiva sobre cómo hacer mejor nuestro trabajo”.

Los teóricos de la complejidad no se preocupan de que este algoritmo mágico los deje sin trabajo; no creen que exista en absoluto, porque Razborov y Rudich demostraron que cualquier algoritmo de este tipo para distinguir tablas de verdad de alta complejidad de las de baja complejidad haría criptografía imposible. Eso significa que MCSP es probablemente un problema computacional difícil. Pero, ¿qué tan difícil es? ¿Es NP-completo, como el problema de la ruta hamiltoniana y casi todos los demás problemas con los que lucharon los investigadores en la década de 1960?

Para problemas en NP, "¿qué tan difícil es?" suele ser bastante fácil de responder, pero MCSP parecía ser un extraño caso atípico. “Tenemos muy pocos problemas 'flotantes' que no hayan sido conectados a esta isla de problemas NP-completos, aunque parezcan ser difíciles”, dijo Kabanets.

Kabanets sabía que él y Cai no eran los primeros en considerar el problema que habían denominado MCSP. Los matemáticos soviéticos habían estudiado un problema muy similar a partir de la década de 1950, en un primer intento por comprender la dificultad intrínseca de diferentes problemas computacionales. Leonid Levin había luchado con él mientras desarrollaba lo que se convertiría en la teoría del NP-completo a fines de la década de 1960, pero no pudo demostrar que era NP-completo y publicó su artículo seminal sin él.

Después de eso, el problema atrajo poca atención durante 30 años, hasta que Kabanets y Cai notaron su conexión con la barrera de las pruebas naturales. Kabanets no esperaba resolver la cuestión por sí mismo, sino que quería explorar por qué había sido tan difícil demostrar que este problema aparentemente difícil sobre la dureza computacional era realmente difícil.

“Es, en cierto sentido, meta-meta-complejidad”, dijo Raúl Santhanam, un teórico de la complejidad de la Universidad de Oxford.

Pero, ¿era la dureza total o había al menos alguna forma de entender por qué los investigadores no habían logrado demostrar que MCSP era NP-completo? Kabanets descubrió que, sí, había una razón: la dificultad de comprender la complejidad del circuito actúa como una barrera para cualquier estrategia conocida para probar la integridad NP de MCSP, un problema que en sí mismo tiene que ver con la dificultad de comprender la complejidad del circuito. La lógica retorcida y contraproducente de la barrera de las pruebas naturales parecía ineludible.

También es posible que MCSP no sea NP-completo, pero eso también parece poco probable: ya se sabe que ciertas variantes más simples del problema son NP-completo.

“Simplemente no tenemos un buen lugar para colocarlo que lo relacione directamente con todos los demás problemas que estudiamos”, dijo Impagliazzo.

Kabanets había iluminado el extraño comportamiento de MCSP, pero no sabía cómo hacer más progresos. La investigación de la metacomplejidad se redujo a un goteo. Volvería a florecer 16 años después, cuando los investigadores descubrieron una conexión sorprendente con otra pregunta fundamental: ¿Qué tan difícil es resolver problemas si solo te preocupas por obtener la respuesta correcta la mayor parte del tiempo?

Guerra de las palabras

Para los problemas cotidianos, las respuestas que funcionan la mayor parte del tiempo suelen ser lo suficientemente buenas. Planificamos nuestros viajes diarios para los patrones de tráfico típicos, por ejemplo, no para los peores escenarios.

La mayoría de los teóricos de la complejidad son más difíciles de satisfacer: solo se contentan con declarar un problema fácil si pueden encontrar un algoritmo rápido que obtenga la respuesta correcta en cada entrada posible. Ese enfoque estándar clasifica los problemas de acuerdo con lo que los investigadores llaman complejidad del "peor de los casos". Pero también existe una teoría de la complejidad del "caso promedio", en la que los problemas se consideran fáciles si hay un algoritmo rápido que obtiene la respuesta correcta en la mayoría de las entradas.

La distinción es importante para los criptógrafos. Imagine un problema computacional que sea fácil de resolver para casi todas las entradas, excepto en algunos casos difíciles en los que falla el mejor algoritmo. La teoría de la complejidad del peor de los casos considera que es un problema difícil, pero para la criptografía es inútil: si solo algunos de sus mensajes son difíciles de descifrar, ¿cuál es el punto?

En realidad, fue Levin quien inició el estudio riguroso de la complejidad del caso promedio, una década después de su trabajo pionero sobre la completitud de NP. En los años intermedios, se había enfrentado a las autoridades soviéticas: era un alborotador irreverente que ocasionalmente socavaría las actividades patrióticas en su grupo juvenil del Partido Comunista. En 1972, se le negó el doctorado por razones explícitamente políticas.

“Para tener éxito en la Unión Soviética como joven investigador, no puedes ser muy obstinado, y es difícil imaginar que Leonid no sea obstinado”, dijo Impagliazzo.

Levin emigró a los Estados Unidos en 1978 y, a mediados de la década de 1980, centró su atención en la complejidad de los casos promedio. Comenzó a trabajar con otros para desarrollar aún más la teoría, incluido Impagliazzo, un estudiante de posgrado en ese momento. Pero incluso a medida que avanzaban, Impagliazzo descubrió que los investigadores a menudo hablaban entre sí. Quería que todos estuvieran en la misma página, y no ayudó que los artículos de Levin fueran famosamente sucintos, el que inició el campo de complejidad de caso promedio tenía menos de dos páginas.

“Iba a hacer una traducción del trabajo de Leonid a términos técnicos más accesibles”, dijo Impagliazzo. Decidió comenzar con una descripción breve y divertida del panorama general antes de sumergirse en las matemáticas. “Eso se apoderó del papel, y es la única parte que alguien recuerda de todos modos”.

El , publicado en 1995, se convirtió en un clásico instantáneo. Impagliazzo acuñó nombres caprichosos para cinco mundos se distinguen por diferentes grados de dureza computacional y diferentes capacidades criptográficas. Vivimos en uno de estos mundos, pero no sabemos cuál.

Desde que apareció el artículo de Impagliazzo, los investigadores han soñado con eliminar partes de su multiverso en miniatura, reduciendo el espacio de posibilidades al demostrar que, después de todo, algunos de los mundos no son posibles. Dos mundos son objetivos especialmente tentadores: aquellos en los que la criptografía es imposible aunque P ≠ NP.

En uno de estos mundos, llamado Heuristica, todos los problemas NP-completos son fáciles de resolver en la mayoría de las entradas, pero los algoritmos rápidos ocasionalmente cometen errores, por lo que estos problemas aún se consideran difíciles según los estándares de la teoría de la complejidad del peor de los casos. Este es el mundo en el que la criptografía es imposible porque casi todos los códigos se descifran fácilmente. En el otro mundo, llamado Pessiland, la criptografía es imposible por una razón diferente: todos los problemas son difíciles en el sentido del caso promedio, pero cifrar un mensaje lo hace ilegible incluso para el destinatario.

Estos dos mundos resultan estar estrechamente vinculados a problemas de metacomplejidad; en particular, el destino de Heuristica está vinculado a la cuestión de larga data de si MCSP es NP-completo. La pregunta que fascinó a Kabanets y desconcertó a Levin hace tanto tiempo no es una mera curiosidad: hay todo un mundo en juego.

Para descartar Heuristica, los investigadores tendrían que colapsar la distinción entre el peor de los casos y la complejidad del caso promedio, es decir, tendrían que demostrar que cualquier algoritmo hipotético que resuelva correctamente un problema NP-completo en la mayoría de las entradas puede realmente resolverlo. en todos los casos. Se sabe que este tipo de conexión, llamada reducción del peor de los casos al caso promedio, existe para ciertos problemas, pero ninguno de ellos es NP-completo, por lo que esos resultados no implican nada más general. La eliminación de Heuristica llevaría a los criptógrafos a medio camino de hacer realidad el sueño del cifrado seguro basado en la única suposición de que P ≠ NP.

Pero destruir un mundo no es poca cosa. En 2003, dos teóricos de la complejidad mostró que los enfoques existentes para probar las reducciones del peor de los casos al caso promedio para problemas NP-completos conocidos implicarían consecuencias extravagantes, lo que sugiere que tales pruebas probablemente no sean posibles.

Los investigadores tendrían que encontrar otro enfoque y ahora creen que MCSP podría ser justo el problema que necesitan. Pero eso no quedaría claro durante más de una década. El primer atisbo de la conexión surgió de la persistente fascinación de Marco Carmosino con la barrera de las pruebas naturales.

Carmosino se encontró por primera vez con la investigación de la metacomplejidad como estudiante de posgrado a través de una papel 2013 por Kabanets y otros cuatro investigadores, que desarrollaron aún más el enfoque de la barrera de las pruebas naturales en el que Kabanets había sido pionero más de una década antes. Solo reforzó su convicción de que aún había más que aprender del artículo clásico de Razborov y Rudich.

“Estaba obsesionado con ese periódico en ese momento”, dijo Carmosino. "Nada ha cambiado."

La obsesión finalmente dio sus frutos durante una visita a un taller de un semestre en la Universidad de California, Berkeley, donde pasó la mayor parte de su tiempo hablando con Impagliazzo, Kabanets y antonina kolokolova, un teórico de la complejidad de la Memorial University of Newfoundland que colaboró ​​con Kabanets en el artículo de 2013. Carmosino ya había trabajado con los tres una vez, y esa exitosa colaboración le dio la confianza para acribillarlos a preguntas sobre el tema que más le apasionaba.

“Estaba molestando a la gente en el buen sentido”, recordó Kabanets.

Al principio, Carmosino tenía nuevas ideas para probar la completitud de NP para la versión de MCSP que había aparecido en el artículo de Razborov y Rudich sobre la barrera de las pruebas naturales. Pero esas ideas no dieron resultado. En cambio, un comentario improvisado de Impagliazzo hizo que los cuatro investigadores se dieran cuenta de que la barrera de las pruebas naturales podría producir algoritmos más potentes de lo que nadie había imaginado: había un mapa secreto grabado en la barricada.

En un papel 2016, los cuatro investigadores demostraron que un cierto tipo de algoritmo MCSP de caso promedio podría usarse para construir un algoritmo del peor de los casos para identificar patrones ocultos en cadenas de dígitos de aspecto aleatorio, una tarea a la que los informáticos se refieren como "aprendizaje". Es un resultado sorprendente porque el aprendizaje intuitivamente parece más difícil que la tarea de clasificación binaria (alta o baja complejidad) realizada por un algoritmo MCSP. Y, sorprendentemente, vinculó la complejidad del peor de los casos de una tarea con la complejidad del caso promedio de la otra.

“No era obvio que tal conexión existiera en absoluto”, dijo Impagliazzo.

Un algoritmo rápido para MCSP es puramente hipotético para circuitos booleanos generales: no puede existir a menos que MCSP resulte ser un problema computacional fácil, a pesar de toda la evidencia en contrario, y eso significa que el algoritmo de aprendizaje implícito en el artículo de los cuatro investigadores es igualmente hipotético.

Pero para algunas versiones más simples de MCSP, que distinguen las tablas de verdad de alta complejidad de las de baja complejidad cuando existen restricciones específicas en los circuitos, los algoritmos rápidos se conocen desde hace muchos años. El artículo de Carmosino, Impagliazzo, Kabanets y Kolokolova mostró que estos algoritmos podrían transformarse en algoritmos de aprendizaje igualmente restringidos pero aún más poderosos que cualquiera que los investigadores hubieran entendido previamente a un nivel teórico tan riguroso.

“De alguna manera, su sabor autorreferencial te permite hacer cosas que aparentemente no puedes hacer con problemas más estándar”, dijo Ilango.

El resultado llamó la atención de los teóricos de la complejidad que trabajan en otros temas. También fue un anticipo de otras conexiones entre la metacomplejidad y la complejidad de casos promedio que surgirían en los próximos años.

Sobre todo, fue un testimonio de hasta dónde pueden llegar los investigadores al hacer preguntas simples sobre las barreras que al principio parecen solo obstruir su progreso.

“Este tipo de dualidad es un tema durante al menos los últimos 30 o 40 años de complejidad”, dijo Impagliazzo. “Los obstáculos son a menudo las oportunidades”.

Credito parcial

El progreso solo se ha acelerado en los años transcurridos desde que Carmosino y sus colegas publicaron su artículo.

“Están sucediendo cosas nuevas”, dijo Kolokolova. “Hay muchos investigadores jóvenes muy, muy brillantes”.

Ilango es uno de estos jóvenes investigadores: en sus primeros tres años de la escuela de posgrado, atacó el desalentador problema abierto de demostrar que MCSP NP-completo usando una estrategia de dos frentes: probar la completitud de NP para más sencillo versiones de MCSP, como hicieron los investigadores de complejidad de circuitos cuando atacaron P versus NP en la década de 1980, al mismo tiempo que demostraban la integridad de NP para versiones más complicadas, que intuitivamente parecen más difíciles y, por lo tanto, quizás sean más fáciles de demostrar.

Ilango atribuye su interés por la metacomplejidad a eric alender, un teórico de la complejidad de la Universidad de Rutgers y uno de los pocos investigadores que continuaron trabajando en la metacomplejidad en la década de 2000 y principios de la de 2010. “Su entusiasmo era contagioso”, dijo Ilango.

Otro joven investigador inspirado por Allender es Shûichi Hirahara, ahora profesor en el Instituto Nacional de Informática en Tokio. Cuando aún era estudiante de posgrado en 2018, Hirahara reveló el verdadero alcance de la relación entre la metacomplejidad y la complejidad del caso promedio que habían descubierto Carmosino y sus coautores. Esos cuatro investigadores habían encontrado una conexión entre la complejidad del caso promedio de un problema, MCSP, y la complejidad del caso peor de otro, el aprendizaje booleano. Hirahara desarrolló sus técnicas más allá de derivar una reducción del peor de los casos al caso promedio para MCSP. Su resultado implica que un hipotético algoritmo MCSP de caso promedio como el que Carmosino y sus colegas habían considerado sería lo suficientemente poderoso como para resolver una versión ligeramente diferente de MCSP sin cometer errores.

El resultado de Hirahara es emocionante porque muchos investigadores sospechan que MCSP es NP-completo, a diferencia de todos los demás problemas para los que se conocen reducciones del peor de los casos al caso promedio. Si pueden extender los resultados de Hirahara para cubrir todos los algoritmos de casos promedio y luego probar que MCSP es NP-completo, eso probaría que no vivimos en Heuristica.

“Eso sería realmente un resultado trascendental”, dijo Santhanam.

Demostrar que MCSP es NP-completo puede parecer una tarea difícil; después de todo, la pregunta ha estado abierta durante más de 50 años. pero después de un ruptura el año pasado por Hirahara, los investigadores ahora están mucho más cerca de lo que nadie hubiera esperado hace unos años.

Hirahara demostró la completitud de NP para una variante del problema llamada MCSP parcial, en la que se ignoran ciertas entradas en cada tabla de verdad. Su prueba se basó en métodos desarrollados por Ilango para mostrar que el MCSP parcial era equivalente a un problema aparentemente no relacionado que involucraba una técnica criptográfica llamada intercambio de secretos. Esta es una forma de dividir un mensaje encriptado entre muchas personas para que solo pueda ser descifrado si una cierta fracción de ellos trabaja en conjunto.

Para cualquier aplicación real en criptografía, querrá saber esa fracción por adelantado, pero con la ayuda de trucos criptográficos adicionales, puede construir un escenario frustrante en el que es difícil averiguar cuántas personas necesitan cooperar. Hirahara encontró una manera de probar que este problema criptográfico artificial era NP-completo y luego mostró que la prueba también implicaba la NP-completitud de MCSP parcial.

Este resultado animó a los investigadores en metacomplejidad incluso más que el trabajo anterior de Hirahara, y otros investigadores también se dieron cuenta: el teórico de la complejidad y bloguero Lance Fortnow lo denominó el resultado del año. Esto se debe a que abordar tales versiones de "función parcial" de los problemas computacionales ha sido un paso intermedio clave en otras pruebas de completitud de NP.

“Es un trabajo increíble”, dijo Williams. “Todos pensaron que estos problemas parciales tenían aproximadamente la misma dificultad que el problema completo”.

Siguen existiendo impedimentos para probar la integridad de NP para la versión completa de MCSP. Pero ninguna es el tipo de barrera que sugiere que se necesita un conjunto de herramientas completamente nuevo; puede ser solo una cuestión de encontrar la forma correcta de combinar técnicas conocidas. Una prueba finalmente establecería el estatus de uno de los pocos problemas que se han resistido a la clasificación desde que existe la teoría de la complejidad. Por correo electrónico, Levin escribió: "Me haría sentir humilde si mostrara que fui estúpido por no haber podido verlo :-)".

las piezas que faltan

MCSP ni siquiera es el único problema de metacomplejidad que ha provocado un gran avance. En 2020, el criptógrafo de Cornell Tech Pase Rafael y su estudiante de posgrado Yanyi Liu descubrió una conexión entre un problema de metacomplejidad diferente y un protocolo criptográfico fundamental que define el límite entre Heuristica y Pessiland, el peor de los mundos de Impagliazzo (donde los problemas NP-completos son difíciles en el sentido del caso promedio pero la criptografía sigue siendo imposible). Eso hace que el problema que estudiaron sea un candidato principal para un asalto a Pessiland, y su trabajo más reciente indica que también podría funcionar contra Heuristica.

“Faltan diferentes piezas del rompecabezas”, dijo Pass. "Para mí, es simplemente mágico que estos campos estén tan íntimamente conectados".

Hirahara advierte que los desafíos aún aguardan a los investigadores que intentan seleccionar los mundos que Impagliazzo conjuró hace 30 años. “Me gustaría decir que en algún momento se descartarán Heuristica y Pessiland, pero no estoy seguro de qué tan cerca estamos”, dijo.

Muchos investigadores esperan que la mayor dificultad sea cerrar una brecha aparentemente inocua entre dos modelos diferentes de complejidad de caso promedio. Los criptógrafos generalmente estudian algoritmos de casos promedio que cometen errores en ambas direcciones, ocasionalmente etiquetando cadenas aleatorias como pseudoaleatorias y viceversa. Mientras tanto, las reducciones del peor caso al caso promedio de Hirahara funcionan para algoritmos del caso promedio que solo cometen el primer tipo de error. Distinciones sutiles como esta pueden marcar una gran diferencia en la teoría de la complejidad. Pero a pesar de este obstáculo y muchos otros, Allender no puede evitar dar una nota de optimismo cauteloso.

“Trato de no ser demasiado creyente porque hay un historial bastante bien establecido de que nada funciona”, dijo. “Pero estamos viendo muchos desarrollos realmente emocionantes: formas de superar cosas que parecían barreras”.

Si hay una lección que los investigadores han aprendido de sus luchas para responder la pregunta P versus NP, o simplemente entenderla, es que la teoría de la complejidad es compleja en sí misma. Pero ese desafío es precisamente lo que hace que la búsqueda sea tan gratificante.

“En realidad es genial que sea tan difícil”, dijo Carmosino. "Nunca me voy a aburrir".

Nota del editor: Scott Aaronson es miembro de Quanta revista, consejo asesor.