Conferencias

“P vs NP. ¿Qué significa fácil o difícil para un ordenador?”. Café Científico

“P vs NP. ¿Qué significa fácil o difícil para un ordenador?”. Café Científico en Santander
Santander
Lugar. Café de las Artes
Fecha. 27 de febrero de 2015
Hora. 20.30h
Precio. Entrada libre
Evento Familiar

En el año 2000, el Instituto Clay de Matemáticas (Rhode Island) ofreció siete recompensas de un millón de dólares cada una por la resolución de otros tantos problemas matemáticos a los que se denominó "Los problemas del milenio".

Algunos son preguntas muy clásicas, como la Conjetura de Poincaré (resuelta en 2003 por Perelman, quien renunció tanto al millón de dólares como a la medalla Fields) o la Hipótesis de Riemann. Pero uno de ellos resulta un tanto peculiar, el problema de "P versus NP".

Se trata del más reciente de los siete problemas, formulado inicialmente por Stephen Cook en 1971. Su inclusión en la lista sorprendió porque en realidad es un problema más de teoría de la computación que de matemáticas propiamente dicho.

En este Café, Francisco Santos explicará esta pregunta a un público no especializado, así como las ideas básicas de la teoría de la complejidad de algoritmos. Como se indica en el título, el estudio de la complejidad de algoritmos trata de modelizar qué es fácil o difícil para un ordenador. La pregunta de "P versus NP" se puede parafrasear como: ¿de verdad es más difícil resolver algo que comprobar una solución?.

Desde el IFCA, os esperamos en esta nueva sesión de Café Científica para hablar sobre ciencia de una forma amena, cercana y distendida.