Złożoność wariantu sumy częściowej

Czy ten wariant problemu sumy częściowej jest łatwy / znany?

Biorąc pod uwagę liczbę całkowitą oraz zestaw dodatnich liczb całkowitych tak, że każdy ma co najwyżej bity ustawione na ( ); czy jest podzestaw taki, że suma jego elementów jest równa ? $m$ $A = \{x_1, x_2, ..., x_n\}$ $x_i$ $k=2$ $1$ $x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$ $A' \subseteq A$ $m$

Czy to jest ? Czy nadal jest -kompletny? $\sf{P}$ $\sf{NP}$

A jeśli każdy ma co najwyżej bity ustawione na ? Dla problem jest trywialny. $x_i$ $k=3$ $1$ $k=1$

complexity-theory reference-request decision-problem

— Vor
źródło

Nadal jest -kompletny, nawet dla . Biorąc pod uwagę sumę podzbioru, możemy ją przekształcić w ten wariant, dzieląc liczby i dodając dodatkowe bity. $\sf{NP}$ $k=2$

Po pierwsze, suma wszystkich liczb w zadaniu będzie mniejsza niż dla pewnej wartości . $2^m$ $m$

Teraz weźmy liczbę z pierwotnego problemu, który ma ustawione bity . Podzielimy tę liczbę na liczby z dokładnie 2 bitami ustawionymi tak, aby suma tych liczb wynosiła . Możemy to zrobić rekurencyjnie, znajdując które sumują się do pierwszych plus i liczby, które zsumuj do ostatnich bitów plus . $n$ $k$ $k$ $n+2^{k+m}$ $\lceil{k}\rceil$ $\lceil{k}\rceil$ $2^{k+m-1}$ $\lfloor{k}\rfloor$ $\lfloor{k}\rfloor$ $2^{k+m-1}$

Oprócz tej liczby dodamy również do problemu liczbę . Rozwiązanie musi zawierać tę liczbę lub wszystkie wcześniej zbudowane liczby . Jeśli pierwotną wartością docelową było nową wartością docelową będzie . $2^{k+m}$ $k$ $t$ $t+2^{k+m}$

Jeśli pierwotny problem miał więcej niż jedną liczbę, możemy powtórzyć ten proces, przyjmując dla nowej wartości . $k+m+1$ $m$

Są tylko dwa sposoby ustawienia bitu w pozycji : odpowiedź może zawierać liczbę lub wszystkie liczby które sumują się do . Więc zmniejszyliśmy sumę podzbioru do twojego wariantu sumy podzbiorów. $k+m$ $2^{k+m}$ $k$ $n+2^{k+m}$

Jako przykład weźmy z wartością docelową . Problem ten można zakodować jako przedstawiony tu wariant sumy podzbioru, przyjmując następujące liczby binarne: ${\{2,3,5\}}$ $7$

2 zostanie zamapowany na i . (Użycie dodatkowego bitu nie jest tu absolutnie konieczne). $0100\ 1$ $0000\ 1$

3 zostanie zamapowany na i $1000\ 00\ 1, 0100\ 00\ 1$ $0000\ 00\ 01$

5 zostanie zmapowany na i . $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ $0000\ 00\ 000\ 01$

Nowa wartość docelowa to . $1110\ 10\ 010\ 01$

Jeśli problem pierwotny jest reprezentowany przez bitów, problem przekształcony ma co najwyżej bitów. Pierwotny problem będzie miał najwyżej liczb, z których każda ma najwyżej bitów, więc suma ich wszystkich jest również O (n). Przekształcony problem będzie miał liczby (ponieważ każda liczba bitowa jest podzielona na bitowe liczby, przy czym ich długość wynosi co najwyżej ponieważ używamy dodatkowych bitów dla każda liczba. Zatem całkowity rozmiar transformowanego problemu wynosi bitów. $n$ $O(n^4)$ $O(n)$ $O(n)$ $O(n^2)$ $n$ $n+1$ $2$ $O(n^2)$ $n$ $O(n^4)$

— Tom van der Zanden
źródło

czy jesteś pewien, że kodowanie nie prowadzi do wykładniczego rozmiaru działającej taśmy?

— Vor

Nie, myślę, że przekształcony problem ma charakter kwartalny. Jeśli wejście ma n bitów, wówczas jest co najwyżej n liczb z ustawionymi n bitami. Więc w przekształconym problemie będą liczby O (n ^ 2) (ponieważ liczba k-bitów jest podzielona na liczby k + 1). Każda liczba ma (2n) bitów, aby pomieścić maksymalną sumę plus n bitów dla każdej z n liczb w pierwotnym problemie. Zatem każda liczba będzie miała bity O (2n + n ^ 2), co daje w sumie bity O (n ^ 4).

— Tom van der Zanden

@TomvaderZanden: Dodałem zdjęcie twojej redukcji w pytaniu; zobaczę, czy poprawnie to zinterpretowałem

— Vor

@TomvaderZanden: dzisiaj patrzę na swojej redukcji ponownie, ale nie jest jasne, w jaki sposób z dowolnej liczby o ustawić bity można podzielić ją na 2-bitowych liczb gdzie „najwyższy” część sum . Załóżmy, że masz numer z bitów ustawionych; potrzebujesz 13 2-bitowych liczb, ale 13 to 1101 i nie możesz „zakryć” go dwucyfrową liczbą (twój przykład działa, ponieważ dla 3 i 5 k = 2). Myślę, że można to łatwo naprawić, jeśli użyjesz innego wysokiego bitu dla każdej z 2-bitowych liczb; sumują się do 01111 ... 1, a następnie dodajesz manekina 0000 ... 1, który pozwoli na sumę .

n

$n$

k

$k$

k

$k$

2^{k}

$2^k$

n

$n$

k = 13

$k=13$

k

$k$

2^{k}

$2^k$

— Vor

Jest to nieco niejasne, ale z pewnością możliwe jest zastosowanie procedury „indukcyjnej”. Tak naprawdę nie potrzebujesz bitów, potrzebujesz tylko . Jeśli chcesz znaleźć 13 liczb 1-bitowych, które sumują się do , musisz znaleźć 6 liczb, które sumują się do i 7, które również sumują się do . Możemy wziąć co faktycznie sumuje się do .

k

$k$

c e i l (\log k)

$ceil(\log k)$

2^{4}

$2^4$

2^{3}

$2^3$

2^{3}

$2^3$

10 * 2^{0} + 3 * 2^{1}

$10*2^0+3*2^1$

2^{4}

$2^4$

— Tom van der Zanden,

To informacje wyodrębnione z pytania Vora.

Dla $k \geq 3$ problem pozostaje NP-zupełny. Znalazłem szybką redukcję z monotonicznego X-SAT ( patrz schemat redukcji tutaj ).

Problem pozostaje NP-zupełny, nawet jeśli $k = 2$ zobacz szczegóły Toma w odpowiedzi. Oto mała reprezentacja jego redukcji z SUBSET SUM:

wprowadź opis zdjęcia tutaj

— Juho
źródło