Mathematics Colloquium: Mike Freedman (Microsoft and UCSB), 'P vs NP'

Event Date: 

Thursday, October 24, 2013 -
3:30pm to 4:30pm

Event Location: 

  • 6635 South Hall

Event Contact: 

Daryl Cooper

Email: cooper@math.ucsb.edu

The title refers to the iconic problem of separating the class of (decision) problems for which we can find solutions quickly from those where it is merely possible to check solutions quickly. For mathematicians this problem asks "Is there really anything to your subject?". For if P=NP it would not be much harder to find proof than to read them. Maybe P vs.NP is undecidable. I'll discuss why some people say the problem is irrelevant. I'll say a little about the little that is known from: diagonalization, oracle reduction, and "natural proofs" and mention a program that exists to solve a related problem ( in algebraic complexity). Then I will tell you my own thoughts, if I have any.