| Item type |
Trans(1) |
| 公開日 |
2023-10-31 |
| タイトル |
|
|
タイトル |
キンコンカンのNP完全性の証明について |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Proof of NP-completeness of Kin-Kon-Kan |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[オリジナル論文] 計算困難性，NP完全，組合せパズルゲーム，キンコンカン |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
静岡県立大学大学院経営情報イノベーション研究科 |
| 著者所属 |
|
|
|
静岡県立大学大学院経営情報イノベーション研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Management and Information of Innovation, University of Shizuoka |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Management and Information of Innovation, University of Shizuoka |
| 著者名 |
福永, 智渉
大久保, 誠也
|
| 著者名(英) |
Chiho, Fukunaga
Seiya, Okubo
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本研究では，組合せパズルゲームの1つである，キンコンカンについて，解の存在判定がNP完全問題であることを証明する．具体的には，NP完全問題であるCircuit SATからの多項式時間帰着を用いて，証明を行う． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
In this study, we prove that the existence determination of a solution is an NP-complete problem for one of the combinatorial puzzles, Kin-Kon-Kan. Specifically, the proof is based on a polynomial-time reduction from Circuit SAT, which is an NP-complete problem. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464803 |
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM）
巻 16,
号 2,
p. 59-66,
発行日 2023-10-31
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7780 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TOM1602007.pdf (632.9 kB)
