¿Cuál es la mejor manera de resolver problemas difíciles? Ésa es la pregunta central de un subcampo de la informática llamado teoría de la complejidad computacional. Es una pregunta difícil de responder, pero si le damos la vuelta se vuelve más fácil. El peor enfoque casi siempre es el de prueba y error, que implica ir incorporando posibles soluciones hasta que una funciona. Pero para algunos problemas, parece que simplemente no hay alternativas: el peor enfoque es también el mejor.

Los investigadores se han preguntado durante mucho tiempo si ese es realmente el caso, dijo raul ilango, un estudiante de posgrado que estudia teoría de la complejidad en el Instituto de Tecnología de Massachusetts. “Se podría preguntar: '¿Hay problemas para los cuales adivinar y verificar es óptimo?'”

Los teóricos de la complejidad han estudiado muchos problemas computacionales, e incluso los más difíciles a menudo admiten algún tipo de procedimiento o algoritmo inteligente que hace que encontrar una solución sea un poco más fácil que el puro ensayo y error. Entre las pocas excepciones se encuentran los llamados problemas de compresión, donde el objetivo es encontrar la descripción más corta de un conjunto de datos.

Pero el pasado mes de noviembre, dos grupos de investigadores independientemente descubierto CRISPR Otro algoritmo para problemas de compresión, uno que es ligeramente más rápido que verificar todas las respuestas posibles. El nuevo enfoque funciona adaptando un algoritmo inventado por criptógrafos hace 25 años para atacar un problema diferente. Solo hay una restricción: debes adaptar el algoritmo al tamaño de tu conjunto de datos.

"Son resultados realmente hermosos e importantes", dijo eric alender, científico informático teórico de la Universidad de Rutgers.

Definición de dureza

Los nuevos resultados son los últimos en investigar una cuestión que se estudió por primera vez en la Unión Soviética, mucho antes del advenimiento de la teoría de la complejidad. “Antes de que yo estuviera en la escuela primaria, la gente en Rusia formulaba esto”, dijo Allender.

El problema computacional específico que estudiaron esos investigadores soviéticos, llamado problema del tamaño mínimo de circuito, es similar al que enfrentan los diseñadores de hardware informático todo el tiempo. Si le dan especificaciones completas sobre cómo debe comportarse un circuito electrónico, ¿puede encontrar el circuito más simple que haga el trabajo? Nadie sabía cómo resolver este problema sin "perebor", una palabra rusa que equivale aproximadamente a "búsqueda exhaustiva".

El problema del tamaño mínimo del circuito es un ejemplo de problema de compresión. Se puede describir el comportamiento de un circuito con una larga cadena de bits (ceros y unos) y luego preguntar si hay alguna forma de reproducir ese mismo comportamiento utilizando menos bits. Verificar todos los diseños de circuitos posibles llevaría un tiempo que crece exponencialmente con el número de bits de la cadena.

Este tipo de crecimiento exponencial es la característica definitoria de un problema computacional difícil. Pero no todos los problemas difíciles son igualmente difíciles: algunos tienen algoritmos que son más rápidos que la búsqueda exhaustiva, aunque sus tiempos de ejecución siguen creciendo exponencialmente. En términos modernos, la pregunta perebor es si existen algoritmos de este tipo para problemas de compresión.

En 1959, un destacado investigador llamado Sergey Yablonsky afirmó haber demostrado que la búsqueda exhaustiva era realmente la única forma de resolver el problema del tamaño mínimo de circuito. Pero su prueba dejó algunas lagunas. Algunos investigadores notaron las fallas en ese momento, pero Yablonsky fue lo suficientemente influyente como para disuadir a la mayoría de los demás de trabajar en la cuestión del perebor.

En las décadas siguientes, pocos investigadores estudiaron los problemas de compresión, y la cuestión de Perebor se conoció principalmente como una nota a pie de página en la prehistoria de la teoría de la complejidad. La atención generalizada a la cuestión llegó recientemente, después de que los investigadores descubrieran un vínculo curioso entre los problemas de compresión y los fundamentos de la criptografía.

Un solo sentido

La criptografía moderna utiliza complejos problemas computacionales para salvaguardar los mensajes secretos. Pero la dureza computacional sólo es útil si es asimétrica: si es difícil descifrar mensajes codificados pero, en primer lugar, no es difícil codificar mensajes.

En todo esquema de criptografía, el origen de esta asimetría es un objeto matemático llamado función unidireccional, que transforma cadenas de bits de entrada en cadenas de salida de la misma longitud. Dada una entrada para una función unidireccional, es fácil calcular la salida, pero dada una salida es difícil invertir la función, es decir, aplicar ingeniería inversa y recuperar la entrada.

“A los criptógrafos realmente les gustaría tener funciones unidireccionales computables de manera muy, muy eficiente y que sean realmente difíciles de invertir”, dijo Allender. Muchas funciones matemáticas parecen tener esta propiedad, y la dificultad de invertir estas funciones surge de la aparente dificultad de resolver diferentes problemas computacionales.

