Задача про суму підмножини

Складність проблеми суми підмножин залежність двох параметрів: N — кількості змінних рішення, і P — точності вирішення проблеми (вказується як кількість двійкових розрядів, що потрібні, щоб сформулювати завдання). (Примітка: тут літери N і P не мають нічого спільного з класом задач NP.)

Складність відомих алгоритмів експоненціально залежить від меншого з двох параметрів N і P. Таким чином, проблема є складнішою, якщо N і P мають один і той же порядок. Все спрощується тільки тоді, якщо N або P будуть дуже маленькими.

Якщо N (кількість змінних) є невеликою, то можна знайти рішення повним перебором варіантів. Якщо P (число розрядів) є невеликим фіксованим числом, то існують алгоритми динамічного програмування, які можуть вирішити це точно.

Ефективні алгоритми для випадків малих N і малих P наведено нижче.

Є кілька способів, щоб вирішити суму підмножини у експоненціальний час в N. Найпростіший спосіб — перебирати всі підмножини з N чисел і для кожної з них перевіряти, чи отримано потрібну суму. Час виконання буде порядку O(2^NN), так як всього 2^N підмножин і, щоб перевірити кожну підмножину потрібно додати N елементів.

Більш оптимальний алгоритм має час роботи О(2^N/2). Цей алгоритм ділить всі множини з N елементів на дві підмножини по N/2 елементів у кожній. Для кожної з цих підмножин будується набір сум всіх 2^N/2 можливих підмножин. Обидва списки сортуються. Якщо використовувати просте порівняння для сортування, отримаємо час О(2^N/2N). Однак можна застосувати метод злиття. Маючи суму для k елементів, додамо (k + 1) елемент і отримаємо два сортованих списків, потім зробимо злиття списків (без доданого елемента і з доданим елементом). Тепер є список сум для (k + 1) елементів, і для його створення було потрібно O(2^k) часу. Таким чином, кожен список може бути створений за час O(2^N/2). Маючи два відсортованих списків, алгоритм може перевірити, чи можуть дати суми елементів першого і другого списку значення s за час O(2^N/2). Для цього алгоритм переглядає перший список в порядку спадання (починаючи з найбільшого елемента), а другий список в порядку зростання (починаючи з найменшого елемента). Якщо сума поточних елементів більше s, алгоритм пересувається до наступного елемента в першому списку, а якщо менше s, до наступного елемента в другому списку. Якщо він менше s, то алгоритм переходить до наступного елементу другого масиву. Якщо ж сума дорівнює s, рішення знайдено і алгоритм зупиняється. Еліс Горовіц (англ. Ellis Horowitz) і Сартаж Сахні (англ. Sartaj Sahni) вперше опублікували цей алгоритм у 1972 році[4].

Завдання може бути розв'язане за допомогою динамічного програмування у псевдополіноміальний час. Нехай дана послідовність чисел

x₁, …, x_N

і необхідно знайти, чи існує непорожня підмножина цієї послідовності з нульовою сумою елементів. Нехай A — сума від'ємних елементів і B — сума додатних. Визначимо булеву функцію Q(i, s), що приймає значення Так, якщо існує непорожня підмножина елементів x₁, …, x_i, що дає в сумі s, і Ні в іншому випадку.

Тоді рішенням завдання буде значення Q(N, 0).

Зрозуміло, що Q(i, s) = Ні, якщо s < A або s > B, так що ці значення немає необхідності обчислювати або зберігати. Створимо масив, що містить значення Q(i, s) для 1 ≤ i ≤ N і A ≤ s ≤ B.

Масив може бути заповнений за допомогою простої рекурсії. Спочатку, для A ≤ s ≤ B, покладемо

Q(1, s) := (x₁ == s).

де == — це булева функція, яка повертає Так, якщо х₁ дорівнює s, і Ні в іншому випадку.

Наразі для i = 2, …, N, покладемо

Q(i, s) := Q(i − 1, s) чи (x_i == s) чи Q(i − 1, s − x_i),  for A ≤ s ≤ B.

Для кожного присвоєння значення Q в правій частині вже відомо, оскільки або воно занесено в таблицю попередніх значень i, або Q(i − 1,s − x_i) = Ні при s − x_i < A чи s − x_i > B. Таким чином, повний час арифметичних операцій становить O(N(B − A)). Наприклад, якщо всі значення порядку O(N^k) для деякого k, то необхідно час O(N^k+2).

Алгоритм легко модифікується для знаходження нульової суми, якщо така є.

Алгоритм не вважається поліноміальним, оскільки B − A не є поліноміальним від розміру задачі, в ролі якого виступає число біт. Алгоритм поліноміальний від значень A та B, а вони експоненціально залежать від числа біт.

Для випадку, коли всі x_i позитивні і обмежені константою С, Пісінжер знайшов лінійний алгоритм зі складністю O(NC) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним)[5]. У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю ${\displaystyle {\tilde {O}}(s{\sqrt {N}})}$, де ${\displaystyle s}$ — сума, яку потрібно знайти.[6]

Існує версія наближеного апроксимаційного алгоритму, що дає для заданої множини N елементів x₁, x₂, …, x_N і числа s наступний результат:

• Так, якщо існує підмножина з сумою елементів s;
• Ні, якщо немає підмножини, що має суму елементів між (1 − c)s і s для деякого малого c > 0;
• Будь-яка відповідь (так чи ні), якщо існує підмножина з сумою елементів між (1 − c)s і s, але ця сума не дорівнює  s.

Якщо всі елементи невід'ємні, алгоритм дає рішення за поліноміальний час, який залежить від N і 1/с.

Алгоритм забезпечує рішення вихідної задачі знаходження суми підмножин у разі, якщо числа малі (і, знову ж таки, невід'ємні). Якщо будь-яка сума чисел має не більше P біт, то рішення задачі c = 2^−P еквівалентно знаходженню точного рішення. Таким чином, поліноміальний наближений алгоритм стає точним із часом виконання, залежать поліноміально від N та 2^P (тобто експоненціально від P).

Алгоритм наближеного розв'язання задачі про суму множин працює таким чином:

Створюємо список S, що спочатку складається з одного елемента 0.
Для всіх i від 1 до N виконаємо наступні дії
   Створюємо список T, що складається з xi + y для всіх y з S
   Створюємо список U, рівний об'єднанню T і S
   Сортуємо U
   Спустошуємо S
   Нехай y – найменший елемент U
   Внесемо y в S
   Для всіх елементів z з U, перебираючи їх у порядку зростання, виконаємо
      //тим самим ми виключаємо близькі значення і
      //відкидаємо значення, що перевищують s
     Якщо y + cs/N < z ≤ s, покладемо y = z і внесемо z у список S 
Якщо s містить число між (1 − c)s і s, виводиться Так, у противному випадку - Ні

Алгоритм має поліноміальний час роботи, оскільки розмір списків S, T та U завжди поліноміально залежить від N і 1/c і, отже, всі операції над ними виконуватимуться за поліноміальний час. Зберегти розмір поліноміальних списків дозволяє крок виключення близьких значень, на якому додається елемент z у список S, тільки якщо він більше попереднього на cs/N і не більше s, що забезпечує включення не більш N/c елементів в список.

Алгоритм коректний, оскільки кожен крок дає сумарну помилку не більше  cs/N і N кроків разом дадуть помилку, яка не перевершує cs.

• 3SUM
• Ранцева криптосистема Меркле — Геллмана

• Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. с. 1296. ISBN 978-617-684-239-2.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.