Imagine que está buscando comprender la naturaleza misma de la computación. Estás en lo profundo del desierto, lejos de cualquier camino, y inescrutable la vida están tallados en los troncos de los árboles que te rodean — BPP, AC⁰[m], Σ₂P, YACC y cientos de otros. Los glifos intentan decirte algo, pero ¿por dónde empezar? Ni siquiera puedes mantenerlos todos en orden.

Pocos investigadores han hecho tanto russell impagliazzo para atravesar este aparente caos. Durante 40 años, Impagliazzo ha trabajado a la vanguardia de la teoría de la complejidad computacional, el estudio de la dificultad intrínseca de diferentes problemas. La pregunta abierta más famosa en este campo, llamada problema P versus NP, pregunta si muchos problemas computacionales aparentemente difíciles son en realidad fáciles, con el algoritmo correcto. Una respuesta tendría implicaciones de gran alcance para la ciencia y la seguridad de la criptografía moderna.

En las décadas de 1980 y 1990, Impagliazzo desempeñó un papel destacado en la unificación de la fundamentos teóricos de la criptografía. En 1995, articuló la importancia de estos nuevos desarrollos en un artículo icónico que reformuló posibles soluciones a P versus NP y un puñado de problemas relacionados en el lenguaje de cinco mundos hipotéticos podríamos habitar, caprichosamente denominadas Algorithmica, Heuristica, Pessiland, Minicrypt y Cryptomania. Los cinco mundos de Impagliazzo han inspirado a una generación de investigadores y continúan guiando la investigación en el floreciente subcampo de la metacomplejidad.

Y estos no son los únicos mundos que ha soñado. Impagliazzo ha sido un aficionado de toda la vida a los juegos de rol de mesa como Dungeons and Dragons, y le encanta inventar nuevos conjuntos de reglas y nuevos escenarios para explorar. El mismo espíritu lúdico anima su práctica de 30 años de comedia de improvisación.

Impagliazzo también realizó un trabajo fundamental al dilucidar el papel fundamental de la aleatoriedad en la computación. A finales de los años 1970, los científicos informáticos descubrieron que la aleatoriedad a veces podía mejorar los algoritmos para resolver problemas inherentemente deterministas, un hallazgo contradictorio que dejó perplejos a los investigadores durante años. El trabajo de Impagliazzo con el teórico de la complejidad. Avi Wigderson y otros investigadores en la década de 1990 demostraron que si ciertos problemas computacionales realmente son fundamentalmente difíciles, entonces es siempre posible convertir algoritmos que utilizan la aleatoriedad en algoritmos deterministas. Y a la inversa, demostrar que la aleatoriedad se puede eliminar de cualquier algoritmo. también probaría que existen problemas verdaderamente difíciles.

¿Cuánto habló con Impagliazzo sobre la diferencia entre problemas difíciles y acertijos difíciles, consulta de oráculos y las lecciones matemáticas de la comedia de improvisación. La entrevista ha sido condensada y editada para mayor claridad.

¿Cuándo se interesó por primera vez en las matemáticas?

Me interesaban las matemáticas incluso antes de saber realmente qué eran. En tercer grado, mis calificaciones en matemáticas comenzaron a bajar porque se suponía que debíamos memorizar las tablas de multiplicar y me negué. Mi madre dijo: "Pero Russell, te encantan las matemáticas, ¿por qué no haces esto?". Y dije: “Eso no es matemática, es memorización. Las verdaderas matemáticas no implican memorización”. Todo lo que había aprendido en ese momento era aritmética, así que no estoy seguro de dónde saqué la idea de que las matemáticas se trataban de conceptos abstractos.

¿Qué pasa con la informática? Algunas partes del campo son muy abstractas, pero no son lo que la mayoría de la gente encuentra por primera vez.

En la escuela secundaria, había tomado un curso de programación en BASIC, pero era muy difícil hacer algo. Los programas tenían que transferirse a cintas de papel, que tenían que ejecutarse a través de esta computadora muy antigua que a menudo fallaba y rompía el papel por la mitad. Entonces pensé que la informática era terriblemente aburrida.

Tenía la intención de estudiar lógica. Pero muchos de los conceptos, cuando se intentaba formalizarlos, implicaban computación y, especialmente, límites a la computación. Preguntas como "¿Cómo sabemos que las cosas en matemáticas son ciertas?" y “¿Cómo entendemos la dificultad de hacer matemáticas?” condujo a la informática teórica y especialmente a la teoría de la complejidad.

Algunos de sus trabajos más famosos exploran las conexiones entre la criptografía y la teoría de la complejidad computacional. ¿Por qué están relacionados esos dos campos?

