Сложность варианта подмножества суммы

9

Является ли этот вариант проблемы подмножества простым / известным?

Принимая во внимание целого , и множество положительных целых чисел А = { х 1 , х 2 , . , , , x n } , так что каждый x i имеет не более k = 2 битов, установленных в 1 ( x i = 2 b i 1 + 2 b i 2 ,мAзнак равно{Икс1,Икс2,,,,,ИксN}ИксяКзнак равно21 ); существует ли подмножество A A такое, что сумма его элементов равна m ?Иксязнак равно2бя1+2бя2,бя1,бя20A'Aм

Это в ? Это все еще N P- полный?пNп

И если каждый имеет самое большее k = 3 бита, установленного в 1 ? Для k = 1 задача тривиальна.ИксяКзнак равно31Кзнак равно1

Вор
источник

Ответы:

8

Он все еще полон, даже для k = 2 . Учитывая экземпляр суммы подмножеств, мы можем преобразовать его в этот вариант, разделив числа и добавив несколько дополнительных битов.NпКзнак равно2

Во-первых, сумма всех чисел в задаче будет меньше для некоторого значения m .2мм

Теперь давайте возьмем число из исходной задачи, для которой установлено k битов. Мы разделим это число на k чисел с точно установленными 2 битами так, чтобы сумма этих чисел была n + 2 k + m . Мы можем сделать это рекурсивно, найдя k чисел, которые суммируют до первых k битов плюс 2 k + m - 1 и k чисел, которые суммируют до последних k битов плюс 2 knkkn+2k+mkk2k+m1kk .2k+m1

В дополнение к этому числу мы также добавим к задаче число . Решение должно содержать либо это число, либо все числа k, построенные ранее. Если исходным целевым значением было t, новым целевым значением будет t + 2 k + m .2К+мКTT+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)

Том ван дер Занден
источник
Вы уверены, что кодировка не приводит к экспоненциальному размеру рабочей ленты?
Вор
Нет, я думаю, что трансформированная проблема является квартирой по размеру. Если на входе имеется n битов, то существует не более n чисел, в каждом из которых установлено n битов. Таким образом, в преобразованной задаче будет O (n ^ 2) чисел (поскольку k-битное число разбивается на k + 1 числа). Каждое число имеет длину (2n) битов, чтобы вместить максимальную сумму плюс n битов для каждого из n чисел в исходной задаче. Таким образом, каждое число будет иметь O (2n + n ^ 2) битов, в общей сложности O (n ^ 4) битов.
Том ван дер Занден
@TomvaderZanden: я добавил фото вашего сокращения в вопросе; посмотреть, правильно ли я это понял
Vor
@TomvaderZanden: сегодня я снова смотрю на ваше сокращение, но неясно, как из произвольного числа с набором k битов вы можете разделить его на k 2-битных чисел, где «старшая» часть составляет 2 k . Предположим, у вас есть число n с установленным k = 13 битов; вам нужно 13 2-битных чисел, но 13 - это 1101, и вы не можете "покрыть" его двухбитным числом (ваш пример работает, потому что для 3 и 5 k = 2). Я думаю, что это легко исправить, если вы используете разные старшие биты для каждого из k 2-битных чисел; они будут суммироваться до 01111 ... 1, затем вы добавляете фиктивный 0000 ... 1, который позволит сумме 2 k .nkk2knk=13k2k
Вор
Это немного расплывчато, но, безусловно, это возможно при использовании «индуктивной» процедуры. На самом деле вам не нужно бит, вам нужно только c e i l ( log k ) . Если вы хотите найти 13 1-битных чисел с суммой до 2 4 , то вам нужно найти 6 чисел с суммой до 2 3 и 7, которые также суммируются до 2 3 . Мы можем взять 10 2 0 + 3 2 1, который действительно суммирует до 2 4 . kceil(logk)2423231020+32124
Том ван дер Занден
0

Это информация, извлеченная из вопроса Вором.

При задача остается NP-полной. Я нашел быстрое сокращение от монотонного X-SAT ( см. Схему сокращения здесь ).k3

Проблема остается NP-полной, даже если , подробности см. В ответе Тома. Вот небольшое представление о его сокращении от SUBSET SUM:k=2

введите описание изображения здесь

Юхо
источник