Hi everyone,

This talk already occurred. Here is the writeup. Notes from the available upon request (send me an email).

Time: 5pm – 7pm, Friday January 24
Location: BA 6183
Speaker: Paul Sacawa
Title: Computational Complexity and Cook-Levin Theorem

Abstract: An introduction to the modelling of computation, computability, connections to incompleteness in logic, time complexity of problems, completeness in the class NP, and a proof of the Cook-Levin theorem. We’ll end by discussing a modern approach to the famous P v. NP problem based in geometry if there’s time.
The whole talk will be very elementary.