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

Talk given on Wednesday, 17th of November of 2021. Abstract: 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). Poster of the talk: https://www.ub.edu/simba/posters/simba211117_1220.pdf ========================================================= SIMBa Seminar website: http://www.ub.edu/simba Subscribe to the SIMBa Seminar mailing list: http://eepurl.com/gMkuv Do you want to give a talk? https://goo.gl/1TcwQR