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

9

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 ?mA={x1,x2,...,xn}xik=21xi=2bi1+2bi2,bi1,bi20AAm

Czy to jest ? Czy nadal jest -kompletny?PNP

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

Vor
źródło

Odpowiedzi:

8

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.NPk=2

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

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 .nkkn+2k+mkk2k+m1kk2k+m1

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 .2k+mktt+2k+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+1m

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+m2k+mkn+2k+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 10000 1

3 zostanie zamapowany na i1000 00 1,0100 00 10000 00 01

5 zostanie zmapowany na i .1000 00 000 1,0010 00 000 10000 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.nO(n4)O(n)O(n)O(n2)nn+1 2O(n2)nO(n4)

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ę . nkk2knk=13k2k
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 . kceil(logk)2423231020+32124
Tom van der Zanden,
0

To informacje wyodrębnione z pytania Vora.

Dla k3problem 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=2zobacz szczegóły Toma w odpowiedzi. Oto mała reprezentacja jego redukcji z SUBSET SUM:

wprowadź opis zdjęcia tutaj

Juho
źródło