1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Задача|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>}}
==Доказательство NP-полноты==
Для доказательства того, что '''задаче о сумме подмножества''' (англ. ''Subset sum problem'', <tex>\mathrm{SSP}</tex>) [[NPC | NP-полной]], необходимо доказать два факта:
*<tex>\mathrm{SSP} \in</tex> [[NP | <tex>\mathrm{NP}</tex>]]
*<tex>\mathrm{SSP} \in</tex> [[NPH | <tex>\mathrm{NPH}</tex>]]
===Доказательство принадлежности NP===
В качестве сертификата возьмем удовлетворяющее условию задачи множество <tex>S'</tex> с суммой <tex>s</tex>. Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов <tex>S'</tex> в множество <tex>S</tex> за время <tex>\left\vert{S'}\right\vert \times \left\vert{S}\right\vert</tex>.
===Доказательство принадлежности NPH===
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|<tex>\mathrm{3CNFSAT}</tex>]] к задаче о сумме подмножества. Пусть задана <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>.
====Построение сводящей функции====
Для каждой переменной <tex>x_{i}</tex> и каждой пары скобок <tex>C_{j}</tex> создадим по два числа в десятичной системе счисления, каждое длиной <tex>n+k</tex> цифр. Эти числа образуют <tex>S</tex>. Также создадим число <tex>s</tex> длиной <tex>n+k</tex> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.
Метки, соответствующие парам скобок, присвоены <tex>k</tex> младшим разрядам чисел.
*В числе <tex>s</tex> все разряды, соответствующие переменным, установим <tex>1</tex>, а оставшиеся сделаем равными <tex>4</tex>.
*Каждой переменной <tex>x_{i}</tex> соответствуют два числа из <tex>S</tex>: <tex>v_{i}</tex> и <tex>u_{i}</tex>. Опишем создание этих чисел. Разряд, соответствующий <tex>x_{i}</tex> установим равным <tex>1</tex>, а все остальные разряды, соответствующие переменным, установим равными <tex>0</tex>. Далее, для числа <tex>v_{i}</tex> установим все разряды, соответствующие парам скобок, содержащих <tex>x_{i}</tex>, равными <tex>1</tex>. Во все остальные "скобочные" разряды поставим <tex>0</tex>. В числе <tex>w_{i}</tex> установим все разряды, соответствующие парам скобок, содержащих <tex>\neg x_{i}</tex>, равными <tex>1</tex>, а во все остальные "скобочные" разряды поставим <tex>0</tex>.
*Каждой паре скобок <tex>C_{j}</tex> соответствуют два числа из <tex>S</tex>: <tex>d_{i}</tex> и <tex>e_{i}</tex>. Оба этих числа содержат <tex>0</tex> во всех разрядах, кроме соответствующего <tex>C_{j}</tex>. В этом разряде у <tex>d_{i}</tex> поставим <tex>1</tex>, а у <tex>e_{i}</tex> {{---}} <tex>2</tex>.
====Корректность сводящей функции====
*Получаемое сводящей функцией множество <tex>S</tex> состоит из <tex>2(n+k)</tex> десятичных чисел длиной <tex>(n+k)</tex> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
*Пусть формула <tex>\varphi</tex> выполнима, то есть существует набор значений <tex>\{y_{i}\}^{n}_{i=1}:~\varphi(y_{1}\ldots y_{n})=1 </tex>. И пусть <tex>(S,s) = f(\varphi)</tex>. Тогда в полученном множестве <tex>S</tex> существует подмножество с суммой <tex>s</tex>. Действительно, для каждой переменной, если <tex>y_{k} = 1</tex>, то добавим <tex>v_{i}</tex> в <tex>S'</tex>. Иначе добавим <tex>w_{i}</tex>. Теперь <tex>S'</tex> содержит уже <tex>n</tex> чисел. Заметим, что для каждого "скобочного" разряда в уже набранной части <tex>S'</tex> есть не менее одного и не более трех чисел, у которых в данном разряде стоит <tex>1</tex>. Значит для каждого соответствующего паре скобок <tex>C_{j}</tex> разряда мы сможем выбрать одно или оба числа <tex>d_{j}</tex> и <tex>e_{j}</tex> так, чтобы сумма в данном разряде совпадала с требуемой (стала равна <tex>4</tex>). Добавим их в <tex>S'</tex>. Также заметим, что суммы во всех "переменных" разрядах равны <tex>1</tex>, так как для каждого <tex>i</tex> выбиралось строго одно число из <tex>v_{i}</tex> и <tex>u_{i}</tex>. Значит, <tex> \sum\limits_{s_{k} \in S'}{s_{k}} = s</tex>.
*Пусть теперь в наборе <tex>S</tex> есть подмножество <tex>S':~ \sum\limits_{s_{k} \in S'}{s_{k}} = s</tex>. Тогда исходная формула <tex>\varphi</tex> выполнима. Действительно, если <tex>v_{i} \in S'</tex>, то установим переменную <tex>x_{i}=1</tex>. Если же <tex>w_{i} \in S'</tex>, то <tex>x_{i}=0</tex>. Покажем, что <tex>\varphi(x_{1}\ldots x_{n}) = 1 </tex>. Действительно, так как <tex> \sum\limits_{s_{k} \in S'}{s_{k}} = s</tex>, в каждой паре скобок хотя бы один терм равен <tex>1</tex>. Значит каждый терм равен <tex>1</tex>. А тогда и вся <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-полных языков]]
