8面，20面ダイスを用いたRolling Dice PuzzleのNP完全性

摘要

本論文では,格子盤面上でダイスを回転移動させることで,ある目的を達成できるかを問うRolling Cube Puzzleを拡張した問題について,その計算複雑さを議論する.6面ダイスと四角格子で定義されるRolling Cube PuzzleのNP完全性は既に証明されており,その先行研究において多角格子上での他の正多面体ダイスに関する未解決問題が提示されている.本論文では,その未解決問題の中から特に,正八面体及び正二十面体ダイスを三角格子上で回転移動させる問題について,既存結果の証明手法に倣い,それらのNP完全性を証明する.