パリティゲーム
ここまで述べてきたゲームや、同値なグラフ理論の問題に、ある少しの変更を加えることで、NP困難になる。 具体的には受理条件 (勝利条件) としてラビンの受理条件を採用するとNP困難になる。二部グラフ上の問題として説明すると、これはV0の各頂点から出向辺を1つずつ選ぶことで、どの閉路も(あるいは、どの強連結成分も)ある i について 2i で彩色された頂点を持つが、 2i + 1 で彩色された頂点を持たないようにできるか、という問題といえる。
パリティゲームとは異なり、ラビンの受理条件を採用したゲームはプレイヤー0とプレイヤー1に関して対称ではない。
有限グラフ上のパリティゲームを解くとは、与えられた初期位置に対して、二人のプレイヤーのうちどちらが必勝戦略を持つか決定することである。この問題はNPかつCo-NP (より強く、UPかつco-UP) であることがわかっている。 また、QP (準多項式時間) であることもわかっている この問題が多項式時間で解けるかどうかは未解決問題である。
パリティゲームが履歴なしの決定性を持っているため、パリティゲームを解く問題は次のような単純げなグラフ理論の問題と同値である: n頂点の有限有向2部グラフ V = V 0 ∪ V 1 {\displaystyle V=V_{0}\cup V_{1}} までの自然数で彩色されたものが与えられる。このとき、 V 0 {\displaystyle V_{0}} の頂点ごとにその頂点から出る辺を一つずつ選び、残りの出向辺を削除することで、得られた部分グラフの任意の閉路の最大優先度が偶数となるようにできるか?