必勝法を探索する問題の困難性による分類
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/03 09:02 UTC 版)
「ゲーム」の記事における「必勝法を探索する問題の困難性による分類」の解説
ゲームの必勝法探索問題それ自身の困難性は、今のところ定義されておらず、ゲームのクラスに対する必勝法探索問題の困難性が定義されている。 ハミルトンゲームはNP完全問題である。(先手後手あわせて)n手で終了するゲームの必勝法を探索する問題は ∑ n P ∪ ∏ n P {\displaystyle \sum _{n}P\cup \prod _{n}P} に属する。 (一般化された)しりとりはPSPACE完全問題である。 尚、二人零和有限確定完全情報ゲームには必勝法があることが知られている。
※この「必勝法を探索する問題の困難性による分類」の解説は、「ゲーム」の解説の一部です。
「必勝法を探索する問題の困難性による分類」を含む「ゲーム」の記事については、「ゲーム」の概要を参照ください。
- 必勝法を探索する問題の困難性による分類のページへのリンク