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

Задача о сумме подмножества (англ. subset sum problem) — это классическая задача комбинаторики и теории вычислительной сложности, заключающаяся в определении, существует ли такое непустое подмножество заданного множества целых чисел, сумма элементов которого равна заданному целевому числу. Задача является NP-полной, что означает отсутствие известного эффективного (полиномиального) алгоритма для её решения в общем случае, однако для частных случаев (например, при малых значениях чисел или при использовании приближённых методов) существуют практические алгоритмы.

Формальная постановка

Пусть дано множество целых чисел \( S = \{a_1, a_2, \dots, a_n\} \) и целевое число \( T \). Требуется найти такое подмножество \( S' \subseteq S \), что сумма элементов \( S' \) равна \( T \). В классической формулировке подмножество должно быть непустым, хотя в некоторых вариантах допускается пустое подмножество с суммой 0. Если \( T = 0 \), то задача решается тривиально — пустое подмножество даёт сумму 0, но в большинстве постановок требуется непустое подмножество.

Задача может быть как задачей разрешения (существует ли подмножество), так и задачей поиска (найти само подмножество). В вычислительной сложности обычно рассматривается первый вариант.

История и происхождение

Задача о сумме подмножества впервые была сформулирована в середине XX века в контексте криптографии и теории кодирования. В 1978 году она была включена в список 21 NP-полной задачи, опубликованный Ричардом Карпом, что подтвердило её фундаментальную роль в теории сложности. Одним из ранних практических приложений стала криптосистема с открытым ключом на основе ранца (knapsack cryptosystem), предложенная Ральфом Мерклем и Мартином Хеллманом в 1978 году. Однако эта система была взломана в 1984 году Ади Шамиром, что показало уязвимость некоторых вариантов задачи.

Классификация и варианты

По типу чисел

• Целочисленная задача: все числа и целевое значение — целые числа. Наиболее распространённый вариант.
• Задача с натуральными числами: числа положительны. Часто встречается в приложениях.
• Задача с произвольными целыми: допускаются отрицательные числа. В этом случае задача может быть сведена к положительному случаю путём сдвига.
• Задача с булевыми числами: числа равны 0 или 1. Тривиальный случай, сводящийся к проверке наличия единицы.

По количеству решений

• Задача разрешения: существует ли хотя бы одно подмножество.
• Задача подсчёта: сколько различных подмножеств дают нужную сумму.
• Задача поиска: найти одно или все подмножества.

По ограничениям

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

Вычислительная сложность

Задача о сумме подмножества является NP-полной, что было доказано Карпом в 1972 году. Это означает, что:

1. Задача принадлежит классу NP: данное подмножество можно проверить за полиномиальное время, сложив его элементы.
2. Любая задача из класса NP может быть сведена к задаче о сумме подмножества за полиномиальное время.

Таким образом, существование полиномиального алгоритма для задачи о сумме подмножества означало бы, что P = NP, что является одной из нерешённых проблем современной информатики.

Для частных случаев задача может быть решена за полиномиальное время. Например, если все числа ограничены полиномом от \( n \), то можно использовать динамическое программирование с временной сложностью \( O(n \cdot T) \), где \( T \) — целевое значение. Однако при больших \( T \) (экспоненциально больших относительно \( n \)) этот метод становится непрактичным.

Алгоритмы решения

Полный перебор

Наивный алгоритм заключается в переборе всех подмножеств множества \( S \). Количество подмножеств равно \( 2^n \), поэтому временная сложность составляет \( O(2^n) \). Для \( n = 30 \) это уже около миллиарда вариантов, что делает метод неприменимым для больших \( n \).

Динамическое программирование

Для задачи с целыми неотрицательными числами можно использовать метод динамического программирования. Строится таблица \( dp[i][j] \), где \( i \) — количество рассмотренных элементов, \( j \) — возможная сумма. Значение \( dp[i][j] \) равно true, если можно получить сумму \( j \) из первых \( i \) элементов. Рекуррентное соотношение: \[ dp[i][j] = dp[i-1][j] \lor dp[i-1][j - a_i] \] с начальным условием \( dp[0][0] = true \). Временная сложность — \( O(n \cdot T) \), где \( T \) — целевое число. Память — \( O(T) \) при оптимизации.

Недостаток: при больших \( T \) (например, \( T = 10^9 \)) таблица становится огромной, и метод неприменим.

