NP-полнота задачи разбиения множества

Задача разбиения множества (Partition) имеет очень простую формулировку, но является NP-полной. Формулировка задачи следующая: по (мульти)множеству А натуральных чисел требуется выяснить, можно ли разбить А на два подмножества с одинаковыми суммами элементов. Эту задачу можно сформулировать и как оптимизационную: для (мульти)множества А найти такое его разбиение на два подмножества, при котором модуль разности сумм элементов этих подмножеств является наименьшей из возможных. В докладе будет показано простое доказательство NP-полноты (прежде всего, NP-трудности) задачи Partition. Для этого будет построено полиномиальное сведение к ней задачи SubsetSum (состоящей в том, что нужно установить для числового множества А и числа Т, имеется ли в А подмножество с суммой элементов, равной Т), к которой мы полиномиально сведем проблему CNF (проблему выполнимости булевых формул, находящихся в конъюнктивной нормальной форме). В оставшееся время мы докажем NP-трудность проблемы CNF, полиномиально сведя к ней проблему SAT (проблему выполнимости булевых формул в полном языке), а затем докажем NP-трудность проблемы SAT, используя идею классического доказательства Кука–Левина.