著者

八登 崇之

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2000, no.84(2000-AL-074), pp.25-31, 2000-09-21

---

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.