El científico ruso Aleksandr Zhulanov ha propuesto un nuevo enfoque para uno de los siete "problemas del milenio": el problema P versus NP. Actualmente, los matemáticos intentan comprender si un problema complejo puede resolverse tan rápidamente como se verifica una respuesta ya preparada. El trabajo de Zhulanov ha sido publicado en la revista científica "Informatsionnye protsessy" del Instituto de Problemas de Transmisión de Información de la Russian Academy of Sciences.
Los "problemas del milenio" son siete problemas matemáticos cruciales formulados por el Clay Mathematics Institute en el año 2000. Se ofrece un premio de 1 millón de dólares por la solución de cada uno de ellos. La lista incluye las hipótesis de Riemann, Hodge y Birch-Swinnerton-Dyer, el problema P versus NP, las ecuaciones de Navier-Stokes, la teoría de Yang-Mills y la conjetura de Poincaré. Esta última fue finalmente demostrada por Grigori Perelman, mientras que las otras seis se consideran oficialmente sin resolver hasta el día de hoy.
El trabajo de Zhulanov se centra en el problema P versus NP y está relacionado con el llamado problema del viajante de comercio simétrico. En este problema, se debe encontrar la ruta cerrada más corta entre puntos dados, de modo que cada punto sea visitado exactamente una vez.
Este problema pertenece a la clase de problemas NP-difíciles. Por lo tanto, la existencia de un algoritmo exacto que resuelva su caso general en tiempo polinomial implicaría la igualdad de P y NP.
El método propuesto por el científico se basa en la modelización dinámica de señales que se propagan simultáneamente desde todos los vértices del grafo. El algoritmo analiza el orden de visita de estos vértices y descarta gradualmente las rutas que no pueden ser las más cortas.
En el IPPI RAN, se enfatiza que la publicación del artículo por sí misma no significa la solución del problema P versus NP. Los especialistas aún deben verificar la prueba matemática, buscar posibles contraejemplos y asegurarse de que el algoritmo funcione correctamente para cualquier dato de entrada válido.
Al mismo tiempo, los resultados ya pueden verificarse de forma independiente. El autor ha proporcionado el código de software que permite a los matemáticos auditar y verificar las características de tiempo declaradas del algoritmo en la práctica.
Si se confirma la validez del método, podría encontrar aplicación en la optimización de redes logísticas complejas, la creación de nuevas moléculas y el desarrollo de sistemas de inteligencia artificial. En particular, según Dmitriy Repin, investigador principal del IPPI RAN, el algoritmo podría potencialmente ayudar a crear una "IA explicable" que cometa menos errores y "alucinaciones" de las redes neuronales.