Verónica Becher es investigadora principal de CONICET en el ICC y directora de KAPOW, un grupo de teoría de la computación con foco en problemas combinatorios y aleatoriedad. Recientemente fue designada editora asociada del Journal of Complexity, una prestigiosa publicación internacional que se enmarca en la complejidad desde un punto de vista matemático y computacional. En esta nota nos cuenta sobre los desafíos de edición en la revista y algunas de las dificultades teóricas que surgen a la hora de resolver problemas complejos.

La complejidad computacional es un concepto fundamental en informática que cuantifica  los recursos necesarios para resolver problemas computacionales. Claramente en computación científica, investigar los aspectos teóricos de la complejidad computacional resulta crucial para desarrollar algoritmos eficientes y escalables.

En este caso la complejidad temporal mide qué tan rápido puede ejecutarse un algoritmo, mientras que la complejidad espacial mide cuánta memoria necesita un algoritmo. A veces, se puede mejorar uno a expensas del otro, pero no siempre. Por ejemplo, una tabla hash acelera la búsqueda de un elemento en una matriz, pero también consumirá más memoria.  

Medidas de la complejidad computacional

La compleijidad de objetos matemático-computacionales es una función tal que a cada objeto le asigna un valor numérico.  

Por ejemplo, una medida de complejidad de polinomios es el grado del polinomio. Otra medida de complejidad es la altura (o magnitud) de sus coeficientes. Luego tenemos problemas definidos sobre esos objetos, por ejemplo evaluar un polinomio, sumar dos polinomios, derivar un polinomio, etc. En definitiva, la complejidad de estos problemas se expresa en función de la complejidad de la entrada.

En este contexto, la revista Journal of Complexity -fundada en 1985 por Joseph F. Traub- publica artículos de investigación originales que contienen resultados matemáticos sustanciales sobre la complejidad y los sistemas complejos en su concepción amplia. Es la revista de mayor impacto en el área de la complejidad computacional y su enfoque se centra en la complejidad sobre los números reales, con énfasis en los cotas inferiores y algoritmos óptimos.

Y el año pasado la doctora Verónica Becher fue designada editora asociada, en complemento con su amplia tarea de edición en diversas revistas de matemática y computación teórica. Uno de los propósitos de esta revista es poder encontrar estas joyas matemáticas que se denominan “algoritmos óptimos”, aquellos que resuelven problemas o ecuaciones en el menor tiempo posible, con el menor costo posible, y donde existe una demostración matemática de que no puede haber un algoritmo mejor.

“Una cota inferior de complejidad indica que todo algoritmo que resuelva el problema necesitará al menos la cantidad de tiempo indicado por la cota, expresado como una función del tamaño de la entrada. Y existen también las cotas superiores de complejidad, que es una función que describe el comportamiento del peor caso de un algoritmo, es decir predice el peor escenario posible de un algoritmo”, explica la investigadora y profesora Veronica Becher. Y existe lo que se llama “complejidad promedio”, que es lo que más interesa en la vida real: “Si viene una entrada que no sabes de qué tipo va a ser, ¿a cuánto apostás? ¿Cómo se distribuye la complejidad sobre tu problema? Y esos son los temas que le interesa a esta revista”.

Supongamos que debemos calcular el tiempo óptimo que nos lleva viajar en auto a Mar del Plata: sabemos que lleva al menos 2 horas, pero existen algoritmos que nos llevan en 3 horas. El problema es, ¿existe alguna solución real entre 2 horas y 3? Entonces encontrar ese punto entre la cota inferior y los mejores resultados hasta el momento es muy difícil. ¿Cómo se consigue dar resultados óptimos? Cuando la cota inferior coincide con la instancia que uno tiene, dando cotas inferiores cada vez más cercanas al óptimo.  

Esas soluciones se tienen que demostrar matemáticamente. Y si un investigador determina esa medida de complejidad, ese costo de recursos para resolver un problema le tiene que dar una distribución de que la mayoría de las instancias del problema son complejas y muy pocas son simples. 

