53
правки
Изменения
Нет описания правки
===Доказательство принадлежности к NPH===
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|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}\}^{n}_{i=1},\{C_{j}\}^{k}_{j=1}) \to (S,s)</math> (эквивалентная запись: <math>f\!\!:\phi \to (S,s)</math>).
====Построение сводящей функции====
Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>S</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.
