これは論文のあらすじです. 全文を読みたい方は こちらをどうぞ. 本論文の目的 ペグソリティアは古典的なパズルである. ペグソリティアを一般化した問題に 解が存在するかどうかの判定はNP完全問題であり, これを判定するのは非常に 難しい. 本論文ではペグソリティアについての理論, 計算機による解の存在の 判定および解の手順を求める算法について研究する. 本論文の概要 第2章でペグソリティアというパズルを紹介する. 第3章では既存の研究, とく にBerlekamp, Conway, Guyによって提案されたパゴダ関数の理論やその周辺に ついて説明する. 第3章の結果の多くは 菅野による論文で得られたものであり, 線形計画問題が大きな柱となって いる. 第4章では第3章で述べられるジャンプ回数の推定について, より効率的 で精度のよい推定の方法を提案する. ま