NP-полнота задачи о сумме подмножества

Формулировка задачи

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

[math]\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s[/math]

Доказательство NP-полноты

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

• [math]\mbox{Subset sum problem} \in[/math] [math]NP[/math]
• [math]\mbox{Subset sum problem} \in[/math] [math]NPH[/math]

Доказательство принадлежности к NP

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

Доказательство принадлежности к NPH

Сведем 3-CNF_Sat к задаче о о сумме подмножества. Пусть задана 3-CNF формула [math]\phi[/math] от [math]n[/math] переменных [math]x_{i}[/math], состоящая из [math]k[/math] пар скобок [math]C_{i}[/math]. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию [math]f\!\!:(\{x_{i}\},\{C_{i}\}) \to (\{s_{i}\},s)[/math].

Построение сводящей функции

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

• В числе [math]s[/math] все разряды, соответствующие переменным, установим [math]1[/math], а оставшиеся сделаем равными [math]4[/math].
• Каждой переменной [math]x_{i}[/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]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}\}[/math] состоит из [math]2(n+k)[/math] десятичных чисел длиной [math](n+k)[/math] каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
• Пусть формула [math]\phi[/math] выполнима, то есть существует набор значений [math]\{y_{i}\}:~\phi(y_{1},...,y_{n})=1 [/math]. Тогда в полученном множестве [math]\{s_{i}\}[/math] существует подмножество с суммой [math]s[/math]. Действительно, если [math]y_{k} = 1[/math], то добавим в [math]\{s_{i_{j}}\}~ v_{i}[/math]. Иначе добавим [math]w_{i}[/math]. Заметим, что для каждого "скобочного"разряда в уже набранной части [math]\{s_{i_{j}}\}[/math] есть не менее одного и не более трех чисел, у которых в данном разряде стоит [math]1[/math]. Значит для каждого соответствующего паре скобок [math]C_{j}[/math] разряда мы сможем выбрать одно или оба числа [math]d_{i}[/math] и [math]e_{i}[/math] так, чтобы сумма в данном разряде совпадала с требуемой (значением этого разряда в [math]s[/math]). Добавим их в [math]\{s_{i_{j}}\}[/math]. Также заметим, что суммы во всех "переменных" разрядах равны [math]1[/math], так как для каждого [math]i[/math] выбиралось одно число из [math]v_{i}[/math] и [math]u_{i}[/math]. Значит, [math] \sum_{k \in i_{j}}{s_{k}} = s[/math].
• Пусть теперь в наборе [math]\{s_{i}\}[/math] есть подмножество [math]\{s_{i_{j}}\}:~ \sum_{k \in i_{j}}{s_{k}} = s[/math]. Тогда исходная формула [math]\phi[/math] выполнима. Действительно, если в [math]v_{i} \in \{s_{i_{j}}\}[/math], то установим переменную [math]x_{i}=1[/math]. Если же [math]w_{i} \in \{s_{i_{j}}\}[/math], то [math]x_{i}=0[/math]. Покажем, что [math]\phi(x_{1},...,x_{n})=1 [/math]. Действительно, так как [math]\sum_{k \in i_{j}}{s_{k}} = s[/math], в каждой паре скобок хотя бы один терм равен [math]1[/math]. А значит, формула выполнима.