関連するゲームとそれらの決定問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/11/21 13:23 UTC 版)
「パリティゲーム」の記事における「関連するゲームとそれらの決定問題」の解説
ここまで述べてきたゲームや、同値なグラフ理論の問題に、ある少しの変更を加えることで、NP困難になる。 具体的には受理条件 (勝利条件) としてラビンの受理条件を採用するとNP困難になる。二部グラフ上の問題として説明すると、これはV0の各頂点から出向辺を1つずつ選ぶことで、どの閉路も(あるいは、どの強連結成分も)ある i について 2i で彩色された頂点を持つが、 2i + 1 で彩色された頂点を持たないようにできるか、という問題といえる。 パリティゲームとは異なり、ラビンの受理条件を採用したゲームはプレイヤー0とプレイヤー1に関して対称ではない。
※この「関連するゲームとそれらの決定問題」の解説は、「パリティゲーム」の解説の一部です。
「関連するゲームとそれらの決定問題」を含む「パリティゲーム」の記事については、「パリティゲーム」の概要を参照ください。
ウィキペディア小見出し辞書の「関連するゲームとそれらの決定問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 関連するゲームとそれらの決定問題のページへのリンク
