54
правки
Изменения
опечатки
{{Задача
|definition = Дан набор из Дано множество <math>nS</math> целых чисел , содержащие <math>Sn</math> целых чисел и целое число <math>s</math>. Требуется выяснить, возможно ли выбрать подмножество <math>S' \subseteq S</math> с суммой <math>s</math>:
*<math>\mathrm{SSP} \in</math> [[NPH | <math>\mathrm{NPH}</math>]]
===Доказательство принадлежности к NP===
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов <math>S'</math> в множество <math>S</math>.
