18
правок
Изменения
структура д-ва + начато
==Формулировка задачи==
В '''Задаче о сумме помножестваподмножества''' (Subset sum problem) входными данными являются набор из <math>n</math> целых чисел <math>s_{i}</math> и целое число <math>s</math>. Требуется выяснить, возможно ли выбрать такое подмножество из <math>\{s_{i}\}</math> с суммой <math>s</math>:
<p style="text-align:center;">
<math>\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s</math>
</p>
==Доказательство NP-полноты==
Для доказательства того, что <math>Subset~ sum~ problem \in NPC</math> необходимо доказать два факта:
*<math>Subset~ sum~ problem \in</math> [[NP|<math>NP</math>]]
*<math>Subset~ sum~ problem \in</math> [[NPH|<math>NPH</math>]]
===Доказательство принадлежности к NP===
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>\{s_{k_{j}}\}</math>. Очевидно, оно удовлетворяет всем требованиям,
налагаемым на сертификат.
===Доказательство принадлежности к NPH===
Сведем [[3-CNF_Sat|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>.
====Корректность сводящей функции====
