| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-03-04 15:30 初代星のカービィのNP完全性 ○玉山琉弥・山上智幸（福井大）  COMP2025-27 |
|
| 抄録 | （和） | 多くの有名なビデオゲーム，例えば，「スーパーマリオブラザーズ」，「ドンキーコング」，「ゼルダの伝説」， 「ポケットモンスター」，などはゲームの目標を達成することが計算上困難であることが証明されている． 本研究では，任天堂が発売した「カービィ」シリーズに焦点を当てる． 文献では，1996年に発売された「星のカービィ スーパーデラックス」がPSPACE完全であることが示されている． しかし，HAL研究所が開発し，1992年に任天堂がゲームボーイ向けに発売したカービィシリーズの第一作目である「星のカービィ」では， カービィが様々な能力を得ることができる「コピー能力」が実装されていない． 本研究では，「星のカービィ」がNP完全であることを証明した． この困難性の証明は，NP完全問題である3SATへの入力である3CNFブール論理式の本質的部分を制御する様々な装置を構築することで行った． |
| （英） | Many well-known video games, such as Super Mario Bros., Donkey Kong, The Legend of Zelda, and Pokémon, have been proven to be computationally hard to solve with respect to achieving their game objectives. In this paper, we focus on the Kirby series developed and published by Nintendo. Previous work has shown that Kirby Super Star, released in 1996, is PSPACE-complete. However, the first title in the series, Kirby's Dream Land, developed by HAL Laboratory and released for the Game Boy in 1992, does not include the copy ability system that allows Kirby to acquire various abilities. We prove that Kirby's Dream Land is NP-complete. The hardness proof proceeds by constructing various gadgets that control the essential components of a 3CNF Boolean formula, which is an instance of the NP-complete problem 3SAT. |
|
| キーワード | （和） | 任天堂 / 星のカービィ / NP完全 / PSPACE / / / / |
| （英） | Nintendo / Kirby's Dream Land / NP-complete / PSPACE / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 390, COMP2025-27, pp. 38-44, 2026年3月. | |
| 資料番号 | COMP2025-27 | |
| 発行日 | 2026-02-25 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-27 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2026-03-04 - 2026-03-04 |
| 開催地（和） | 中央大学後楽園キャンパス 6号館4階6402 |
| 開催地（英） | Chuo University Korakuen Campus Building 6 4F Room 6402 |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, General |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2026-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 初代星のカービィのNP完全性 |
| サブタイトル（和） | |
| タイトル（英） | Kirby's Dream Land is NP-complete |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 任天堂 / Nintendo |
| キーワード(2)（和/英） | 星のカービィ / Kirby's Dream Land |
| キーワード(3)（和/英） | NP完全 / NP-complete |
| キーワード(4)（和/英） | PSPACE / PSPACE |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 玉山 琉弥 / Ryuya Tamayama / タマヤマ リュウヤ |
| 第1著者 所属（和/英） | 福井大学 (略称： 福井大) University of Fukui (略称： Univ. of Fukui) |
| 第2著者 氏名（和/英/ヨミ） | 山上 智幸 / Tomoyuki Yamakami / ヤマカミ トモユキ |
| 第2著者 所属（和/英） | 福井大学 工学系部門 工学領域 情報・メディア工学講座 (略称： 福井大) University of Fukui Faculty of EngineeringDivision of Engineering Information (略称： Univ. of Fukui) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-03-04 15:30:00 |
| 発表時間 | 20分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-27 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.390 |
| ページ範囲 | pp.38-44 |
| ページ数 | 7 |
| 発行日 | 2026-02-25 (COMP) |
[研究会発表申込システムのトップページに戻る]