Встреча в середине (Meet-in-the-Middle)

Этот метод позволяет решать задачу для \( n \) до 40–50 за разумное время. Идея: разбить множество на две части примерно равного размера. Для каждой части перебрать все подмножества (их \( 2^{n/2} \)) и записать суммы. Затем отсортировать суммы второй части и для каждой суммы первой части проверить, есть ли в второй части сумма, дополняющая до \( T \). Временная сложность — \( O(2^{n/2} \log 2^{n/2}) \approx O(2^{n/2} \cdot n) \). Память — \( O(2^{n/2}) \).

Приближённые алгоритмы

Для больших \( n \) и больших чисел часто используют приближённые методы, такие как жадный алгоритм (сортировка по убыванию и последовательное добавление элементов, не превышающих целевую сумму) или алгоритмы на основе случайного поиска. Эти методы не гарантируют нахождение точного решения, но могут дать приемлемый результат за полиномиальное время.

Псевдополиномиальные алгоритмы

Алгоритм динамического программирования является псевдополиномиальным, так как его сложность зависит от численного значения \( T \), а не только от длины входа. Если \( T \) мало, алгоритм эффективен; если \( T \) велико, он экспоненциален по длине входа.

Применение

Криптография

Исторически задача о сумме подмножества использовалась в криптосистеме Меркля — Хеллмана, основанной на ранце. Хотя исходная система была взломана, более сложные варианты (например, с использованием модульной арифметики) продолжают изучаться. В современной криптографии задача используется в некоторых схемах электронной подписи и протоколах с нулевым разглашением.

Теория кодирования

Задача встречается при построении кодов, исправляющих ошибки, и в алгоритмах декодирования. Например, в кодах Рида — Соломона и свёрточных кодах.

Комбинаторная оптимизация

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

Машинное обучение и анализ данных

В некоторых задачах выбора признаков (feature selection) и в методах разреженного представления данных (sparse coding) возникает необходимость найти подмножество признаков, сумма которых аппроксимирует заданный вектор.

Игры и головоломки

Задача лежит в основе многих логических игр, таких как «Судоку» (в некоторых интерпретациях) и головоломок с числами. Также используется в генерации тестовых данных для проверки алгоритмов.

Связь с другими задачами

Задача о сумме подмножества тесно связана с задачей о рюкзаке (0-1 knapsack problem), где каждый элемент имеет не только вес (сумму), но и ценность, и требуется максимизировать ценность при ограничении на вес. Задача о сумме подмножества является частным случаем задачи о рюкзаке, когда ценность каждого элемента равна его весу, а целевая сумма равна заданному весу.

Также задача сводится к задаче о разбиении (partition problem), где требуется разделить множество на два подмножества с равными суммами. Задача о разбиении является частным случаем задачи о сумме подмножества при \( T = \frac{1}{2} \sum_{i=1}^n a_i \).

Интересные факты

• Задача о сумме подмножества является одной из немногих NP-полных задач, для которых существуют эффективные псевдополиномиальные алгоритмы при малых значениях чисел.
• В 1990-х годах были разработаны квантовые алгоритмы для задачи, но они не дают экспоненциального ускорения в общем случае.
• Существует вариант задачи, называемый «задача о сумме подмножества с ограничением на количество элементов», который также NP-полон.
• В российской научной литературе задача часто рассматривается в контексте теории расписаний и дискретной оптимизации.

Источники

• Карп, Р. (1972). «Reducibility Among Combinatorial Problems». В книге: Miller, R. E.; Thatcher, J. W. (eds.). Complexity of Computer Computations. Plenum Press.
• Меркль, Р.; Хеллман, М. (1978). «Hiding information and signatures in trapdoor knapsacks». IEEE Transactions on Information Theory.
• Шамир, А. (1984). «A polynomial-time algorithm for breaking the basic Merkle–Hellman cryptosystem». IEEE Transactions on Information Theory.
• Кормен, Т.; Лейзерсон, Ч.; Ривест, Р.; Штайн, К. (2009). «Алгоритмы: построение и анализ». 3-е издание. Глава 34.5: NP-полнота задачи о сумме подмножества.
• Гэри, М.; Джонсон, Д. (1979). «Computers and Intractability: A Guide to the Theory of NP-Completeness». W. H. Freeman.