The afternoon session saw Ryuhei Uehara (JAIST, Japan) deliverd an ICALP Masterclass on Algorithms and Complexity for Japanese Puzzles. In a very entertaining presentation, Ryuhei took us on a tour of games as a model for computation that started with Conway's Game of Life and Pebble Games and led us to some open problems in the complexity-theoretic analysis of games.
Ryuhei presented his own view on the complexity of games.
- NP-complete puzzles are typically one player puzzles in which "something decreases at each step".
- PSPACE-complete puzzles are two player versions of NP-complete ones.
Finally, Ryuhei discussed the complexity of reconfiguration games, using the 15 puzzle and its generalizations as a motivating example.
The talk was very well attended and entertaining.
The scientific programme for the day closed with the event for the 40th anniversary of TCS, which featured an excellent presentation by Christos Papadimitriou on 40 years of TCS (the field). As usual, Christos delivered an entertaining and thought-provoking talk. I hope to find the time and energy to report briefly on it soon.