カックロの計算量

• Item type: SIG Technical Reports(1)
• 公開日: 2002-05-23
• タイトル: カックロの計算量
• タイトル / 言語: en
• タイトル: The Complexity of CROSS SUM
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者名: 瀬田, 剛広
• 著者名(英): Seta, Takahiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: パズルの面白さは計算量と関係があり、その多くはNP完全だと予想されている。そこで、その予想を確かめるべく、本論文ではカックロのNP完全性を示した。また、併せて、パズルの作成と関係が深いと思われる、別解問題 (ASP) についても、そのNP完全性を示した。さらに、3個目以降、n個目の解を探す問題について、それが別解問題の別解問題 (ASPのn乗) として表せることを述べ、任意のnについてそのNP完全性が成り立つことを示した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is said that puzzle is interesting for people, because most of them are NP-complete. So, in this paper, first, the NP-completeness of CROSS SUM is proved as an examle to support the idea. Next, the NP-completeness of the Another Solution Problem (ASP), which is very important for designing puzzles, of CROSS SUM is proved. Last, it is pointed out that the problem to determine the existanse of the n-th answer is considered as ASP of ASP (ASP to the n-th), and the NP-completeness of that of CROSS SUM is proved for arbitarary n.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 42(2002-AL-084), p. 51-58, 発行日 2002-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会