NP-полнота задачи о сумме подмножества — различия между версиями
Miron (обсуждение | вклад) (Доказательство завершено.) |
Miron (обсуждение | вклад) (стилистические изменения) |
||
| Строка 1: | Строка 1: | ||
==Формулировка задачи== | ==Формулировка задачи== | ||
| − | В ''' | + | В '''задаче о сумме подмножества''' (Subset sum problem) входными данными являются набор из <math>n</math> целых чисел <math>S</math> и целое число <math>s</math>. Требуется выяснить, возможно ли выбрать подмножество <math>S' \subseteq S</math> с суммой <math>s</math>: |
<p style="text-align:center;"> | <p style="text-align:center;"> | ||
| − | <math>\exist | + | <math>\exist S' \subseteq S: \sum_{s_{i} \in S'}{s_{i}} = s</math> |
</p> | </p> | ||
==Доказательство NP-полноты== | ==Доказательство NP-полноты== | ||
| − | Для доказательства того, что <math> | + | Для доказательства того, что Subset sum problem <math>\in</math> [[NPC]], необходимо доказать два факта: |
| − | *<math> | + | *Subset sum problem <math>\in</math> [[NP]] |
| − | *<math> | + | *Subset sum problem <math>\in</math>[[NPH]] |
===Доказательство принадлежности к NP=== | ===Доказательство принадлежности к NP=== | ||
| − | В качестве сертификата возьмем удовлетворяющее условию задачи множество <math> | + | В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. |
| − | налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
===Доказательство принадлежности к NPH=== | ===Доказательство принадлежности к NPH=== | ||
Сведем [[3-CNF_Sat|3-CNF_Sat]] к задаче о о сумме подмножества. Пусть задана 3-CNF формула <math>\phi</math> от <math>n</math> | Сведем [[3-CNF_Sat|3-CNF_Sat]] к задаче о о сумме подмножества. Пусть задана 3-CNF формула <math>\phi</math> от <math>n</math> | ||
| − | переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:(\{x_{i}\},\{C_{ | + | переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:(\{x_{i}\}^{n}_{i=1},\{C_{j}\}^{k}_{j=1}) \to (S,s)</math> (эквивалентная запись: <math>f\!\!:\phi \to (S,s)</math>). |
====Построение сводящей функции==== | ====Построение сводящей функции==== | ||
| − | Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math> | + | Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>S</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок. |
Метки, соответствующие парам скобок, присвоены <math>k</math> младшим разрядам чисел. | Метки, соответствующие парам скобок, присвоены <math>k</math> младшим разрядам чисел. | ||
*В числе <math>s</math> все разряды, соответствующие переменным, установим <math>1</math>, а оставшиеся сделаем равными <math>4</math>. | *В числе <math>s</math> все разряды, соответствующие переменным, установим <math>1</math>, а оставшиеся сделаем равными <math>4</math>. | ||
| − | *Каждой переменной <math>x_{i}</math> соответствуют два числа: <math>v_{i}</math> и <math>u_{i}</math>. Опишем создание этих чисел. Разряд, соответствующий <math>x_{i}</math> установим равным <math>1</math>, а все остальные разряды, соответствующие переменным, установим равными <math>0</math>. Далее, для числа <math>v_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>x_{i}</math>, равными <math>1</math>. Во все остальные "скобочные" разряды поставим <math>0</math>. В числе <math>w_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>\neg x_{i}</math>, равными <math>1</math>, а во все остальные "скобочные" разряды поставим <math>0</math>. | + | *Каждой переменной <math>x_{i}</math> соответствуют два числа из <math>S</math>: <math>v_{i}</math> и <math>u_{i}</math>. Опишем создание этих чисел. Разряд, соответствующий <math>x_{i}</math> установим равным <math>1</math>, а все остальные разряды, соответствующие переменным, установим равными <math>0</math>. Далее, для числа <math>v_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>x_{i}</math>, равными <math>1</math>. Во все остальные "скобочные" разряды поставим <math>0</math>. В числе <math>w_{i}</math> установим все разряды, соответствующие парам скобок, содержащих <math>\neg x_{i}</math>, равными <math>1</math>, а во все остальные "скобочные" разряды поставим <math>0</math>. |
| − | *Каждой паре скобок <math>C_{j}</math> соответствуют два числа: <math>d_{i}</math> и <math>e_{i}</math>. Оба этих числа содержат <math>0</math> во всех разрядах, кроме соответствующего <math>C_{j}</math>. В этом разряде у <math>d_{i}</math> поставим <math>1</math>, а у <math>e_{i}</math> поставим <math>2</math>. | + | *Каждой паре скобок <math>C_{j}</math> соответствуют два числа из <math>S</math>: <math>d_{i}</math> и <math>e_{i}</math>. Оба этих числа содержат <math>0</math> во всех разрядах, кроме соответствующего <math>C_{j}</math>. В этом разряде у <math>d_{i}</math> поставим <math>1</math>, а у <math>e_{i}</math> поставим <math>2</math>. |
====Корректность сводящей функции==== | ====Корректность сводящей функции==== | ||
| − | *Получаемое сводящей функцией множество <math> | + | *Получаемое сводящей функцией множество <math>S</math> состоит из <math>2(n+k)</math> десятичных чисел длиной <math>(n+k)</math> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время. |
| − | *Пусть формула <math>\phi</math> выполнима, то есть существует набор значений <math>\{y_{i}\}:~\phi(y_{1} | + | *Пусть формула <math>\phi</math> выполнима, то есть существует набор значений <math>\{y_{i}\}^{n}_{i=1}:~\phi(y_{1}\ldots y_{n})=1 </math>. И пусть <math>(S,s) = f(\phi)</math>. Тогда в полученном множестве <math>S</math> существует подмножество с суммой <math>s</math>. Действительно, для каждой переменной, если <math>y_{k} = 1</math>, то добавим в <math>S'~ v_{i}</math>. Иначе добавим <math>w_{i}</math>. Теперь <math>S'</math> содержит уже <math>n</math> чисел. Заметим, что для каждого "скобочного"разряда в уже набранной части <math>S'</math> есть не менее одного и не более трех чисел, у которых в данном разряде стоит <math>1</math>. Значит для каждого соответствующего паре скобок <math>C_{j}</math> разряда мы сможем выбрать одно или оба числа <math>d_{j}</math> и <math>e_{j}</math> так, чтобы сумма в данном разряде совпадала с требуемой (стала равна <math>4</math>). Добавим их в <math>S'</math>. Также заметим, что суммы во всех "переменных" разрядах равны <math>1</math>, так как для каждого <math>i</math> выбиралось строго одно число из <math>v_{i}</math> и <math>u_{i}</math>. Значит, <math> \sum_{s_{k} \in S'}{s_{k}} = s</math>. |
| − | *Пусть теперь в наборе <math> | + | *Пусть теперь в наборе <math>S</math> есть подмножество <math>S':~ \sum_{s_{k} \in S'}{s_{k}} = s</math>. Тогда исходная формула <math>\phi</math> выполнима. Действительно, если <math>v_{i} \in S'</math>, то установим переменную <math>x_{i}=1</math>. Если же <math>w_{i} \in S'</math>, то <math>x_{i}=0</math>. Покажем, что <math>\phi(x_{1}\ldots x_{n}) = 1 </math>. Действительно, так как <math> \sum_{s_{k} \in S'}{s_{k}} = s</math>, в каждой паре скобок хотя бы один терм равен <math>1</math>. Значит каждый терм равен <math>1</math>. А тогда и вся <math>\phi = 1</math>. |
Версия 08:56, 10 марта 2010
Содержание
Формулировка задачи
В задаче о сумме подмножества (Subset sum problem) входными данными являются набор из целых чисел и целое число . Требуется выяснить, возможно ли выбрать подмножество с суммой :
Доказательство NP-полноты
Для доказательства того, что Subset sum problem NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем удовлетворяющее условию задачи множество с суммой . Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH
Сведем 3-CNF_Sat к задаче о о сумме подмножества. Пусть задана 3-CNF формула от переменных , состоящая из пар скобок . Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию (эквивалентная запись: ).
Построение сводящей функции
Для каждой переменной и каждой пары скобок создадим по два числа в десятичной системе счисления, каждое длиной цифр. Эти числа образуют . Также создадим число длиной цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок. Метки, соответствующие парам скобок, присвоены младшим разрядам чисел.
- В числе все разряды, соответствующие переменным, установим , а оставшиеся сделаем равными .
- Каждой переменной соответствуют два числа из : и . Опишем создание этих чисел. Разряд, соответствующий установим равным , а все остальные разряды, соответствующие переменным, установим равными . Далее, для числа установим все разряды, соответствующие парам скобок, содержащих , равными . Во все остальные "скобочные" разряды поставим . В числе установим все разряды, соответствующие парам скобок, содержащих , равными , а во все остальные "скобочные" разряды поставим .
- Каждой паре скобок соответствуют два числа из : и . Оба этих числа содержат во всех разрядах, кроме соответствующего . В этом разряде у поставим , а у поставим .
Корректность сводящей функции
- Получаемое сводящей функцией множество состоит из десятичных чисел длиной каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
- Пусть формула выполнима, то есть существует набор значений . И пусть . Тогда в полученном множестве существует подмножество с суммой . Действительно, для каждой переменной, если , то добавим в . Иначе добавим . Теперь содержит уже чисел. Заметим, что для каждого "скобочного"разряда в уже набранной части есть не менее одного и не более трех чисел, у которых в данном разряде стоит . Значит для каждого соответствующего паре скобок разряда мы сможем выбрать одно или оба числа и так, чтобы сумма в данном разряде совпадала с требуемой (стала равна ). Добавим их в . Также заметим, что суммы во всех "переменных" разрядах равны , так как для каждого выбиралось строго одно число из и . Значит, .
- Пусть теперь в наборе есть подмножество . Тогда исходная формула выполнима. Действительно, если , то установим переменную . Если же , то . Покажем, что . Действительно, так как , в каждой паре скобок хотя бы один терм равен . Значит каждый терм равен . А тогда и вся .
