「タイル返し」のPSPACE完全性

• Item type: SIG Technical Reports(1)
• 公開日: 2022-11-10
• タイトル: 「タイル返し」のPSPACE完全性
• タイトル / 言語: en
• タイトル: Turning Tiles is PSPACE-complete
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学
• 著者所属: 九州大学
• 著者所属: 国立情報学研究所
• 著者所属: 九州大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Nagoya university
• 著者所属(英): en
• 著者所属(英): Kyushu university
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Kyushu university
• 著者所属(英): en
• 著者所属(英): Nagoya university
• 著者名: 吉渡, 叶; 木谷, 裕紀; 末續, 鴻輝; 土中, 哲秀; 小野, 廣隆
• 著者名(英): Kanae, Yoshiwatari; Hironori, Kiya; Koki, Suetsugu; Tesshu, Hanaka; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 組合せゲーム理論では，正規形ゲームにおける必勝戦略の有無の関係を代数的な演算系とみなす形での解析・特徴づけがなされている．そのような解析では各局面に対して値（局面値）を定義する．あるゲーム（のルールセット）が任意の局面値をとりうるとき，全象的であるという．全象性はゲームの複雑さを表す 1 つの指標であるが，同じく複雑さの指標である計算量クラスとの関係は明らかではない．本研究では，全象的なゲーム「タイル返し」についてその必勝判定が PSPACE 完全であることを証明する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each position, called a game value. A game (rule set) is called universal if any game value is achievable in some position in a play. Although the universality of a game implies that the game is sufficiently complex, it does not necessarily imply that the game is intractable in the sense of computational complexity. This paper proves that the universal game Turning Tiles is PSPACE-complete.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-190, 号 21, p. 1-5, 発行日 2022-11-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会