El Problema del Milenio PvsNP: Problemas NP-duros de pelotas con Python. (Sesión II)

Prof. Antonio Ramírez de Arellano Marrero

Prof. Andrés Nicolás Uranga Limón

D. Miguel España Montero

Datos de la ponencia
Martes, 11 de febrero de 2025
15:00
ETSII - US. H1.12
Resumen de la ponencia

El problema PvsNP, el problema no resuelto más importante de las ciencias de la computación y uno de los más importantes de las matemáticas. Tal es así que, en el año 2000, el instituto Clay lo enunció como uno de los 7 Problemas del Milenio, ofreciendo un millón de dólares a quien lo resuelva. En estas dos sesiones, introduciremos el fantástico mundo de la teoría de la complejidad computacional enfocándonos en el problema PvsNP y el camino clásico para atacarlo: la NP-Completitud. En la segunda sesión, nos centraremos en la demostración de problemas NP-Completos mostrando una implementación en Python de estos problemas además de sus "reducciones" a otros problemas de la misma clase. Por último, mostraremos representaciones mediante grafos de las instancias a estos problemas con el uso de la librería NetworkX.