0
PARTITION：正の整数の集合A = {a_1、...、a_n}は、補数の和に等しい総和を持つAの部分集合が存在するか？PARTITIONからSUBSET SUMへのKARPの削減
SUBSET SUM：正の整数A = {a_1、...、a_n}と別の正の整数Bの集合を考えると、その和がBに等しいようなAの部分集合が存在しますか？
PARTITIONがNP完全であれば、SUBSET SUMもPARTをSSUMに減らすことでNP完全であることを証明しようとしていました。
私の解決策は次のとおりです。A = {a1、...、an}を正の整数の集合とします。次に、PARTに供給されたときに、A = {k1、...、km}（ここで、k_iは解の部分集合のメンバーのインデックスである）解を与えるならば、A '= {a1、 S}ここで、Sは{a_k1、a_k2、...、a_km}の合計です。 A 'はSSUMの解決策です。
私の問題はこれが単なる方法であるということです。つまり、与えられたA 'とAがPARTの解であることを示すことはできません。これは問題ですか？どのように私はそれをカバーするために証拠を変更することができますか？