Cuando configura un sistema criptográfico, necesita distinguir entre usuarios legítimos (las personas a las que desea otorgar acceso) y todos los demás. Los problemas computacionalmente difíciles nos brindan una manera de distinguir estos grupos en función de lo que saben. Pero si quieres que saber la respuesta a un problema sea una forma de distinguir dos grupos de personas, no puedes simplemente utilizar cualquier problema difícil: necesitas un acertijo difícil.

¿Cuál es la diferencia entre un problema y un rompecabezas?

En general, es posible que la persona que plantea un problema no sepa la respuesta. Un rompecabezas es un problema diseñado con una respuesta en mente. Entonces, ¿por qué necesitamos un rompecabezas? Porque necesitamos poder determinar si una persona que supuestamente lo resolvió realmente lo hizo. En la vida cotidiana utilizamos rompecabezas para divertirnos, pero también los utilizamos en las aulas para comprobar si la gente ha entendido el material. Esto es lo que sucede en criptografía: utilizamos acertijos para probar el conocimiento de alguien.

La diferencia entre los cinco mundos es cómo responden a las preguntas "¿Existen problemas difíciles?" y "¿Hay acertijos difíciles?"

¿Cómo se desarrollan esas diferentes respuestas?

En el primer mundo, Algorithmica, ningún problema es difícil. No es necesario que sepas cómo alguien diseñó tu problema: siempre puedes resolverlo. La heurística dice: "Bueno, tal vez algunos problemas sean difíciles". Luego llegamos a Pessiland, donde muchos problemas son difíciles, pero la mayoría de los acertijos no lo son. Casi cualquier problema que invente y del que conozca la solución, tú también podrás resolverlo. Todos estos mundos son malos para la criptografía.

En Minicrypt, puedo crear acertijos que sé cómo resolver y que siguen siendo realmente desafiantes para ti. Y finalmente, Cryptomania es un mundo en el que dos personas pueden estar en un lugar público donde un espía puede escuchar y juntos crear un rompecabezas que aún es difícil para el espía.

¿Qué te motivó a escribir el artículo de los cinco mundos?

En ese momento, se sabía que diferentes respuestas a la pregunta P versus NP tendrían un gran impacto en qué tipo de problemas podemos resolver y también qué tipo de seguridad podemos esperar, pero las distinciones cualitativas entre diferentes formas de facilidad y La dureza no estaba muy clara.

Unos años antes, hubo un artículo muy revelador que establecía las distinciones utilizando muchas preguntas interrelacionadas con alrededor de 20 respuestas posibles. Una de las razones por las que quise escribir el artículo de los cinco mundos fue que habíamos logrado un gran progreso en esos pocos años. Habría sido difícil encontrar nombres para 20 mundos posibles.

Entonces, ¿por qué plantearlo de esa manera, como mundos diferentes con nombres extravagantes?

Había aceptado escribir este artículo para una conferencia. Me quedé despierto hasta tarde en la noche tratando de descubrir qué iba a decir, y alrededor de la 1 am, enmarcar los diferentes mundos me pareció una buena idea. Y luego lo leí a la mañana siguiente y todavía me parecía una buena idea: era una manera de mostrar cómo estas ideas realmente influirían en el mundo sin quedar atrapado en detalles cuantitativos. Lo que me hace más feliz de este artículo es que escucho de personas que realizan investigaciones en complejidad que este fue el artículo que los hizo interesarse en el campo como estudiantes universitarios.

¿Han descartado los investigadores alguno de los cinco mundos posibles?

De hecho, estamos agregando más; la gente ha comenzado a hablar sobre Ofustopía como un mundo de herramientas criptográficas aún más potentes. Es un poco deprimente que hayamos progresado tanto a finales de los años 1980 y no hayamos eliminado ningún mundo desde entonces. Pero, por otro lado, sabemos mucho más sobre las conexiones entre mundos y tenemos una imagen mucho más clara de cómo sería cada mundo.

Los mundos hipotéticos también desempeñan otro papel en la teoría de la complejidad, en pruebas que suponen la existencia de "oráculos". Entonces, antes que nada, ¿qué es exactamente un oráculo?

Imaginemos que alguien construye un dispositivo ingenioso que puede resolver algún problema sin que conozcamos un algoritmo para resolverlo. Eso es lo que es un oráculo. Si tuviéramos un dispositivo tan milagroso y lo pusiéramos dentro de nuestras computadoras, podría cambiar la línea entre lo que es computable y lo que no es computable.

¿Creen los investigadores que estas cajas mágicas realmente podrían existir?

