18
правок
Изменения
часть доказательства
</p>
==Доказательство NP-полноты==
Для доказательства того, что <math>\mbox{Subset~ sum~ problem } \in NPC</math> необходимо доказать два факта:*<math>\mbox{Subset~ sum~ problem } \in</math> [[NP|<math>NP</math>]] *<math>\mbox{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>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>.
===Пример сведения===
