1632
правки
Изменения
м
rollbackEdits.php mass rollback
===Доказательство принадлежности NPH===
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|3-CNF_Sat<tex>\mathrm{3CNFSAT}</tex>]] к задаче о сумме подмножества. Пусть задана 3-CNF <tex>\mathrm{3CNF}</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>.
