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

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

В Задаче о сумме помножества (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]