Изменения

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

<math>\exist \{k_{j}\} S' \subseteq (1..n)S: \sum_{s_{i } \in k_{j}S'}{s_{i}} = s</math>

Для доказательства того, что Subset sum problem <math>\mbox{Subset sum problem} \in NPC</math> [[NPC]], необходимо доказать два факта:*Subset sum problem <math>\mbox{Subset sum problem} \in</math> [[NP|<math>NP</math>]] *Subset sum problem <math>\mbox{Subset sum problem} \in</math> [[NPH|<math>NPH</math>]]

В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>\{s_{k_{j}}\}S'</math> с суммой <math>s</math>. Очевидно, оно удовлетворяет всем требованиям,налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.

переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:(\{x_{i}\}^{n}_{i=1},\{C_{ij}\}^{k}_{j=1}) \to (S,s)</math> (эквивалентная запись: <math>f\!\!:\{s_{i}phi \}to (S,s)</math>).

Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>\{s_{i}\}S</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.

*Каждой переменной <math>x_{i}</math> соответствуют два числаиз <math>S</math>: <math>v_{i}</math> и <math>u_{i}</math>. Опишем создание этих чисел. Разряд, соответствующий <math>x_{i}</math> установим равным <math>1</math>, а все остальные разряды, соответствующие переменным, установим равными <math>0</math>. Далее, для числа <math>v_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>x_{i}</math>, равными <math>1</math>. Во все остальные "скобочные" разряды поставим <math>0</math>. В числе <math>w_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>\neg x_{i}</math>, равными <math>1</math>, а во все остальные "скобочные" разряды поставим <math>0</math>.*Каждой паре скобок <math>C_{j}</math> соответствуют два числаиз <math>S</math>: <math>d_{i}</math> и <math>e_{i}</math>. Оба этих числа содержат <math>0</math> во всех разрядах, кроме соответствующего <math>C_{j}</math>. В этом разряде у <math>d_{i}</math> поставим <math>1</math>, а у <math>e_{i}</math> поставим <math>2</math>.

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