Los profesores David Machado y Roberto Mulet, de la Facultad de Física de la Universidad de La Habana, y el estudiante de cuarto año de esa carrera, Jonathan González García, publicaron el artículo “Las ecuaciones locales describen algoritmos estocásticos irrazonablemente eficientes en K-SAT aleatorios” en la prestigiosa revista científica Actas de la Academia Nacional de Ciencias (PNAS, siglas en inglés) de la Academia Nacional de Ciencias estadounidense (NAS).
PNAS es una de las revistas científicas multidisciplinarias más citadas y completas del mundo, con más de 3500 artículos al año. La publicación es reconocida por su estricta revisión por pares y ser una fuente fidedigna de investigación original y de alto impacto, abarcando las ciencias biológicas, físicas y sociales, con alcance global y libre acceso a todos los científicos.
En su trabajo, los investigadores, pertenecientes Centro de Sistemas Complejos y al Departamento de Física Teórica de la Facultad de Física, plantean que “desarrollamos un sistema de ecuaciones maestras aproximadas que capturan el comportamiento de los algoritmos de búsqueda local en problemas de satisfacción de restricciones”.
Pues “el buen rendimiento de ciertos algoritmos en la resolución de tareas complejas de optimización combinatoria sigue siendo poco comprendido. Esta brecha se debe, en gran medida, a la falta de herramientas teóricas para analizar su dinámica fuera de equilibrio”.
En el artículo, editado por el Premio Nobel de Física 2021 Giorgio Parisi, cuyos descubrimientos se encuentran entre las contribuciones más importantes a la teoría de sistemas complejos, los investigadores señalan que los resultados expuestos “desafían la suposición predominante de que las correlaciones de largo alcance siempre son necesarias para describir una dinámica de búsqueda local eficiente, y abren un camino para diseñar algoritmos eficientes para resolver problemas de optimización combinatoria.
“El estudio de los problemas de satisfacibilidad es un área crucial en la frontera entre la complejidad computacional y la física estadística. En particular, el problema aleatorio de K-Satisfacibilidad (K-SAT) ha servido como referencia para estudiar el rendimiento algorítmico y obtener conocimientos fundamentales sobre las transiciones de fase y el comportamiento dinámico de sistemas complejos”.