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

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

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

Пусть дано множество целых чисел \( S = \{a_1, a_2, \dots, a_n\} \) и целевое число \( T \). Требуется определить, существует ли такое подмножество \( S' \subseteq S \), что: \[ \sum_{a_i \in S'} a_i = T. \] В классической формулировке числа могут быть как положительными, так и отрицательными, однако наиболее распространённый вариант — все числа положительные. Если \( T = 0 \), то задача сводится к поиску подмножества с нулевой суммой (zero-sum subset). Часто рассматривается также вариант, где требуется найти не только факт существования, но и само подмножество.

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

Задача о сумме подмножеств является NP-полной. Это означает, что она принадлежит классу NP (решение можно проверить за полиномиальное время, просуммировав элементы предложенного подмножества) и к ней можно свести любую другую задачу из класса NP за полиномиальное время. Доказательство NP-полноты было получено Ричардом Карпом в 1972 году в рамках его знаменитого списка 21 NP-полной задачи. Сведение обычно выполняется от задачи о выполнимости булевых формул (SAT) или от задачи о вершинном покрытии.

Несмотря на NP-полноту, для задачи существуют алгоритмы, работающие за псевдополиномиальное время, то есть время выполнения зависит не только от числа элементов \( n \), но и от величины чисел. В частности, если все числа и целевая сумма ограничены полиномом от \( n \), задача решается за полиномиальное время.

¶Методы решения

¶Алгоритм динамического программирования

Наиболее распространённый точный метод — динамическое программирование. Пусть \( dp[i][j] \) — булева величина, указывающая, можно ли получить сумму \( j \) из первых \( i \) элементов множества. Рекуррентное соотношение: \[ dp[i][j] = dp[i-1][j] \ \text{или} \ dp[i-1][j - a_i] \ (\text{если } j \geq a_i). \] База: \( dp[0][0] = true \), \( dp[0][j] = false \) для \( j > 0 \). Время работы — \( O(n \cdot T) \), память — \( O(T) \) при оптимизации по одномерному массиву. Недостаток: при больших \( T \) (например, \( T \approx 10^9 \)) алгоритм становится неприменимым из-за огромного объёма памяти и времени.

¶Метод meet-in-the-middle

Для случая, когда \( n \) невелико (до 40–50), эффективен метод «встреча посередине». Множество разбивается на две равные части. Для каждой части перебираются все возможные подмножества (их \( 2^{n/2} \)), вычисляются суммы. Затем суммы из первой части сортируются, и для каждой суммы из второй части проверяется, существует ли в первой части сумма, равная \( T - s_2 \). Время работы — \( O(2^{n/2} \cdot n) \), что значительно лучше полного перебора \( O(2^n) \).

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

Для больших \( n \) и \( T \) используются приближённые методы. Например, жадный алгоритм: элементы сортируются по убыванию, и последовательно добавляются, если сумма не превышает \( T \). Однако он не гарантирует нахождения точного решения. Существуют также полностью полиномиальные приближённые схемы (FPTAS), которые за время, полиномиальное от \( n \) и \( 1/\varepsilon \), находят решение с относительной ошибкой не более \( \varepsilon \).

¶Рандомизированные методы

В некоторых случаях применяются алгоритмы, основанные на случайной выборке подмножеств, например, метод Монте-Карло. Однако они не дают гарантии точности.

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

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

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

¶Применение

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

В 1978 году Ральф Меркл и Мартин Хеллман предложили криптосистему с открытым ключом на основе задачи о сумме подмножеств (ранцевая криптосистема Меркла — Хеллмана). Безопасность системы основывалась на NP-полноте задачи. Однако в 1982 году Ади Шамир показал, что конкретная реализация Меркла — Хеллмана уязвима к атакам, основанным на свойствах сверхвозрастающих последовательностей. С тех пор были предложены другие варианты, но большинство из них также были взломаны. Тем не менее, задача продолжает использоваться в теоретических исследованиях постквантовой криптографии.

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

В теории кодирования задача о сумме подмножеств применяется при анализе линейных кодов, в частности, для поиска кодовых слов минимального веса. Также она используется в алгоритмах декодирования по синдрому.

¶Оптимизация и планирование

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

¶Финансы и инвестиции

В портфельном анализе задача о сумме подмножеств может использоваться для подбора активов с заданной суммарной стоимостью или доходностью.

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

• Задача о сумме подмножеств является одной из первых задач, для которых была доказана NP-полнота. Она входит в список 21 NP-полной задачи Карпа.
• В 2010 году группа исследователей из Массачусетского технологического института (MIT) продемонстрировала, что для случайных множеств с большими числами задача может быть решена за полиномиальное время с высокой вероятностью, используя методы решёток.
• Существует вариант задачи, называемый «задача о сумме подмножеств с ограничением на количество элементов», где требуется найти подмножество ровно из \( k \) элементов.
• В 2018 году была опубликована работа, показывающая, что квантовые компьютеры могут решать задачу о сумме подмножеств с квадратичным ускорением по сравнению с классическими алгоритмами, но не экспоненциальным.

¶Источники

• Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
• Karp, R. M. (1972). «Reducibility Among Combinatorial Problems». In Complexity of Computer Computations, Plenum Press.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Shamir, A. (1982). «A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem». Proceedings of the 23rd Annual Symposium on Foundations of Computer Science.
• Horowitz, E., Sahni, S. (1974). «Computing partitions with applications to the knapsack problem». Journal of the ACM, 21(2), 277–292.