18
правок
Изменения
добавлена формулировка
==Формулировка задачи==
В '''Задаче о сумме помножества''' (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;">
<math>\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s</math>
</p>
==Доказательство NP-полноты==
В '''Задаче о сумме помножества''' (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;">
<math>\exist \{k_{j}\} \subseteq (1..n): \sum_{i \in k_{j}}{s_{i}} = s</math>
</p>
==Доказательство NP-полноты==
