Games & Complexity
After the inspiring book by Hearn» and Demaine»:Games, Puzzles, & Computation,
AK. Peters (2009)
IPA Advanced Course on Algorithmics and Complexity
Eindhoven, 8 July 2011
Walter Kosters»
Hendrik Jan Hoogeboom»
1. intro:
Games and complexity classes, constraint logic
2. Gadgets, planarity, exercises
3. Tip-Over is NP-complete
4. Rush Hour is PSPACE complete, plank puzzle
5.
Wrap-up:
other classes of games