Blog de la Biblioteca de Matemàtiques i Informàtica


Deixa un comentari

SIMBa: Computation, Complexity, P-NP (and the fistful of sand that learned how to think)

SIBMa

El proper dimecres, 17 de novembre, se celebrarà una nova xerrada —en format virtual i, alerta, presencial!— del Seminari Informal de Matemàtiques de Barcelona (SIMBa).

Speaker: Javier Villar
Universitat: Universidad de La Rioja

Data: Wednesday, November 17th, 2021.
Hora: 12:00, coffee break; 12:20, talk.
Lloc: Zoom (the link will be posted on our website)
Idioma: English.

Títol: Computation, Complexity, P-NP (and the fistful of sand that learned
how to think)
Resum: Worst-time complexity, Blum’s complexity measures, and the complexity classes derived from them, are some of the most basic tools of modern Computer Science. The theory developed from the problem of classifying computational problems is a rich and popular piece of Math, with many applications to fields like Cryptography or Statistical Physics.
In this presentation we try to give a minimum-prerequisite insight into the current understanding of computability, machine-independent complexity, the P-NP problem and the reasons behind why we haven’t been able to solve it (yet).

 

Si voleu estar al cas de les xerrades previstes, podeu consultar el calendari. Si voleu proposar una xerrada, ompliu el formulari. Si voleu contactar amb els responsables podeu escriure un missatge a seminari(dot)simba(at)ub(dot)edu.