54
правки
Изменения
м
→Доказательство принадлежности NPH
===Доказательство принадлежности NPH===
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|<tex>\mathrm{3-CNFSAT3CNFSAT}</tex>]] к задаче о сумме подмножества. Пусть задана <tex>\mathrm{3-CNF }</tex> формула <tex>\varphi</tex> от <tex>n</tex>
переменных <tex>x_{i}</tex>, состоящая из <tex>k</tex> пар скобок <tex>C_{i}</tex>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <tex>f\!\!:\varphi \to (S,s)</tex>.
