[Todos CMAT] Coloquio de Estudiantes

[Joaquin Lema]

Estimados.

Este jueves 12 a las *18:15 hs* en el 14 vamos a escuchar a *Leandro
Bentancur*, abajo va el título y resúmen.

Los esperamos!

======================================================

*P vs NP*

El objetivo de la charla es contar qué es el problema P versus NP, el cual
es uno de los problemas más importantes de las ciencias de la computación y
uno de los problemas del milenio propuestos por el Instituto Clay de
Matemáticas.
Comenzaremos presentando qué es la complejidad computacional, viendo la
relación entre los recursos necesarios (tiempo y espacio) para resolver un
problema y el tamaño del input. Luego definiremos las clases P y NP,
veremos qué precisamos y qué implica que estos dos conjuntos sean iguales o
distintos, también definiremos la clase NP-completa y el papel que juega.
Para terminar, vamos a hablar brevemente sobre qué son las máquinas de
Turing deterministas y no deterministas para ver un poco cómo se formaliza
el asunto.

======================================================
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.cmat.edu.uy/pipermail/todos/attachments/20171010/c9b5042f/attachment.html>