WEKO3
アイテム
Fillmat is NP-Complete and ASP-Complete
https://ipsj.ixsq.nii.ac.jp/records/142073
https://ipsj.ixsq.nii.ac.jp/records/1420732060d91d-8c53-40f8-b3d1-a128e9139023
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5605013 (2.0 MB)
|
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-05-15 | |||||||||
| タイトル | ||||||||||
| タイトル | Fillmat is NP-Complete and ASP-Complete | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Fillmat is NP-Complete and ASP-Complete | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [特集：娯楽の離散数理] 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
× Uejima, Akihiro
× Suzuki, Hiroaki
|
|||||||||
| 著者名(英) |
Uejima, Akihiro
× 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.23.310 ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.23.310 ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116647 | |||||||||
| 書誌情報 |
情報処理学会論文誌 巻 56, 号 5, 発行日 2015-05-15 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7764 | |||||||||
