Изменения
→Доказательство принадлежности к NPH
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
===Доказательство принадлежности к 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\!\!:\phi \to (S,s)</math>.
====Построение сводящей функции====
