Event time:
Friday, September 12, 2014 - 8:00am to 10:00am
Location:
201 LOM
Speaker:
Shaken Koplewitz
Speaker affiliation:
Yale University
Event description:
I intend to cover the basics of decidability and computability. I’ll start by defining decidable languages and showing that the halting problem is undecidable, then move on to the problem of P vs NP, and give some examples of NP-complete problems. Finally, if there’s time, I’ll also define the notions of PSPACE- and EXPTIME-completeness.