Tres experiencias en torno a P vs NP

Resumen:

P vs NP es uno de los 7 problemas del milenio. En esencia P y NP son conjuntos de problemas y P es subconjunto de NP. La pregunta es si la contención es propia o no.  Un problema de decisión es uno cuya respuesta es si o no.  El problema de decidir si una gráfica es conexa o no, o el de decidir si un número es primo o compuesto son ejemplos de problemas que están en P porque existen sendos  algoritmos que en un número de pasos acotado por un polinomio siempre resuelven esos problemas. La existencia de un circuito hamiltoniano en una gráfica dada o la existencia de un factor de determinado tamaño de un número entero dado están en NP porque cuando la respuesta es positiva existe un algoritmo polinomial que nos permite comprobar que la solución propuesta es correcta. Sin embargo, no se sabe si estos problemas están en P o no. Un problema es  NP-completo si esta en NP y todos los demás problemas NP pueden reducirse polinomiálmente a él. La mayor parte de los investigadores  piensan que P ≠ NP.

En esta plática narraré tres experiencias personales relacionadas a este problema. Dos viejas y una nueva y dos teóricas y una práctica.

Unirse a la reunión Zoom
https://vc-cudi.zoom.us/j/86548180010

ID de reunión: 865 4818 0010
Contraseña: 408000

Compartir este seminario