Он все еще полон, даже для k = 2 . Учитывая экземпляр суммы подмножеств, мы можем преобразовать его в этот вариант, разделив числа и добавив несколько дополнительных битов.NPk=2
Во-первых, сумма всех чисел в задаче будет меньше для некоторого значения m .2mm
Теперь давайте возьмем число из исходной задачи, для которой установлено k битов. Мы разделим это число на k чисел с точно установленными 2 битами так, чтобы сумма этих чисел была n + 2 k + m . Мы можем сделать это рекурсивно, найдя ⌈ k ⌉ чисел, которые суммируют до первых ⌈ k ⌉ битов плюс 2 k + m - 1 и ⌊ k ⌋ чисел, которые суммируют до последних ⌊ k ⌋ битов плюс 2 knkkn+2k+m⌈k⌉⌈k⌉2k+m−1⌊k⌋⌊k⌋ .2k+m−1
В дополнение к этому числу мы также добавим к задаче число . Решение должно содержать либо это число, либо все числа k, построенные ранее. Если исходным целевым значением было t, новым целевым значением будет t + 2 k + m .2к + мКTт + 2к + м
Если исходная задача имела более одного числа, мы можем повторить этот процесс, взяв для нового значения m .k+m+1m
Существует только два способа установки бита в позиции : ответ может содержать число 2 k + m или все числа k, которые в сумме составляют n + 2 k + m . Таким образом, мы уменьшили сумму подмножества до вашего варианта суммы подмножеств.k+m2k+mkn+2k+m
В качестве примера возьмем с целевым значением 7 . Эта проблема может быть закодирована как вариант суммы подмножеств, представленный здесь, взяв следующие двоичные числа:{2,3,5}7
2 сопоставляется с и 0000 1 . (Использование дополнительного бита здесь не обязательно).0100 10000 1
3 сопоставляется с и 0000 00 011000 00 1,0100 00 10000 00 01
5 сопоставляется с и 0000 00 000 01 .1000 00 000 1,0010 00 000 10000 00 000 01
Новое целевое значение станет .1110 10 010 01
Если исходная задача представлена битами, то преобразованная проблема имеет не более O ( n 4 ) битов. Исходная задача будет иметь не более O ( п ) чисел каждый с в основном O ( п ) бит, так что сумма всех из них также O (п). Преобразованная задача будет иметь O ( n 2 ) чисел (поскольку каждое n- разрядное число разбивается на n + 1 2 -битные числа, причем их длина не превышает O ( n 2 )nO(n4)O(n)O(n)O(n2)nn+1 2O(n2)так как мы используем дополнительных бит для каждого числа. Таким образом, общий размер преобразованной задачи составляет O ( n 4 ) бит.nO(n4)
Это информация, извлеченная из вопроса Вором.
При задача остается NP-полной. Я нашел быстрое сокращение от монотонного X-SAT ( см. Схему сокращения здесь ).k≥3
Проблема остается NP-полной, даже если , подробности см. В ответе Тома. Вот небольшое представление о его сокращении от SUBSET SUM:k=2
источник