In research on theoretical computer science, the research on games and puzzles have been playing important roles. Especially, in the research on computational complexity, giving simple and intuitive complete problems for some complexity classes will bring us new viewpoints and deep understanding of the classes since the characterizations by the Turing machine model are not necessarily easy to capture. 

 

From historical point of view, since there have been given tons of complete problems for the class NP, it is clarified that some common properties of puzzles characterize the class NP. Recently, it becomes to be possible to solve a fairly large-scape NP complete problems in a realistic time. The reasons are not only development of computers and algorithms; such understanding also plays a certain role. 

 

On the other hand, there had been a group of puzzles whose complexities  were unsolved in the last 5 decades. In recent years, it has gradually  become clear that such puzzles can be explained in the framework of combinatorial reconfiguration. Especially, it is interesting that representative puzzles are all PSPACE-complete. Elucidating simple PSPACE complete problems in the framework of combinatorial reconfiguration is expected to improve the understanding of the structure of class PSPACE, and in the future, it will be possible to solve some PSPACE complete problems in a realistic time.

 

I would like to share some interesting open problems that are interesting from the viewpoint of combinatorial reconfiguration.