NP-полнота задачи о сумме подмножества — различия между версиями
Miron (обсуждение | вклад) (добавлена формулировка) |
Miron (обсуждение | вклад) (структура д-ва + начато) |
||
| Строка 1: | Строка 1: | ||
==Формулировка задачи== | ==Формулировка задачи== | ||
| − | В '''Задаче о сумме | + | В '''Задаче о сумме подмножества''' (Subset sum problem) входными данными являются набор из <math>n</math> целых чисел <math>s_{i}</math> и целое число <math>s</math>. Требуется выяснить, возможно ли выбрать такое подмножество из <math>\{s_{i}\}</math> с суммой <math>s</math>: |
<p style="text-align:center;"> | <p style="text-align:center;"> | ||
<math>\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s</math> | <math>\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s</math> | ||
</p> | </p> | ||
==Доказательство NP-полноты== | ==Доказательство NP-полноты== | ||
| + | Для доказательства того, что <math>Subset~ sum~ problem \in NPC</math> необходимо доказать два факта: | ||
| + | *<math>Subset~ sum~ problem \in</math> [[NP|<math>NP</math>]] | ||
| + | *<math>Subset~ sum~ problem \in</math> [[NPH|<math>NPH</math>]] | ||
| + | ===Доказательство принадлежности к NP=== | ||
| + | В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>\{s_{k_{j}}\}</math>. Очевидно, оно удовлетворяет всем требованиям, | ||
| + | налагаемым на сертификат. | ||
| + | ===Доказательство принадлежности к NPH=== | ||
| + | Сведем [[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_{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>. | ||
| + | ====Корректность сводящей функции==== | ||
Версия 12:35, 9 марта 2010
Содержание
Формулировка задачи
В Задаче о сумме подмножества (Subset sum problem) входными данными являются набор из целых чисел и целое число . Требуется выяснить, возможно ли выбрать такое подмножество из с суммой :
Доказательство NP-полноты
Для доказательства того, что необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем удовлетворяющее условию задачи множество . Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат.
Доказательство принадлежности к NPH
Сведем 3-CNF_Sat к задаче о о сумме подмножества. Пусть задана 3-CNF формула от переменных , состоящая из пар скобок . Построим сводящую функцию .
Построение сводящей функции
Для каждой переменной и каждой пары скобок создадим по два числа в десятичной системе счисления, каждое длиной цифр. Эти числа образуют . Также создадим число длиной цифр. Присвоим каждому разряду полученных чисел (одинаковую для всех чисел) метку, соответствующую либо переменной, либо паре скобок. Метки, соответствующие парам скобок, присвоены младшим разрядам чисел.
- в числе все разряды, соответствующие переменным, установим , а оставшиеся сделаем равными ;
- каждой переменной соответствуют два числа: и .
