理論計算機科学の研究の中で，ゲームやパズルの研究は重要な役割を果たしてきた．特に計算量クラスの研究において，チューリング機械による特徴付けは必ずしもわかりやすいものではなく，特定の計算量クラスに対して直観的にわかりやすい単純な完全問題を示すことは，その計算量クラスに対する新たな視点と本質的な理解をもたらしてくれる．

　歴史的に見れば，特にクラスNPに関する完全問題が数多く示されたことにより，ある種のパズルの特徴がクラスNPを特徴づけていることが明らかになってきた．近年のコンピュータの発達とアルゴリズムの発展により，かなり大規模なNP完全問題が現実的な時間で解けるようになってきた背景には，こうした理解が進んだことも一定の役割を果たしているだろう．

　一方，歴史の中で50年近くも困難性が未解決だったパズルの一群が存在する．近年，こうしたパズルが組合せ遷移の枠組みで説明できることが徐々にわかってきた．特に，典型的なパズルがどれもPSPACE完全性を示していることは興味深い．組合せ遷移問題の枠組みでPSPACE完全性をもつ単純な問題を解明していくことは，クラスPSPACEの構造の理解が進展することが期待され，今後，ある程度のPSPACE完全問題を現実的な時間で解けるようになる．

　最後にいくつかの組合せ遷移の観点から興味深い未解決問題をいくつか共有したい．