Изменения

{{Задача|definition ==Формулировка задачи==В '''Задаче о сумме подмножества''' (Subset sum problem) входными данными являются набор из Дано множество <mathtex>nS</mathtex> целых чисел , содержащие <mathtex>s_{i}n</mathtex> целых чисел и целое число <mathtex>s</mathtex>. Требуется выяснить, возможно ли выбрать такое подмножество из <mathtex>S' \{s_{i}\}subseteq S</mathtex> с суммой <mathtex>s</mathtex>:<p style="text-align:center;"br><mathtex>\exist \{k_{j}\} exists S' \subseteq (1..n)S: \sum_sum\limits_{s_{i } \in k_{j}S'}{s_{i}} = s</mathtex></p>}} 

Для доказательства того, что '''задаче о сумме подмножества''' (англ. ''Subset sum problem'', <mathtex>\mboxmathrm{Subset sum problemSSP} \in NPC</mathtex> ) [[NPC | NP-полной]], необходимо доказать два факта:*<mathtex>\mboxmathrm{Subset sum problemSSP} \in</mathtex> [[NP|<mathtex>\mathrm{NP}</mathtex>]] *<mathtex>\mboxmathrm{Subset sum problemSSP} \in</mathtex> [[NPH|<mathtex>\mathrm{NPH}</mathtex>]]  ===Доказательство принадлежности к NP===В качестве сертификата возьмем удовлетворяющее условию задачи множество <mathtex>\{s_{k_{j}}\}S'</tex> с суммой <tex>s</mathtex>. Очевидно, оно Оно удовлетворяет всем требованиям,налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает проверит вхождение всех элементов <tex>S'</tex> в множество <tex>S</tex> за полиномиальное от размера входа время<tex>\left\vert{S'}\right\vert \times \left\vert{S}\right\vert</tex>. ===Доказательство принадлежности к NPH===Сведем [[3NP-CNF_Satполнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|3-CNF_Sat<tex>\mathrm{3CNFSAT}</tex>]] к задаче о о сумме подмножества. Пусть задана 3-CNF <tex>\mathrm{3CNF}</tex> формула <mathtex>\phivarphi</mathtex> от <mathtex>n</mathtex>переменных <mathtex>x_{i}</mathtex>, состоящая из <mathtex>k</mathtex> пар скобок <mathtex>C_{i}</mathtex>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <mathtex>f\!\!:(\{x_{i}\},\{C_{i}\}) varphi \to (\{s_{i}\}S,s)</mathtex>. 

Для каждой переменной <mathtex>x_{i}</mathtex> и каждой пары скобок <mathtex>C_{j}</mathtex> создадим по два числа в десятичной системе счисления, каждое длиной <mathtex>n+k</mathtex> цифр. Эти числа образуют <mathtex>\{s_{i}\}S</mathtex>. Также создадим число <mathtex>s</mathtex> длиной <mathtex>n+k</mathtex> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.Метки, соответствующие парам скобок, присвоены <mathtex>k</mathtex> младшим разрядам чисел.*В числе <mathtex>s</mathtex> все разряды, соответствующие переменным, установим <mathtex>1</mathtex>, а оставшиеся сделаем равными <mathtex>4</mathtex>.*Каждой переменной <mathtex>x_{i}</mathtex> соответствуют два числаиз <tex>S</tex>: <mathtex>v_{i}</mathtex> и <mathtex>u_{i}</mathtex>. Опишем создание этих чисел. Разряд, соответствующий <mathtex>x_{i}</mathtex> установим равным <mathtex>1</mathtex>, а все остальные разряды, соответствующие переменным, установим равными <mathtex>0</mathtex>. Далее, для числа <mathtex>v_{i}</mathtex> установим все разряды, соответствующие парам скобок, содержащих <mathtex>x_{i}</mathtex>, равными <mathtex>1</mathtex>. Во все остальные "скобочные" разряды поставим <mathtex>0</mathtex>. В числе <mathtex>w_{i}</mathtex> установим все разряды, соответствующие парам скобок, содержащих <mathtex>\neg x_{i}</mathtex>, равными <mathtex>1</mathtex>, а во все остальные "скобочные" разряды поставим <mathtex>0</mathtex>.*Каждой паре скобок <mathtex>C_{j}</mathtex> соответствуют два числаиз <tex>S</tex>: <mathtex>d_{i}</mathtex> и <mathtex>e_{i}</mathtex>. Оба этих числа содержат <mathtex>0</mathtex> во всех разрядах, кроме соответствующего <mathtex>C_{j}</mathtex>. В этом разряде у <mathtex>d_{i}</mathtex> поставим <mathtex>1</mathtex>, а у <mathtex>e_{i}</mathtex> поставим {{---}} <mathtex>2</mathtex>.

*Получаемое сводящей функцией множество <mathtex>\{s_{i}\}S</mathtex> состоит из <mathtex>2(n+k)</mathtex> десятичных чисел длиной <mathtex>(n+k)</mathtex> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.*Пусть формула <mathtex>\phivarphi</mathtex> выполнима, то есть существует набор значений <mathtex>\{y_{i}\}^{n}_{i=1}:~\phivarphi(y_{1},...,\ldots y_{n})=1 </mathtex>. И пусть <tex>(S,s) = f(\varphi)</tex>. Тогда в полученном множестве <mathtex>\{s_{i}\}S</mathtex> существует подмножество с суммой <mathtex>s</mathtex>. Действительно, для каждой переменной, если <mathtex>y_{k} = 1</mathtex>, то добавим в <mathtex>\{s_{i_{j}}\}~ v_{i}</mathtex> в <tex>S'</tex>. Иначе добавим <mathtex>w_{i}</mathtex>. Теперь <tex>S'</tex> содержит уже <tex>n</tex> чисел. Заметим, что для каждого "скобочного"разряда в уже набранной части <mathtex>\{s_{i_{j}}\}S'</mathtex> есть не менее одного и не более трех чисел, у которых в данном разряде стоит <mathtex>1</mathtex>. Значит для каждого соответствующего паре скобок <mathtex>C_{j}</mathtex> разряда мы сможем выбрать одно или оба числа <mathtex>d_{ij}</mathtex> и <mathtex>e_{ij}</mathtex> так, чтобы сумма в данном разряде совпадала с требуемой (значением этого разряда в стала равна <mathtex>s4</mathtex>). Добавим их в <mathtex>\{s_{i_{j}}\}S'</mathtex>. Также заметим, что суммы во всех "переменных" разрядах равны <mathtex>1</mathtex>, так как для каждого <mathtex>i</mathtex> выбиралось строго одно число из <mathtex>v_{i}</mathtex> и <mathtex>u_{i}</mathtex>. Значит, <mathtex> \sum_sum\limits_{s_{k } \in i_{j}S'}{s_{k}} = s</mathtex>.*Пусть теперь в наборе <mathtex>\{s_{i}\}S</mathtex> есть подмножество <mathtex>S':~ \sum\limits_{s_{i_{j}}\k}:~ \sum_{k \in i_{j}S'}{s_{k}} = s</mathtex>. Тогда исходная формула <mathtex>\phivarphi</mathtex> выполнима. Действительно, если в <mathtex>v_{i} \in \{s_{i_{j}}\}S'</mathtex>, то установим переменную <mathtex>x_{i}=1</mathtex>. Если же <mathtex>w_{i} \in \{s_{i_{j}}\}S'</mathtex>, то <mathtex>x_{i}=0</mathtex>. Покажем, что <mathtex>\phivarphi(x_{1},...,\ldots x_{n})=1 </mathtex>. Действительно, так как <mathtex>\sum_sum\limits_{s_{k } \in i_{j}S'}{s_{k}} = s</mathtex>, в каждой паре скобок хотя бы один терм равен <mathtex>1</tex>. Значит каждый терм равен <tex>1</mathtex>. А значиттогда и вся <tex>\varphi = 1</tex>.====Пример сведения====Пусть исходная функция <tex>\varphi(x_{1} \ldots x_{4}) = (x_{1} \lor x_{2} \lor \neg x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4})</tex>.Пометим разряды следующим образом (слева направо): <tex>x_{1},x_{2},x_{3},x_{4},C_{1}, формула выполнимаC_{2}</tex>. Тогда:*<tex>v_{1} = 100010</tex>*<tex>w_{1} = 100001</tex> *<tex>v_{2} = 010011 = 10011</tex>*<tex>w_{2} = 010000 = 10000</tex> *<tex>v_{3} = 001000 = 1000</tex>*<tex>w_{3} = 001010 = 1010</tex> *<tex>v_{4} = 000101 = 101</tex>*<tex>w_{4} = 000100 = 100</tex> *<tex>d_{1} = 000010 = 10</tex>*<tex>e_{1} = 000020 = 20</tex> *<tex>d_{2} = 000001 = 1</tex>*<tex>e_{2} = 000002 = 2</tex> *<tex>s = 111144</tex> <tex>S = (\bigcup\limits_{i=1}^{4} v_{i}) \cup (\bigcup\limits_{i=1}^{4} w_{i}) \cup (\bigcup\limits_{i=1}^{2} d_{i}) \cup (\bigcup\limits_{i=1}^{2} e_{i})</tex> Тогда набору значений <tex>Y = (0,0,0,1):~ \varphi(Y) = 1</tex> соответствует <tex>S' = \{w_{1},~w_{2},~w_{3},~v_{4},~d_{1},~e_{1},~e_{2}\}</tex>. И действительно, <tex>100001 + 10000 + 1010 + 101 + 10 + 20 + 2 = 111144</tex>. ==См. также==* [[NP]]* [[NPH]]* [[NPC]]* [[Классы NP и Σ₁]]* [[3CNFSAT]]* [[Примеры NP-полных языков]] ==Источники информации==* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms, 3rd Edition" {{---}} Издательство MIT Press, 2009. {{---}} 1086 c. {{---}} ISBN 978-0-262-03384-8 (англ.)* Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 423 с. {{---}} ISBN 5-8459-0261-4 (рус.) [[Категория: Теория сложности]][[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]][[Категория: Примеры NP-полных языков]]