MUMS Talk January 24 – Paul Sacawa: “Computational Complexity and the Cook-Levin Theorem”

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.

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>