Presented by: 
Jan van den Heuvel, London School of Economics
Date: 
Tue 26 Jul, 3:00 pm - 4:00 pm
Venue: 
67-442

Abstract:

Many combinatorial puzzles and problems can be formulated as "Can I transform configuration 1 into configuration 2, if certain transformations only are allowed?". An example of such a question is:

given a certain position of the Rubik's Cube, is it possible to go back to the position with all sides of one colour (and without taking the cube apart!)? A more mathematical example is: given two valid assignments of a logical expression, can I transform the first assignment into the second one, by changing the truth value one variable at a time, and always maintaining a solution of the SAT-instance? A final example is: given two k-colourings of a graph, can I transform the first k-colouring into the second one, by recolouring one vertex at a time, and always maintaining a proper k-colouring?

In this talk we shall give an overview of some older and more recent work on this type of problem. The emphasis will be on the computational complexity of the problems: how hard is it to decide if a certain transformation is possible or not?