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]Subset~ sum~ problem \in NPC[/math] необходимо доказать два факта:

• [math]Subset~ sum~ problem \in[/math] [math]NP[/math]
• [math]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].