Hablando de Matemáticas son ciclos de conferencias panorámicas que tienen el propósito de presentar áreas de las matemáticas que son de interés actual.

Los ciclos son organizados por la Facultad de Ciencias y el Instituto de Matemáticas de la UNAM en Ciudad Universitaria desde 2014 y tienen como objetivo aumentar la cultura matemática entre estudiantes de licenciatura.

Cada conferencia tiene como propósito explicar los problemas principales y los temas que trata un área.

  

Sigue la transmisión por Facebook Live en:

@HablandoDeMatematicas

https://www.facebook.com/HablandoDeMatematicas 

 

 

  

 

  29 de abril de 2021, 16:00 horas

"NP-Completitud: encontrar soluciones vs. verificarlas, ¿por qué suelen tener dificultades tan diferentes?”

David Flores / Facultad de Ciencias de la UNAM

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.  .

 

Go to top

Tenemos 48 visitantes y ningun miembro en Línea