Si bien los artículos científicos de esta área son muy específicos y la investigadora recibe del editor en jefe (Erich Novak) unos pocos trabajos por mes para evaluar, la tarea le resulta demandante, considerando que el rango de temas es muy amplio de indagar ya que es complejidad en todas las posibles áreas. “No sólo tengo que sumergirme en el tema desde cero sino tratar de dialogar con los principales referentes o pioneros en la temática”, comenta entusiasmada Becher.

Y aclara que si bien tradicionalmente el Journal of Complexity se ocupa del mundo continuo (números reales, funciones sobre números reales, ecuaciones diferenciales), “me incorporaron para ampliar el conjunto editorial y darle mi impronta respecto a mi trabajo en el mundo discreto (números naturales, símbolos, grafos) con una aplicación al mundo continuo”, detalla.

Becher destaca que a nivel local, quien impulsó la complejidad matemática y computacional en el mundo continuo y tuvo un enorme protagonismo en el área fue Joos Heintz, doctor en filosofía con orientación matemática, profesor titular y emérito en Exactas e investigador superior del CONICET,  tanto en matemáticas como en computación. Motivado por su idea de integrar la matemática con temas netamente computacionales, sus contribuciones en complejidad computacional para resolver problemas de geometría algebraica fueron muy profundas (ver recuadro).

“El hecho de formar parte de esta  revista de alto impacto, se lo debo principalmente a Joos, quien, entre varios logros de su trayectoria, se convirtió en especialista en cotas inferiores de complejidad para resolver ecuaciones polinomiales y obtuvo dos premios en esta revista. Fue una persona brillante. Y poder continuar con ese legado me llena de orgullo”, comenta emocionada Becher, quien fue una de sus discípulas.    

Algoritmos óptimos: la búsqueda binaria y los autómatas finitos

Encontrar estos algoritmos óptimos en el mundo real no es nada sencillo. Pero aún así se pueden lograr algunas aproximaciones que permitan comprender cómo estos problemas netamente teóricos se conectan con aplicaciones actuales de la informática.

“Esos algoritmos óptimos son extraordinarios y para eso realmente estudiamos e investigamos en computación. Siempre les remarco a nuestros estudiantes que tenemos la responsabilidad de que cada vez que hay un algoritmo óptimo debemos usarlo”, plantea la investigadora.

En este sentido, Becher remarca algunos ejemplos sumamente interesantes:

1) La búsqueda binaria: supongamos que tenemos que encontrar el apellido Sadosky en el padrón de electores para una votación. Encontrar la palabra en la lista dada, que sabemos que está ordenada alfabéticamente, tiene complejidad temporal de peor caso del orden de logarítmico en el tamaño de la lista ya que el árbol de decisión del problema tiene una altura logarítmica en el tamaño de la lista (para distinguir entre cada una de las posibles entradas).  

2) Los autómatas finitos son las máquinas más sencillas de aceptación de secuencias finitas. Computan en tiempo lineal en el tamaño de la entrada. Se usan para muchísimas aplicaciones. Por ejemplo, la asistente virtual Siri incluye una composición de autómatas finitos que leen y escriben (transductores finitos), los cuales realizan el reconocimiento de voz: las señales de voz que recibe del usuario se codifican en símbolos que se van traduciendo a un código intermedio y de ese código a otro código intermedio, hasta que finalmente le queda una representación interna en palabras de la pregunta o la afirmación que se le hizo. Es una máquina muy sencilla que tarda tantos pasos como la cantidad de símbolos de entrada. Por lo tanto, el cómputo tiene complejidad temporal lineal en el tamaño de la entrada.

El resurgimiento de la computación analógica 

Continuando con lo anterior, si bien estamos acostumbrados a la máquina de Turing, esta línea de investigación retoma La Máquina Analógica de Propósito General (The General Purpose Analog Computer de Claude Shannon).  Esos modelos de cómputo trabajan usando números reales, en vez de números naturales. Se trata de máquinas analógicas que existían mucho antes que las máquinas discretas. Desde el punto de vista matemático estas máquinas son sistemas de ecuaciones diferenciales ordinarias.

