Square BreakerパズルのNP困難性

• Item type: Symposium(1)
• 公開日: 2002-11-15
• タイトル: Square BreakerパズルのNP困難性
• タイトル / 言語: en
• タイトル: NP-hardness of Square Breaker Puzzle
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): Information Technology Center, University of Tokyo
• 著者名: 田中, 哲朗
• 著者名(英): Tanaka, Tetsuro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Square BreakerはInternational Collegiate Programming Contest（ICPC）2001年アジア予選taejon大会で出題されたマッチ棒を使ったパズルである．この問題は，NP困難であると予想されていたが，証明はされていなかった．本論文ではこの問題がNP困難であることを証明する．証明の結果自体には予想されたことでもありインパクトはないが，証明の過程自体は興味深いと思われる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Square Breaker is a puzzle with matchsticks, which appeared as a problem of International Collegiate Programming Contest (ICPC) Asia regional Taejon in 2001. This problem has been assumed to be a NP-hard problem, but the proof has not been done. In this paper, we show that the problem is NP-hard. Although the result itself has been assumed to be true, the proof process is seemed to be interesting.
• 書誌情報: ゲームプログラミングワークショップ2002論文集; 巻 2002, 号 17, p. 136-139, 発行日 2002-11-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会