Задача о сумме подмножеств

Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.

Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.

Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество { −3, −2, 5} дает в сумме ноль.

Задача является NP-полной.

Эквивалентной является задача нахождения подмножества, сумма элементов которого равна некоторому заданному числу s.

Задачу о сумме подмножеств также можно рассматривать как некоторый специальный случай задачи о ранце.

Интересным случаем задачи о суммировании подмножеств является задача о разбиении, в которой s равна половине суммы всех элементов множества.

Источник: Википедия