Fillmat is NP-Complete and ASP-Complete

• Item type: JInfP(1)
• 公開日: 2015-05-15
• タイトル: Fillmat is NP-Complete and ASP-Complete
• タイトル / 言語: en
• タイトル: Fillmat is NP-Complete and ASP-Complete
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Special Issue of Recreational Discrete Mathematics] computational complexity, NP-completeness, ASP-completeness, pencil-and-paper puzzle, Fillmat
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Osaka Electro-Communication University
• 著者所属: Osaka Electro-Communication University
• 著者所属(英): en
• 著者所属(英): Osaka Electro-Communication University
• 著者所属(英): en
• 著者所属(英): Osaka Electro-Communication University
• 著者名: Uejima, Akihiro; Suzuki, Hiroaki
• 著者名(英): Uejima, Akihiro; Suzuki, Hiroaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We study the computational complexity of a packing puzzle Fillmat, which is a type of pencil-and-paper puzzles made by Japanese puzzle publisher Nikoli. We show that the problem to decide if a given instance of Fillmat has a solution is NP-complete by a reduction from the circuit-satisfiability problem (Circuit-SAT). Our reduction is carefully designed so that we can also prove \textbf{ASP}-completeness of the another-solution-problem.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the computational complexity of a packing puzzle Fillmat, which is a type of pencil-and-paper puzzles made by Japanese puzzle publisher Nikoli. We show that the problem to decide if a given instance of Fillmat has a solution is NP-complete by a reduction from the circuit-satisfiability problem (Circuit-SAT). Our reduction is carefully designed so that we can also prove \textbf{ASP}-completeness of the another-solution-problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 23, 号 3, p. 310-316, 発行日 2015-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会