Доказательство Н. П. Полноты проблемы разбиения множества

Question

Я уменьшил проблему суммы подмножеств, чтобы установить проблему с разделами, но не знаю, является ли она правильной, и поэтому мне нужна ваша помощь.
МОЙ МЕТОД:
В задаче о сумме подмножества мы должны найти подмножество S1 из множества S, чтобы оно суммировалось с числом t, а в задаче о разбиении множества нам нужно найти подмножество X1 из множества X, такое, что суммирование чисел в множестве X1 составляет половину от X. Итак, давайте возьмем пример задачи суммы подмножеств, где t = сумма чисел в X / 2. Если мы сможем решить проблему разбиения множества, то мы также решили проблему суммы подмножеств. Но мы знаем, что сумма подмножества с идентификатором NP Complete так, что проблема с суммой подмножества также является NP Complete(я знаю, как доказать, что это NP).
Я сомневаюсь, сможем ли мы сделать такой выбор или нет. Пожалуйста помоги.

Answer 1

Ваша логика здорова, это действительное сокращение.

Мы знаем, что это верно, потому что доказательство относится к известной проблеме к неизвестной проблеме. Вам необходимо доказать, что КАЖДЫЙ экземпляр известной проблемы можно превратить в НЕКОТОРЫЙ экземпляр неизвестной проблемы. Таким образом, наложение ограничений на вашу неизвестную проблему вполне приемлемо.

Некоторые примечания: Ваше описание недостаточно для правильного доказательства. Вы отметили, что знали об этом, но для любых читателей здесь: чтобы доказать, что проблема - NP-Complete, вы сначала доказываете, что она в NP, а затем доказываете, что это NP-Hard. Этот вопрос касается только небольшой части того, что должно содержать доказательство NP-Hard.