Desafortunadamente, los criptógrafos no saben con certeza si alguna de estas funciones es realmente difícil de invertir; de hecho, es posible que no existan verdaderas funciones unidireccionales. Esta incertidumbre persiste porque los teóricos de la complejidad han luchó durante 50 años para demostrar que los problemas aparentemente difíciles realmente lo son. Si no es así, y si los investigadores descubren algoritmos súper rápidos para estos problemas, sería desastroso para la criptografía, similar a desviar repentinamente a los autos a alta velocidad en ambas direcciones en una calle de un solo sentido.

Aunque sigue siendo difícil lograr una comprensión integral de la dureza computacional, recientemente los criptógrafos han logrado avances interesantes hacia una teoría unificada de funciones unidireccionales. En 2020 se dio un gran paso cuando el criptógrafo de la Universidad de Tel Aviv Pase Rafael y su estudiante de posgrado Yanyi Liu demostró que las funciones unidireccionales son íntimamente conectado a un problema de compresión específico llamado problema de complejidad de Kolmogorov con límite de tiempo.

Si ese problema realmente es difícil de resolver para la mayoría de las entradas, entonces el resultado de Pass y Liu produce una receta sobre cómo construir una función unidireccional demostrablemente difícil, una que garantiza su seguridad incluso si otros problemas computacionales resultan mucho más fáciles. de lo que esperaban los investigadores. Pero si existe un algoritmo rápido para resolver el problema de complejidad temporal de Kolmogorov, entonces la criptografía está condenada al fracaso y cualquier función puede invertirse fácilmente. Una función unidireccional basada en la dureza de este problema es la función más segura posible: una función unidireccional para gobernarlos a todos.

Construyendo sobre estructuras de datos

El descubrimiento de Pass y Liu fue el último capítulo de una larga línea de investigación que utiliza la teoría de la complejidad para comprender mejor los fundamentos de la criptografía. Pero también sugirió una forma de invertir esa relación: la equivalencia entre el problema de complejidad de Kolmogorov con límite de tiempo y la inversión de funciones implica que las ideas sobre cualquiera de los problemas pueden revelar más sobre el otro. Los criptógrafos llevan décadas estudiando algoritmos de inversión de funciones para comprender mejor los puntos débiles de sus métodos de cifrado. Los investigadores comenzaron a preguntarse si esos algoritmos podrían ayudar a responder preguntas antiguas de la teoría de la complejidad.

Como muchos problemas computacionales, la inversión de funciones se puede resolver mediante una búsqueda exhaustiva. Dada una cadena de salida, simplemente conecte todas las entradas posibles a la función hasta que encuentre la que produzca la respuesta correcta.

En 1980, el criptógrafo Martin Hellman comenzó a estudiar si era posible hacerlo mejor: la misma pregunta que los matemáticos soviéticos habían hecho décadas antes sobre los problemas de compresión. Demonios, hombre descubierto CRISPR Eso sí, es posible, siempre y cuando estés dispuesto a trabajar un poco más por adelantado, utilizando objetos matemáticos llamados estructuras de datos.

Una estructura de datos es esencialmente una tabla que almacena información sobre la función que se va a invertir, y construir una requiere calcular las salidas de la función para ciertas entradas estratégicamente elegidas. Todos esos cálculos "podrían llevar mucho tiempo", dijo Ryan Williams, teórico de la complejidad del MIT. “Pero la idea es que esto se haga de una vez por todas”. Si está intentando invertir la misma función dadas muchas salidas diferentes (por ejemplo, para decodificar muchos mensajes diferentes cifrados de la misma manera), puede que valga la pena hacer este trabajo por adelantado.

Por supuesto, almacenar esa información adicional requiere espacio, así que lleve esta estrategia al extremo y podría terminar con un programa rápido que no cabe en ninguna computadora. Hellman diseñó una estructura de datos inteligente que permitió a su algoritmo invertir la mayoría de las funciones un poco más rápido que una búsqueda exhaustiva sin ocupar mucho más espacio. Luego, en el año 2000, los criptógrafos Amos Fiat y Moni Naor extendido Argumentos de Hellman para todas las funciones.

Después del avance de Pass y Liu en 2020, estos viejos resultados de repente cobraron relevancia. El algoritmo Fiat-Naor podría invertir funciones arbitrarias más rápido que una búsqueda exhaustiva. ¿Podría funcionar también para problemas de compresión?

Sin uniforme

Los primeros investigadores que plantearon la cuestión fueron los teóricos de la complejidad. Raúl Santhanam de la Universidad de Oxford y su estudiante de posgrado Hanlin Ren. Lo hicieron en un papel 2021 demostrando que los problemas de compresión y la inversión de funciones estaban aún más entrelazados de lo que los investigadores habían pensado.

