Título: "NP-Completitud: encontrar soluciones vs. verificarlas, ¿por qué suelen tener dificultades tan diferentes?”
David Flores / Facultad de Ciencias de la UNAM
29 de abril de 2021, 16:00 horas
Resumen:
¿Qué es más difícil, escribir una demostración de un teorema; o verificarla?, ¿dado un listado de parejas de amigos, encontrar 10 personas que son todos amigos entre sí; o dadas 10 personas y la lista, verificar que en efecto todos son amigos entre sí?, ¿dado un entero compuesto, factorizarlo en dos enteros; o dados dos enteros, calcular su producto?
Este fenómeno de que, “encontrar una solución a un problema”, es mucho más difícil que “verificar que una solución propuesta sí es de hecho una solución”, ocurre de forma muy frecuente en problemas cotidianos del mundo real y del digital. La teoría de la NP-Completitud formaliza y estudia esta asimetría de dificultades. Nos permite, entre otras cosas, exhibir la “dificultad” inherente en problemas que sabemos que son resolubles, pero que no podemos encontrar formas “eficientes” de resolver. A cincuenta años de su inicio, esta teoría fundamenta a varias áreas pilares de la tecnología, incluyendo criptografía y optimización combinatoria.
En esta plática veremos una muy breve introducción a la teoría de la NP-Completitud, algunos de sus resultados y problemas más importantes, y ejemplos de resultados de “dificultad intrínseca” en algunos problemas de geometría y de videojuegos, recientemente obtenidos en colaboración con dos de mis estudiantes de maestría. .
Temas: