GLG: The Polynomial Hierarchy by Way of the Traveling Salesman Problem | Department of Mathematics

GLG: The Polynomial Hierarchy by Way of the Traveling Salesman Problem

Event Information
Event Location: 
GAB 473
Event Date: 
Wednesday, October 30, 2019 - 3:45pm

We'll be continuing the discussion of P and NP that we began in the previous talk, and through looking at the travelling salesmen problem find our way towards a generalization of these classes into a natural hierarchy which looks very similar to the arithmetical hierarchy in some ways, but different in others.

I hope to see you all at the talk.