パリティゲーム

計算機科学の未解決問題

パリティゲームは多項式時間で解けるか？

有限グラフ上のパリティゲームを解くとは、与えられた初期位置に対して、二人のプレイヤーのうちどちらが必勝戦略を持つか決定することである。この問題はNPかつCo-NP (より強く、UPかつco-UP) であることがわかっている。^[6] また、QP (準多項式時間) であることもわかっている^[7] この問題が多項式時間で解けるかどうかは未解決問題である。

パリティゲームが履歴なしの決定性を持っているため、パリティゲームを解く問題は次のような単純げなグラフ理論の問題と同値である: n頂点の有限有向2部グラフ ${\displaystyle V=V_{0}\cup V_{1}}$までの自然数で彩色されたものが与えられる。このとき、${\displaystyle V_{0}}$の頂点ごとにその頂点から出る辺を一つずつ選び、残りの出向辺を削除することで、得られた部分グラフの任意の閉路の最大優先度が偶数となるようにできるか？

Summarize Timeline Top Qs Fact Check

パリティゲームを解くための再帰的なアルゴリズムが、Zielonkaにより説明されている。 ${\displaystyle G=(V,V_{0},V_{1},E,\Omega )}$をパリティゲームとする。ここで、${\displaystyle V_{0}}$と${\displaystyle V_{1}}$はそれぞれプレイヤー0とプレイヤー1の手番になるノードの集合、${\displaystyle V=V_{0}\cup V_{1}}$ はノード全体の集合、 ${\displaystyle E\subseteq V\times V}$ は辺の集合、 ${\displaystyle \Omega :V\rightarrow \mathbb {N} }$ は優先度を割り当てる関数とする。 Eはtotalであるとする。つまり、どのノードからも1本以上の辺が出ていると仮定する。

Zielonkaのアルゴリズムはアトラクタの概念に基づいている。 ${\displaystyle U\subseteq V}$ をノードの集合とし、 ${\displaystyle i=0,1}$ をプレイヤーの番号とする。Uのi-アトラクタ ${\displaystyle Attr_{i}(U)}$ とは、プレイヤー(1-i)の選択にかかわらず有限回でUに到達するようプレイヤーiが誘導できるようなノードの集合である。これは以下のような不動点計算により定義できる:

${\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}}$

別の言い方をすれば、初期集合 U から開始して、「プレイヤー0の手番となるノードで、 U に一歩で到達できるノード」と「プレイヤー1の手番となるノードで、プレイヤー1がどのように選択しても U に入ってしまうノード」をUに追加していく。これを繰り返して止まったときのUがAttr0(U)である。

Zielonkaのアルゴリズムは、優先度の値に関する再帰降下に基づいている。最大優先度が0のときは、どんな戦略であってもプレイヤー0が勝つのは明らかである。それ以外のときは、 p を最大優先度とし、 ${\displaystyle i=p{\bmod {2}}}$ をその優先度に紐付けられたプレイヤーの番号とする。また、 ${\displaystyle U=\{v\mid \Omega (v)=p\}}$ を優先度が p であるようなノード全体の集合、 ${\displaystyle A=Attr_{i}(U)}$ をプレイヤー i のアトラクタとおく。このとき、プレイヤー i はうまく戦略を選ぶことで、 A を無限回訪問するようなプレイでは必ずプレイヤー i が勝つようにできる。

${\displaystyle G'=G\setminus A}$ を考える。このゲーム ${\displaystyle G'}$ は元のゲームより真に小さいから再帰的に解くことができ、それにより各プレイヤーの勝利領域 ${\displaystyle W'_{i},W'_{1-i}}$ がわかる。ここでもし ${\displaystyle W'_{1-i}}$ が空ならば、元のゲームGの対応する勝利領域${\displaystyle W_{1-i}}$ も空である。なぜならば、プレイヤー ${\displaystyle 1-i}$ が ${\displaystyle W_{i}}$ から抜ける唯一の方法は A に行くことで、この場合もプレイヤー i の勝利が確定するからである。

いっぽう、もし ${\displaystyle W'_{1-i}}$ が空ではなかった場合、プレイヤー ${\displaystyle 1-i}$ は少なくとも ${\displaystyle W'_{1-i}}$ では勝利することができる。なぜならば、プレイヤー i が ${\displaystyle W'_{1-i}}$ から A に逃げることはできない (さもなくば A がアトラクタであることに反する) からである。しかしそれ以外のノードでの必勝性は明らかではないので、プレイヤー ${\displaystyle 1-i}$  のアトラクタ ${\displaystyle B=Attr_{1-i}(W'_{1-i})}$ を計算し、これを G から取り除いた、より小さいゲーム ${\displaystyle G''=G\setminus B}$ を得る。するとやはりこのゲームの必勝性を再帰的に解くことができ、各プレイヤーの勝利領域 ${\displaystyle W''_{i},W''_{1-i}}$ がわかる。このとき ${\displaystyle W_{i}=W''_{i}}$ かつ ${\displaystyle W_{1-i}=W''_{1-i}\cup B}$ であることがわかる。

このアルゴリズムは、擬似コードでは以下のように書ける:

 function ${\displaystyle solve(G)}$
     p := G の最大優先度
     if ${\displaystyle p=0}$
         return ${\displaystyle W_{0},W_{1}:=V,\{\}}$
     else
         U :=  G のノードで優先度 p のもの全体
         ${\displaystyle i:=p{\bmod {2}}}$
         ${\displaystyle A:=Attr_{i}(U)}$
         ${\displaystyle W_{0}',W_{1}':=solve(G\setminus A)}$
         if ${\displaystyle W_{i}'=V}$
              return ${\displaystyle W_{i},W_{1-i}:=V,\{\}}$
         ${\displaystyle B:=Attr_{1-i}(W_{1-i}')}$
         ${\displaystyle W_{0}'',W_{1}'':=solve(G\setminus B)}$
         return ${\displaystyle W_{i},W_{1-i}:=W_{i}'',W_{1-i}''\cup B}$

ここまで述べてきたゲームや、同値なグラフ理論の問題に、ある少しの変更を加えることで、NP困難になる。 具体的には受理条件 (勝利条件) としてラビンの受理条件を採用するとNP困難になる。二部グラフ上の問題として説明すると、これはV₀の各頂点から出向辺を1つずつ選ぶことで、どの閉路も(あるいは、どの強連結成分も)ある i について 2i で彩色された頂点を持つが、 2i + 1 で彩色された頂点を持たないようにできるか、という問題といえる。

パリティゲームとは異なり、ラビンの受理条件を採用したゲームはプレイヤー0とプレイヤー1に関して対称ではない。

パリティゲームは計算複雑性理論の観点からも興味深い一方、パリティゲーム問題を自動検証やコントローラ合成などのバックエンドと位置付けることもできる。 たとえば、様相μ計算に対するモデル検査問題はパリティゲーム問題と同値であることが知られている。様相論理式の妥当性や充足可能性などを決定する問題もまた、パリティゲームに帰着することができる。