Si bien la teoría es de 1930, se demoró más de siete décadas en demostrar: alcanza con considerar solamente a las ecuaciones diferenciales ordinarias polinomiales. Y el hecho de que las máquinas analógicas computan en tiempo polinomial corresponde a los sistemas de  ecuaciones diferenciales ordinarias polinomiales, de longitud polinomial. Estos resultan teoremas importantes demostrados por Bournez, Graça y Pouly (2017, 2020).

 

Representación del chip de computación analógica de la Universidad de Tsinghua. Crédito: Universidad de Tsinghua.

Los algoritmos que computan en tiempo polinomial se llaman algoritmos tratables y contrastan con algoritmos de tiempo exponencial, que se vuelven intratables rápidamente a medida que aumenta el tamaño de la entrada (un tiempo que para los humanos no es posible, suele abordarse con paralelismo masivo y tal vez pueda abordarse con máquinas cuánticas).

Dra. Verónica Becher. Crédito fotográfico: Silvio Fabrykant

Según Becher, a partir de la caracterización de la clase polinomial de las máquinas analógicas, podemos pensar que van a ser parte del plantel computacional.  “Por ejemplo, son las señales de audio donde la habitual discretización requiere energía (y pierde algo de información). En cambio, al incorporar en cualquier autómata discreto, sea una computadora o un celular, un dispositivo más pequeño que pueda sensar las señales directamente, evita el gasto de energía que hubiera requerido discretizar las ecuaciones”, concluye.

Estos son algunos de los problemas de interés que fundamentalmente demuestran que la teoría matemática-computacional en torno a la complejidad se conecta con usos prácticos y desarrollos de la tecnología de vanguardia actual.

En homenaje a Joos Heintz

Joos Heintz nació el 27 de octubre de 1945 y falleció el 3 de octubre de 2024. Heintz nació en Zúrich, Suiza, donde pasó su infancia y juventud. Se formó como lingüista (turcología) y matemático en la Universidad de Zurich. En la misma universidad hizo su doctorado en Filosofía con orientación matemática, con la dirección de Volker Strassen. Hizo su Habilitación en Ciencias Matemáticas con Venia Lengendi, en la Facultad de Matemáticas de la Universidad J.W. von Goethe, Frankfurt/Main. A mediados de la década de 1980, por decisión personal, se mudó a Argentina y se nacionalizó argentino. Fue profesor de la Universidad de Buenos Aires e investigador superior del CONICET y al mismo tiempo ejerció como profesor titular en Cantabria (España) donde pasaba una parte del año. Joos Heintz combinó su labor científica con un fuerte compromiso social,  siendo especialmente significativa su incisiva dedicación al colectivo de los cartoneros de Buenos Aires.

Fue una figura heterodoxa en el ámbito matemático. Sus contribuciones matemáticas se inspiraron en su vasta formación sociológica y cultural, así como en sus extraordinarias habilidades políglotas, lo que le confirió un aura de innovación científica inclasificable. Heintz afirmaba creer en la ciencia como producto del esfuerzo colectivo de científicos comprometidos y, en consonancia con esta creencia, solía publicar con coautores y, ocasionalmente, bajo seudónimos colectivos como Noaï Fitchas o D. Franck Le Plateau. En consecuencia, su extraordinaria personalidad le permitió atraer a jóvenes talentosos a su universo científico. Legó una impresionante escuela científica argentina e influyó notablemente en grupos de investigación de París, Berlín y Cantabria, entre otros.

El perfil del Dr. Heintz tiene carácter excepcional por su creatividad para atravesar problemas profundos de la matemática y la computación. Su obra contiene contribuciones de tipo fundamental en áreas de la matemática (pura y aplicada) y de la computación (teórica y práctica), principalmente en geometría algebraica, en computación simbólica y seminumérica, y en complejidad algebraica.

Sus aportes en geometría algebraica son claves para la resolución de sistemas polinomiales sobre los números complejos y reales. En el campo de la computación teórica Joos Heintz fue pionero en el uso de circuitos como estructuras de datos y es una autoridad indiscutida en técnicas de cotas inferiores de complejidad para la evaluación de polinomios.