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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (См. также)
(→‎Доказательство NP-полноты: опечатки)
Строка 5: Строка 5:
  
 
==Доказательство NP-полноты==
 
==Доказательство NP-полноты==
−
Для доказательства того, что Subset sum problem <math>\in</math> [[NPC]], необходимо доказать два факта:
+
Для доказательства того, что задачи о сумме подмножества является [[NPC | NP-полной]], необходимо доказать два факта:
−
*Subset sum problem <math>\in</math> [[NP]]  
+
*Задачи о сумме подмножества <math>\in</math> [[NP]]  
−
*Subset sum problem <math>\in</math>[[NPH]]  
+
*Задачи о сумме подмножества <math>\in</math> [[NPH]]
 +
 
 
===Доказательство принадлежности к NP===
 
===Доказательство принадлежности к NP===
−
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
+
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов <math>S'</math> в множество <math>S</math>.
 +
 
 
===Доказательство принадлежности к NPH===
 
===Доказательство принадлежности к NPH===
 
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|3-CNF_Sat]] к задаче о сумме подмножества. Пусть задана 3-CNF формула <math>\phi</math> от <math>n</math>
 
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|3-CNF_Sat]] к задаче о сумме подмножества. Пусть задана 3-CNF формула <math>\phi</math> от <math>n</math>
 
переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:\phi \to (S,s)</math>.
 
переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:\phi \to (S,s)</math>.
 +
 
====Построение сводящей функции====
 
====Построение сводящей функции====
 
Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>S</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.
 
Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>S</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.
Строка 18: Строка 21:
 
*В числе <math>s</math> все разряды, соответствующие переменным, установим <math>1</math>, а оставшиеся сделаем равными <math>4</math>.
 
*В числе <math>s</math> все разряды, соответствующие переменным, установим <math>1</math>, а оставшиеся сделаем равными <math>4</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>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>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>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>S</math> состоит из <math>2(n+k)</math> десятичных чисел длиной <math>(n+k)</math> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
 
*Получаемое сводящей функцией множество <math>S</math> состоит из <math>2(n+k)</math> десятичных чисел длиной <math>(n+k)</math> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
−
*Пусть формула <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>\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>v_{i}</math> в <math>S'</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>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>.
 
*Пусть теперь в наборе <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>.
 
====Пример сведения====
 
====Пример сведения====

Версия 22:09, 16 мая 2016

Формулировка задачи

В задаче о сумме подмножества (Subset sum problem) входными данными являются набор из [math]n[/math] целых чисел [math]S[/math] и целое число [math]s[/math]. Требуется выяснить, возможно ли выбрать подмножество [math]S' \subseteq S[/math] с суммой [math]s[/math]:

[math]\exists S' \subseteq S: \sum_{s_{i} \in S'}{s_{i}} = s[/math]

Доказательство NP-полноты

Для доказательства того, что задачи о сумме подмножества является NP-полной, необходимо доказать два факта:

  • Задачи о сумме подмножества [math]\in[/math] NP
  • Задачи о сумме подмножества [math]\in[/math] NPH

Доказательство принадлежности к NP

В качестве сертификата возьмем удовлетворяющее условию задачи множество [math]S'[/math] с суммой [math]s[/math]. Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов [math]S'[/math] в множество [math]S[/math].

Доказательство принадлежности к NPH

Сведем 3-CNF_Sat к задаче о сумме подмножества. Пусть задана 3-CNF формула [math]\phi[/math] от [math]n[/math] переменных [math]x_{i}[/math], состоящая из [math]k[/math] пар скобок [math]C_{i}[/math]. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию [math]f\!\!:\phi \to (S,s)[/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]s[/math] все разряды, соответствующие переменным, установим [math]1[/math], а оставшиеся сделаем равными [math]4[/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]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]S[/math] состоит из [math]2(n+k)[/math] десятичных чисел длиной [math](n+k)[/math] каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
  • Пусть формула [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]v_{i}[/math] в [math]S'[/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]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].

Пример сведения

Пусть исходная функция [math]\phi(x_{1} \ldots x_{4}) = (x_{1} \lor x_{2} \lor \neg x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4})[/math]. Пометим разряды следующим образом (слева направо): [math]x_{1},x_{2},x_{3},x_{4},C_{1},C_{2}[/math]. Тогда:

  • [math]v_{1} = 100010[/math]
  • [math]w_{1} = 100001[/math]
  • [math]v_{2} = 010011 = 10011[/math]
  • [math]w_{2} = 010000 = 10000[/math]
  • [math]v_{3} = 001000 = 1000[/math]
  • [math]w_{3} = 001010 = 1010[/math]
  • [math]v_{4} = 000101 = 101[/math]
  • [math]w_{4} = 000100 = 100[/math]
  • [math]d_{1} = 000010 = 10[/math]
  • [math]e_{1} = 000020 = 20[/math]
  • [math]d_{2} = 000001 = 1[/math]
  • [math]e_{2} = 000002 = 2[/math]
  • [math]s = 111144[/math]

[math]S = (\cup_{i=1 \ldots 4} v_{i}) \cup (\cup_{i=1 \ldots 4} w_{i}) \cup (\cup_{i=1 \ldots 2} d_{i}) \cup (\cup_{i=1 \ldots 2} e_{i})[/math]

Тогда набору значений [math]Y = (0,0,0,1):~ \phi(Y) = 1[/math] соответствует [math]S' = \{w_{1},~w_{2},~w_{3},~v_{4},~d_{1},~e_{1},~e_{2}\}[/math]. И действительно, [math]100001 + 10000 + 1010 + 101 + 10 + 20 + 2 = 111144[/math].

См. также

Источники информации

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms, 3rd Edition" — Издательство MIT Press, 2009. — 1292 с. — ISBN 978-0-262-03384-8 (англ.)
  • Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. — М.: Издательский дом "Вильямс", 2002. — 528 с. — ISBN 5-8459-0261-4 (рус.)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=NP-полнота_задачи_о_сумме_подмножества&oldid=53996»