РАЗДЕЛЕНИЕ: Для данного набора натуральных чисел A = {a_1, ..., a_n} существует ли подмножество A с суммой, равной сумме его дополнения?
SUBSET SUM: Учитывая набор положительных целых чисел A = {a_1, ..., a_n} и другое положительное целое число B, существует ли подмножество A такое, что его сумма равна B?
Я пытался доказать, что если PARTITION является NP-полным, то SUBSET SUM также является NP-полным, путем сокращения PART до SSUM.
Мое решение было: пусть A = {a1, ..., an} будет набором натуральных чисел. Затем, если A при подаче в PART дает решение I = {k1, ..., km} (где k_i - индексы членов подмножества решений), то мы строим A '= {a1, ... an, S}, где S - сумма {a_k1, a_k2, ..., a_km}. A '- это решение SSUM.
Моя проблема в том, что это происходит только в одном направлении, а это означает, что мы не можем показать, что если A ', то A является решением PART. Это проблема? и как я могу изменить доказательство, чтобы покрыть его?