No, probablemente no existan. Al principio, los resultados de Oracle fueron algo controvertidos porque son muy hipotéticos. Pero una forma en que pueden ser muy esclarecedores es cuando se utiliza el oráculo para modelar una situación ideal. Digamos que estás tratando de demostrar que A no necesariamente implica B. Comienzas con el escenario donde tienes el A más extremo y demuestras que eso aún no es suficiente para garantizar B. Si puedes demostrar que incluso si todas las probabilidades son a tu favor todavía no puedes probar algo, esa es una evidencia realmente fuerte que va a ser difícil de probar.

También ha descubierto vínculos entre la dureza computacional y la aleatoriedad. ¿Cómo funciona esa conexión?

En realidad, es una forma de decir que si no entiendes algo, puede parecer aleatorio. Supongamos que digo que estoy pensando en un número entre uno y mil. Si elijo el número al azar, tienes una probabilidad entre mil de adivinarlo. Y si pregunto (siguiendo a Monty Python) “En millas por hora, ¿cuál es la velocidad promedio de una golondrina europea?” tienes aproximadamente las mismas posibilidades. Probablemente vaya a más de una milla por hora, y probablemente no vaya a más de mil millas por hora.

En realidad, esto no es aleatorio: es una pregunta que puede responderse de manera determinista. Podríamos simplemente medir todas las golondrinas que vuelan, pero es un poco difícil de determinar con recursos limitados, como no tener un presupuesto para medir la velocidad de las golondrinas y no tener un suministro infinito de golondrinas.

Así que la idea es que los problemas difíciles cuyas soluciones desconocemos pueden proporcionar una fuente de números "pseudoaleatorios" que parecen aleatorios.

Hablando de Monty Python, sé que llevas mucho tiempo haciendo comedia de improvisación. ¿Cómo empezaste?

Comencé como profesor asistente en San Diego en 1991. Y alrededor del 94, más o menos, pensé: "Realmente no tengo mucha vida fuera del departamento". Así que conseguí el periódico semanal gratuito y revisé la lista de clubes y actividades. Eliminé todo excepto la comedia de improvisación; pensé que al menos era plausible que lo hiciera bien. Conocí a mi esposa en esa clase para principiantes.

¿Qué pensaba ella?

Ella dice que fui realmente horrible. Cuando eres lógico, estás capacitado para pensar siempre en los matices de cada palabra. No querrás decir algo incorrecto. La improvisación es excelente porque invierte eso: el punto no es decir algo perfecto sino inventar algo rápidamente. Fue lo contrario del resto de mi vida.

Mi ahora esposa se tomó un descanso de la clase y, cuando regresó un año después, logré impresionarla. Eso fue hace 30 años. Sigo tomando la misma clase con el mismo instructor.

¿La improvisación ha cambiado la forma en que abordas tu investigación?

Es una buena práctica para no ser hipercrítico con cada pensamiento que tengas. Esto es especialmente útil en colaboraciones. Cuando trabajaba con otras personas, solía decir cosas como: “Pero esa idea no funcionará por la siguiente razón. Eso no es literalmente cierto”. En la improvisación, se supone que siempre debes aceptar lo que dice tu compañero. Y creo que es una buena actitud, especialmente cuando investigas con estudiantes: no descartes algo que digan solo porque sabes que es incorrecto. Hay muchas buenas ideas que no son 100% correctas.

¿Como que?

Cuando intentas obtener intuición para un problema, una cosa que ayuda es comenzar con algunas suposiciones simplificadoras. Por lo general, esas suposiciones no son ciertas, pero pueden ayudarle a elaborar una hoja de ruta. Diga: “Si tuviera un elefante, podría cruzar las montañas. Por supuesto, no tengo un elefante. Pero si lo hiciera, así es como lo haría”. Y luego te das cuenta: “Bueno, tal vez no necesito un elefante para este paso. Una mula estaría bien”.

¿Qué pasa con tu amor por los juegos de rol? ¿Eso ha influido en tu trabajo?

Puede que no haya influido en toda mi investigación, pero ciertamente sí influyó en mi artículo de los cinco mundos. Siempre he tenido un interés general por la fantasía y la ciencia ficción y por idear diferentes mundos posibles: ¿cómo serían las cosas si todo fuera diferente?

¿Por qué los juegos de rol son una forma tan atractiva de explorar mundos hipotéticos?

La gente a la que le gusta la ficción especulativa siempre ha inventado mundos. Tolkien es más famoso por eso, y tenía una imaginación tan enorme que realmente parecía habitado en su mundo. Para aquellos de nosotros que no somos tan imaginativos, la mejor manera de lograrlo es invitar a personas a su entorno y un juego. es una forma de hacerlo. Ahora no es sólo mi mundo. Puede que haya comenzado como lo imaginé, pero como en cualquier colaboración, gracias a las contribuciones de todos los demás, ha evolucionado mucho más allá de eso.