現実世界の問題を解決する一般的手法のひとつとして，問題を数理的にモデリングし，そのモデルに対して最適化アルゴリズムを適用するという方法がある．このような文脈においては，最適化アルゴリズムはひとつの (近似) 最適解を求めることが一般的である．しかしながら，このような数理的モデルは現実世界を正確には反映できておらず，モデルの上でひとつの最適解を得ても，現実世界の問題の解決につながるとは限らない．（近似）最適解を複数求めて，その中から実問題に適するものを選ぶことが考えられるが，一般にそのような解は類似していることが多く，このような目的にはあまり意味をなさない．このような現実世界の問題と数理モデルとの間のギャップを解消するために，複数の「多様な」解を求める研究が行われている．本講演では，組合せ最適化問題における「多様な解」を発見するための最近の取り組みについて紹介する．

本講演は標的集合と呼ばれるグラフの頂点集合の性質にまつわる遷移問題を扱う．まず，各頂点vに閾値τ(v)の割り当てられたグラフ上で次の決定的な活性化過程を考える：非活性な頂点vは，τ(v)以上の近傍頂点が活性化していたら自身も活性化し，以後非活性化しない．ある頂点集合Sの頂点のみを最初に活性化した時に，最終的に残りの頂点全てが活性化する場合，Sを「標的集合」と呼ぶ．標的集合は適当なτ(v)の下で頂点被覆・フィードバック頂点集合に対応する．また，この活性化過程はネットワーク上のある種の拡散現象を捉えているため，グラフの最小標的集合を見つける最適化問題は，バイラルマーケティングや分散コンピューティング等の動機づけが与えられている．発表者は，標的集合の遷移問題として，ある標的集合から別の標的集合に，標的集合である性質を保ちながらToken Jump操作（頂点を一つずつ交換）の列の適用で遷移できるか否かを問う判定問題を考え，その計算量解析の結果を紹介する．一般の標的集合遷移問題のPSPACE困難性は頂点被覆遷移問題の結果から直ちに示されるため，入力グラフのクラスを制限した時の容易性・困難性を解析する．特に，次数・閾値の制限時にPとPSPACE困難のどちらに属するかの境界線を探索し，また，入力グラフが木の場合に多項式時間で解けることを示す．最後に計算量が未知のクラスを紹介したい．

多くの日本人は，小さい頃，あみだくじを使った記憶があるのではないだろうか．あみだくじは日本人にとって馴染み深いだけでなく，数学ならびに計算機科学において興味深い研究対象として認知されている．本講演では，あみだくじの列挙問題および遷移問題を紹介し，得られた結果を紹介する．はじめに，本講演で扱うあみだくじの定義を与える．続いて，あみだくじの列挙問題に対する結果として，発表者らが設計した列挙アルゴリズムの概要を解説する．このアルゴリズムは，あみだくじのブレイドリレーションという関係を利用することで列挙を行っている．続いて，あみだくじの遷移問題について解説する．2つのあみだくじが与えられたとき，一方のあみだくじからもう一方のあみだくじへ，ブレイドリレーションという関係を繰り返し用いることにより遷移可能かどうか，という遷移問題について，主に，最短の遷移長に関して得られた結果を解説する．

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

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

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

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