[img_inline align=”right” src=”http://padnws01.mcmaster.ca/images/PitassiPic.jpg” caption=”Toniann Pitassi “]Suppose you are a salesperson who has an expense account of $1,000 and you are told you have to visit three cities and return home. Given that the cost of getting from one city to the next is known, are you able to do this? The answer, yes or no, is probably easy to figure out in this case. Suppose you have to visit 30 cities and have $10,000. Things start to get a little more complicated. You might want to enlist an expert – someone who, given any number of cities and a fixed cost could tell you, in a reasonable length of time, if such an itinerary is possible. Does such an expert exist? It turns out that this is equivalent to one of the biggest open problems in mathematics today which goes by the name P vs. NP – the Clay Mathematics Institute made this one of their millennium problems and offers one million dollars US for its solution.

This week, McMaster's Department of Mathematics and Statistics will host Toniann Pitassi from the University of Toronto who is one of the world's leading experts in computational complexity theory, the branch of mathematics in which the problem P vs. NP resides. She will give the annual Britton Lectures, a series of four lectures, on Propositional Proof Complexity (more details can be found at www.math.mcmaster.ca/talks/britton_lectures.php). In particular, her talk on Wednesday at 2:30 in HH 217 will be devoted to the current status of the problem P vs. NP.

Pitassi has published more than 60 research articles and has given many prestigious lectures including an invited lecture at the 1998 International Congress of Mathematicians. She has held positions at the University of California at San Diego, the University of Pittsburg, the University of Arizona, MIT, the Institute of Advanced Studies and the Fields Institute. She is currently a professor in the Computer Science department at the University of Toronto.