Colloquium Schedule         Guidelines         Directions        

Thursday, April 3, 2014

The Complexity of Change

Jan van den Heuvel (London School of Economics)

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?

<<< previous talk
next talk >>>

Location :  Room 611 of the Hans Freudenthal building, formerly known as the Wiskunde/Maths building, (campus De Uithof) Budapestlaan 6, Utrecht.
Date and time : Thursday, April 3, 2014 15:30-16:30. The lecture is preceded by coffee, tea, and cookies from 15.00 to 15.30 hour in the same room.