Как я могу уменьшить сумму подмножества до раздела?

Может быть, это довольно просто, но у меня есть некоторые проблемы, чтобы получить это сокращение. Я хочу уменьшить Subset Sum до Partition, но в настоящее время я не вижу связи!

Можно ли уменьшить эту проблему с помощью редукции Левина?

Если не понимаешь, пиши для уточнения!

Пусть будет экземпляром суммы подмножеств, где - это список (мультимножество) чисел, а - целевая сумма. Пусть . Пусть будет список сформирован путем добавления к .L B S = ∑ L L ′ S + B , 2 S - B $(L,B)$$L$$B$$S = \sum L$$L'$$S+B,2S-B$$L$

(1) Если существует подсписок суммирующий , то можно разбить на две равные части: и . Действительно, первая часть суммируется с , а вторая с .B L ′ M ∪ { 2 S - B } L ∖ M ∪ { S + B } B + ( 2 S - B ) = 2 S ( S - B ) + ( S + B ) = 2 $M \subseteq L$$B$$L'$$M \cup \{ 2S-B \}$$L\setminus M \cup \{ S+B \}$$B+(2S-B) = 2S$$(S-B)+(S+B) = 2S$

(2) Если может быть разделен на две равные части , то есть подсписок суммирования до . Действительно, поскольку и каждая часть суммируется с , эти два элемента принадлежат разным частям. Без потери общности, . Остальные элементы в принадлежат к и сумму к .P 1 , P 2 L B ( S + B ) + ( 2 S - B ) = 3 S 2 S 2 S - B ∈ P 1 P 1 L $L'$$P_1,P_2$$L$$B$$(S+B)+(2S-B) = 3S$$2S$$2S-B \in P_1$$P_1$$L$$B$

Ответ, упомянутый @Yuval Filmus, неверен (он верен ТОЛЬКО, если нет целых отрицательных чисел). Рассмотрим следующий мультимножество:

и целевая сумма . Мы знаем, что нет подмножества. Теперь мы создадим экземпляр для проблемы с разделами. Добавлены два новых элемента: и . Теперь мультимножество: а общая сумма равна .2 σ - t = 12 σ + t = 3 { - 5 , 2 , 2 , 2 , 2 , 2 , 3 , 12 } $-2$$2\sigma-t = 12$$\sigma+t = 3$

Проблема разбиения решает ответ, дающий подмножество Здесь 2 новых элемента находятся в одном подмножестве (другого способа разбить на половину суммы нет). Следовательно, это контрпример. Правильный ответ таков:

Добавьте элемент со значением . Общая сумма мультимножества теперь составляет . Решите проблему разбиения, которая даст 2 подмножества суммы . Только один раздел будет содержать новый элемент. Мы выбираем другое разбиение с суммой и мы решили проблему подмножества, сведя его к проблеме разбиения. Это то, что объясняет ссылка .2 т т $2t-\sigma$$2t$$t$$t$

Вот прямое доказательство:

Легко видеть, что SET-PARTITION может быть проверен за полиномиальное время; учитывая разбиение $P_1,P_2$ просто суммируем два и проверяем, что их суммы равны друг другу, что, очевидно, является проверкой за полиномиальное время (поскольку суммирование является полиномиальной операцией, и мы выполняем только самое большее $|X|$ много суммирований).

Суть доказательства в том, чтобы свести SUBSETSUM к PARTITION; с этой целью, учитывая множество $X$ и значение $t$ (запрос суммы подмножеств), мы формируем новое множество $X'=X \cup \{s-2t\}$ где $s=\sum_{x \in X}x$ . Чтобы увидеть, что это сокращение:

• ($\implies$) предположим, что существует некоторый $S \subset X$ такой, что $t=\sum_{x \in S}x$ тогда мы имеем, что

  $$\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$$ $$\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$$ и мы бы получили, что $S\cup \{ s-2t \}$ и$X' \setminus( S\cup \{s-2t\})$ образуют разбиение$X'$

• ($\impliedby$) Предположим, что существует разбиение $P_1',P_2'$ в $X'$ такое, что $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$ . Обратите внимание, что это индуцирует естественное разбиение $P_1$ и $P_2$ в $X$ такое, что WLOG имеет, что

  $$\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$$ $$\begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$$

Следовательно , из раствора $t=\sum_{x \in S}x$ можно образовать parition $P_1 =S\cup \{ s-2t \}$ , $P_2=X' \setminus( S\cup \{s-2t\})$ и , наоборот , из раздела $P_1',P_2'$ мы можем сформировать решение $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$иследовательноотображение$f:(X,t)\rightarrow X'$ является уменьшение (потому что$(X,t)$находится в языке / множества SUBSETSUM$\Leftrightarrow X'=f(X,t)$является на языке / set PARTITION) и ясно видно, что преобразование было сделано за полиномиальное время.

Сумма подмножества:

Ввод: {a1, a2, ..., am} st M = {1..m} и ai - неотрицательное целое число, а S⊆ {1..k} и Σai (i∈S) = t

Раздел:

Ввод: {a1, a2, ..., am} и S⊆ {1, · · ·, m} st Σai (i∈S) = Σaj (j∉S)

Partition Np Proof: если средство проверки предоставляет разделы (P1, P2) для верификатора, верификатор может легко вычислить сумму P1 и P2 и проверить, равен ли результат 0 за линейное время.

NP_Hard: SubsetSum ≤p PARTITION

Пусть x будет входом SubsetSum и x = 〈a1, a2, ..., am, t〉 и Σai (i от 1 до m) = a

Case1: 2t> = a:

Пусть f (x) = 〈a1, a2, ..., am, am + 1〉, где am + 1 = 2t − a

Мы хотим показать, что x∈SubsetSum ⇔ f (x) ∈PARTITION

поэтому существуют S⊆ {1, ..., m} st T = {1..m} - S и Σai (i∈T) = at

и пусть T '= {1 ... m, m + 1} - S, поэтому Σaj (j∈T') = a-t + 2t-a = t

который точно Σai (i∈S) = t и показывает f (x) ∈PARTITION

Теперь мы также покажем, что f (x) ∈PARTITION ⇔ x∈SubsetSum

поэтому существуют S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S и Σai (i∈T) = [a + (2t-a ) -t] = т

и он показывает Σai (i∈T) = Σaj (j∈S), поэтому m + 1∈T и S⊆ {1, · · ·, m} и Σai (i∈S) = t

так x∈SubsetSum

Случай 2: 2t = <a :

мы можем проверить то же самое, но только в этот раз я + 1 является -2т

эта ссылка имеет хорошее описание как сокращений, разделение на подмножество-сумма и подмножество-сумма на разделение. Я думаю, что это более очевидно, чем ответ ЮВАЛА . полезная ссылка