Pass y Liu habían demostrado que si el problema de complejidad de Kolmogorov con límite de tiempo es difícil, entonces la inversión de funciones también debe serlo, y viceversa. Pero los problemas pueden ser difíciles y aun así admitir soluciones que son un poco mejores que una búsqueda exhaustiva. Santhanam y Ren demostraron que existe una estrecha conexión entre si se requiere una búsqueda exhaustiva para un problema y si se requiere para el otro.

Su resultado tuvo diferentes implicaciones para dos amplias clases de algoritmos que los investigadores suelen estudiar, llamados algoritmos "uniformes" y "no uniformes". Los algoritmos uniformes siguen el mismo procedimiento para cada entrada: un programa uniforme para ordenar listas de números, por ejemplo, funcionará de la misma manera ya sea que haya 20 entradas en la lista o 20,000. En cambio, los algoritmos no uniformes utilizan diferentes procedimientos para entradas de diferente longitud.

Las estructuras de datos utilizadas por el algoritmo Fiat-Naor siempre se adaptan a una función específica. Para invertir una función que codifica una cadena de 10 bits, necesita una estructura de datos diferente de la que necesitaría para invertir una función que codifica una cadena de 20 bits, incluso si la codificación se realiza de manera similar. Eso convierte a Fiat-Naor en un algoritmo no uniforme.

El resultado de Santhanam y Ren sugirió que podría ser posible transformar el algoritmo Fiat-Naor en un algoritmo para resolver problemas de compresión. Pero adaptar el algoritmo de un problema a otro no fue sencillo y no continuaron con la cuestión.

A Pass se le ocurrió la misma idea un año después, después de escuchar a Fiat dar una charla sobre el algoritmo clásico en un taller que celebraba las contribuciones de Naor a la criptografía. "Esta idea de utilizar la inversión de funciones había estado en mi mente desde entonces", dijo. Más tarde comenzó a trabajar seriamente en el problema con el investigador de la Universidad de Tel Aviv. Noam Mazor.

Mientras tanto, Ilango se inspiró para atacar el problema después de conversaciones con otros investigadores, incluido Santhanam, durante una visita al Instituto Simons de Teoría de la Computación en Berkeley, California. "Surgió de una de esas conversaciones fortuitas en las que simplemente estás tirando cosas", dijo Santhanam. Posteriormente Ilango unió fuerzas con Williams y Shûichi Hirahara, teórico de la complejidad del Instituto Nacional de Informática de Tokio.

La parte difícil fue descubrir cómo integrar la estructura de datos en el corazón del algoritmo Fiat-Naor en un algoritmo no uniforme para resolver problemas de compresión. Existe un procedimiento estándar para realizar ese tipo de incrustación, pero ralentizaría el algoritmo, eliminando su ventaja sobre la búsqueda exhaustiva. Los dos equipos encontraron formas más inteligentes de incorporar la estructura de datos de Fiat-Naor y obtuvieron algoritmos para problemas de compresión que funcionaban en todas las entradas y eran más rápidos que una búsqueda exhaustiva.

Los detalles de los dos algoritmos difieren ligeramente. El de Ilango y sus coautores es más rápido que la búsqueda exhaustiva incluso si se restringe la búsqueda a las posibilidades más simples, y se aplica a todos los problemas de compresión: la complejidad de Kolmogorov con límite de tiempo, el problema del tamaño mínimo del circuito y muchos otros. Pero la idea central era la misma para ambos algoritmos. Las técnicas de la criptografía habían demostrado su eficacia en este nuevo ámbito.

Convergencia de inversión

La nueva prueba de algoritmos no uniformes plantea una pregunta natural: ¿qué pasa con los algoritmos uniformes? ¿Existe alguna manera de resolver los problemas de compresión más rápido que una búsqueda exhaustiva usándolos?

La reciente serie de resultados implica que cualquier algoritmo de este tipo sería equivalente a un algoritmo uniforme para invertir funciones arbitrarias, algo que los criptógrafos han buscado sin éxito durante décadas. Por eso, muchos investigadores consideran que esta posibilidad es poco probable.

“Me sorprendería mucho”, dijo Santhanam. "Se necesitaría una idea completamente nueva".

Pero Allender dijo que los investigadores no deberían descartar la posibilidad. "Para mí, una buena hipótesis de trabajo ha sido que si hay una forma no uniforme de hacer algo, es muy probable que exista una manera uniforme", afirmó.

De cualquier manera, el trabajo ha hecho que los teóricos de la complejidad se interesen recientemente en viejas cuestiones de la criptografía. yuval ishai, un criptógrafo del Technion en Haifa, Israel, dijo que eso es lo que lo hace más emocionante.

"Estoy muy feliz de ver esta convergencia de intereses entre diferentes comunidades", dijo. "Creo que es fantástico para la ciencia".