部分MAXSATは, MAXSATを一般化した組合せ最適化問題であり, スケジュール問題等の現実社会に則した組合せ最適化問題を模倣する能力を持っている. また, 部分MAXSATは, 項の重みづけを施すことにより, 従来のMAXSATアルゴリズムを用いて, 効率良く解けることが実験によって示されている. このように, 部分MAXSATは有用な問題であるが, どのような問題を模倣することができるかを理論的に明らかにする必要がある. 本論文では, 部分MAXSATの組合せ最適化問題のクラスでの完全性を示す. また, 他の組合せ最適化問題に対応する部分最適化問題の完全性も示す.