Складність суми підмножини з кількома цілями - теорія складності, np-повна, підмножина-сума

Чи є наступна проблема в NP-Complete або P?

Вхідний: Набір S додатних цілих чисел {a1, a2, ..., an) та цілого додатного числа M
Питання: Чи існує підмножина S "з S така, що всі елементи в S" складають або M-1, M або M + 1.

Я здогадуюсь, що це у NP-Complete та пов’язане із сумою підмножин. Однак мені важко звести суму підмножини до цієї проблеми.

Відповіді:

Це NP-повно. Дано екземпляр суми підмножини

Знайдіть підмножину {x1, ... xn} із сумою X

Розгляньте наступний приклад проблеми

Знайти підмножину {4 * x1, 4 * x2, ..., 4 * xn} із сумою 4 * X, 4 * X-1 або 4 * X + 1

Розглядаючи подільність-на-4, ясно, щобудь-яка підмножина, яка дорівнює 4 * X, 4 * X-1 або 4 * X + 1, насправді повинна підраховувати до 4X. Але це тривіально дає вирішення проблеми вихідної підмножини, ділячи на 4.