18
правок
Изменения
Доказательство завершено.
===Доказательство принадлежности к 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>\{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>. А значит, формула выполнима.
