Title: My Problem is Harder Than Yours: Complexity Theory for the Combinatorialist
Speaker: Brian Thompson, Rutgers University
Date: Wednesday, November 4, 2009 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
A spaceship lands in the Mathematics Graduate Student Lounge during Pizza Seminar one day. An evil-looking alien hops out and threatens to destroy all of Hill Center next year unless we solve one of two problems:
1) Solve an order-n Sudoku puzzle. 2) Determine whether two graphs on n vertices are isomorphic.
We get to choose the problem, then the alien will give us the hardest example he/she/it can conjure. Which should we choose?
Oddly enough, there's a whole field of theoretical computer science devoted to answering these kinds of questions. We will discuss the idea of reduction, a key concept in Complexity Theory, and use it to compare the relative difficulties of various combinatorial problems.