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

Question

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

Answer 1

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

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

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