Изменения

{{Задача|definition ==Формулировка задачи==В '''задаче о сумме подмножества''' (англ. ''Subset sum problem'') входными данными являются Дан набор из <math>n</math> целых чисел <math>S</math> и целое число <math>s</math>. Требуется выяснить, возможно ли выбрать подмножество <math>S' \subseteq S</math> с суммой <math>s</math>:

 <math>\exists S' \subseteq S: \sum_sum\limits_{s_{i} \in S'}{s_{i}} = s</math>}}

Для доказательства того, что задачи '''задаче о сумме подмножества является ''' (англ. ''Subset sum problem'', <math>\mathrm{SSP}</math>) [[NPC | NP-полной]], необходимо доказать два факта:*Задачи о сумме подмножества <math>\mathrm{SSP} \in</math> [[NP| <math>\mathrm{NP}</math>]] *Задачи о сумме подмножества <math>\mathrm{SSP} \in</math> [[NPH| <math>\mathrm{NPH}</math>]]

*Пусть формула <math>\varphi</math> выполнима, то есть существует набор значений <math>\{y_{i}\}^{n}_{i=1}:~\varphi(y_{1}\ldots y_{n})=1 </math>. И пусть <math>(S,s) = f(\varphi)</math>. Тогда в полученном множестве <math>S</math> существует подмножество с суммой <math>s</math>. Действительно, для каждой переменной, если <math>y_{k} = 1</math>, то добавим <math>v_{i}</math> в <math>S'</math>. Иначе добавим <math>w_{i}</math>. Теперь <math>S'</math> содержит уже <math>n</math> чисел. Заметим, что для каждого "скобочного" разряда в уже набранной части <math>S'</math> есть не менее одного и не более трех чисел, у которых в данном разряде стоит <math>1</math>. Значит для каждого соответствующего паре скобок <math>C_{j}</math> разряда мы сможем выбрать одно или оба числа <math>d_{j}</math> и <math>e_{j}</math> так, чтобы сумма в данном разряде совпадала с требуемой (стала равна <math>4</math>). Добавим их в <math>S'</math>. Также заметим, что суммы во всех "переменных" разрядах равны <math>1</math>, так как для каждого <math>i</math> выбиралось строго одно число из <math>v_{i}</math> и <math>u_{i}</math>. Значит, <math> \sum_sum\limits_{s_{k} \in S'}{s_{k}} = s</math>.*Пусть теперь в наборе <math>S</math> есть подмножество <math>S':~ \sum_sum\limits_{s_{k} \in S'}{s_{k}} = s</math>. Тогда исходная формула <math>\varphi</math> выполнима. Действительно, если <math>v_{i} \in S'</math>, то установим переменную <math>x_{i}=1</math>. Если же <math>w_{i} \in S'</math>, то <math>x_{i}=0</math>. Покажем, что <math>\varphi(x_{1}\ldots x_{n}) = 1 </math>. Действительно, так как <math> \sum_sum\limits_{s_{k} \in S'}{s_{k}} = s</math>, в каждой паре скобок хотя бы один терм равен <math>1</math>. Значит каждый терм равен <math>1</math>. А тогда и вся <math>\varphi = 1</math>.