18
правок
Изменения
Формулы --- принудительно png
</p>
==Доказательство NP-полноты==
Для доказательства того, что <math>\mbox{Knapsack~ problem } \in NPC</math> необходимо доказать два факта:*<math>\mbox{Knapsack~ problem } \in</math> [[NP|<math>NP</math>]] *<math>\mbox{Knapsack~ problem } \in</math> [[NPH|<math>NPH</math>]]
===Доказательство принадлежности к NP===
В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math>\{k_{j}\}</math>. Очевидно, оно удовлетворяет всем требованиям,
<p style="text-align:center;">
<math>f(\{s_{i}\},s) = (\{s_{i}\},\{s_{i}\},s,s)\,</math>
</p>
Очевидно, <math>f~</math> работает за полиномиальное от длины входа время. И удовлетворяет условиям [[Сводимость по Карпу|сводимости по Карпу]].
