別解問題の計算量と完全性、およびパズルへの応用

• Item type: SIG Technical Reports(1)
• 公開日: 2002-11-08
• タイトル: 別解問題の計算量と完全性、およびパズルへの応用
• タイトル / 言語: en
• タイトル: Complexity and Completeness of Finding Another Solution and Its Application to Puzzles
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院情報理工学系研究科コンピュータ科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Graduate School of Science, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 八登, 崇之; 瀬田, 剛広
• 著者名(英): Takayuki, Yato; Takahiro, Seta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 問題?に対する別解問題（ASP）というのは、?のインスタンスｘとそれに対する1つの解ｓが与えられた時に、ｘのｓ以外の解を求める問題のことである。（新しい問題クラスとしてのASPの概念はUedaとNagaoによる。）本論文ではｎ個の解が与えられたときにもう1つの解を求める問題（n-ASP）について考察する。特に、対応する解への変換も多項式時間で行えるような多項式時間parsimonious還元に関する完全性であるASP完全性について考察する。応用として、本論文では3つの有名なパズル、スリザーリンクとカックロ（クロスサム）とナンバープレース（数独）についてそのASP換算製（NP完全性を含意する）を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Another Solution Problem (ASP) of a problem II is the following problem: for a given instance x of II and a solution s to it, find a solution to x other than s. (The notion of ASP as a new class of problems was first introduced by Ueda and Nagao.) In this paper we consider n-ASP, the problem to find another solution when n solutions are given. In particular we consider ASP-completeness, the completeness with respect to the parsimonious reductions which allow polynomial-time transformation of solutions. As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 103(2002-AL-087), p. 9-16, 発行日 2002-11-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会