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

Материал из Викиконспекты
Перейти к: навигация, поиск
(структура д-ва + начато)
(часть доказательства)
Строка 5: Строка 5:
 
</p>
 
</p>
 
==Доказательство NP-полноты==
 
==Доказательство NP-полноты==
−
Для доказательства того, что <math>Subset~ sum~ problem \in NPC</math> необходимо доказать два факта:
+
Для доказательства того, что <math>\mbox{Subset sum problem} \in NPC</math> необходимо доказать два факта:
−
*<math>Subset~ sum~ problem \in</math> [[NP|<math>NP</math>]]  
+
*<math>\mbox{Subset sum problem} \in</math> [[NP|<math>NP</math>]]  
−
*<math>Subset~ sum~ problem \in</math> [[NPH|<math>NPH</math>]]  
+
*<math>\mbox{Subset sum problem} \in</math> [[NPH|<math>NPH</math>]]  
 
===Доказательство принадлежности к NP===
 
===Доказательство принадлежности к NP===
 
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>\{s_{k_{j}}\}</math>. Очевидно, оно удовлетворяет всем требованиям,
 
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>\{s_{k_{j}}\}</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>
Строка 17: Строка 17:
 
Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>\{s_{i}\}</math>. Также создадим число <math>s</math> длиной <math>n+k</math> цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок.
 
Для каждой переменной <math>x_{i}</math> и каждой пары скобок <math>C_{j}</math> создадим по два числа в десятичной системе счисления, каждое длиной <math>n+k</math> цифр. Эти числа образуют <math>\{s_{i}\}</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>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>\{s_{i}\}</math> состоит из <math>2(n+k)</math> десятичных чисел длиной <math>(n+k)</math> каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
 +
*Пусть формула <math>\phi</math> выполнима, то есть существует набор значений <math>\{y_{i}\}:~\phi(y_{1},...,y_{n})=1 </math>. Тогда в полученном множестве <math>\{s_{i}\}</math> существует подмножество с суммой <math>s</math>.
 +
===Пример сведения===

Версия 18:18, 9 марта 2010

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

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

[math]\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s[/math]

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

Для доказательства того, что [math]\mbox{Subset sum problem} \in NPC[/math] необходимо доказать два факта:

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

В качестве сертификата возьмем удовлетворяющее условию задачи множество [math]\{s_{k_{j}}\}[/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\!\!:(\{x_{i}\},\{C_{i}\}) \to (\{s_{i}\},s)[/math].

Построение сводящей функции

Для каждой переменной [math]x_{i}[/math] и каждой пары скобок [math]C_{j}[/math] создадим по два числа в десятичной системе счисления, каждое длиной [math]n+k[/math] цифр. Эти числа образуют [math]\{s_{i}\}[/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]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]\{s_{i}\}[/math] состоит из [math]2(n+k)[/math] десятичных чисел длиной [math](n+k)[/math] каждое, выставление каждого разряда занимает полиномиальное время. Таким образом, сведение выполняется за полиномиальное время.
  • Пусть формула [math]\phi[/math] выполнима, то есть существует набор значений [math]\{y_{i}\}:~\phi(y_{1},...,y_{n})=1 [/math]. Тогда в полученном множестве [math]\{s_{i}\}[/math] существует подмножество с суммой [math]s[/math].

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=NP-полнота_задачи_о_сумме_подмножества&oldid=43»