DIMACS - Graduate Student Combinatorics Seminar

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.