Czy problem „podzbioru produktu” NP-jest kompletny?

Problem sumy częściowej jest klasycznym problemem NP-zupełnym:

Biorąc pod uwagę listę liczb i docelowy , czy istnieje podzbiór liczb od który sumuje się do ? $L$ $k$ $L$ $k$

Student zapytał mnie, czy ten wariant problemu zwany problemem „produktu podzbioru” jest NP-zupełny:

Biorąc pod uwagę listę liczb i docelowy , czy istnieje podzbiór liczb od którego iloczynem jest ? $L$ $k$ $L$ $k$

Przeszukałem trochę i nie mogłem znaleźć żadnych zasobów, które mówiłyby o tym problemie, chociaż być może brakowało mi ich.

Czy problem z podzespołem NP-zupełny?

complexity-theory np-complete reductions templatetypedef
źródło

Ciekawe odpowiedzi, ale zastanawiam się: czy nie możemy zredukować do sumy podzbiorów, biorąc po prostu logi k i wszystkie liczby? (Może powinienem zadać osobne pytanie?)

j_random_hacker

@ j_random_hacker, tak, jeśli nie możesz znaleźć odpowiedzi po wyszukiwaniu w tej witrynie i online, sugeruję, abyś zamieścił osobne pytanie. To miłe pytanie z ładną odpowiedzią (wskazówka: biorąc dzienniki pozostawia ci coś, co nie jest liczbą całkowitą; w innym kierunku pomyśl o tym, co wykładnik robi na liczbach), ale jest to trochę styczna i byłoby lepiej we własnym pytaniu.

@DW: Dzięki, kiedy będę miał czas, zrobię to, co sugerujesz!

j_random_hacker

Odpowiedzi:

Komentarz wspomina o redukcji z X3C do SUBSET PRODUCT przypisanej Yao. Biorąc pod uwagę cel redukcji, nietrudno było zgadnąć, jaka mogła być redukcja.

Definicje:

DOKŁADNE POKRYCIE 3-ZESTAWÓW (X3C)

Biorąc pod uwagę skończony zbiór z wielokrotnością 3, oraz zbiór podzbiorów 3 elementem , czy zawierają dokładnie pokrywy dla , gdzie i każdy element pojawia się tylko raz w ? $X$ $|X|$ $C$ $X$ $C$ $C'$ $X$ $C' \subseteq C$ $X$ $C'$

PRODUKT PODSETOWY

Biorąc pod uwagę listę liczb i docelowy , czy istnieje podzbiór liczb od którego iloczynem jest ? $L$ $k$ $L$ $k$

Aby zredukować instancję X3C do instancji SUBSET PRODUCT:

Ustanów bijective mapping między elementami i pierwszym liczby pierwsze. Zastąp elementy podzbiorów i zmapowanymi liczbami pierwszymi. $X$ $|X|$ $X$ $C$
Dla każdego podzestawu w pomnóż jego członków razem; wynikowa lista produktów to dla instancji SUBSET PRODUCT. Ponieważ liczby pierwsze są używane do mapowania w kroku 1, gwarantuje się, że produkty są równoważne, jeśli podzbiory są równoważne przez unikalne twierdzenie o rozkładzie na czynniki . $C$ $L$
Pomnóż elementy razem; wynikowy produkt jest wartością dla instancji SUBSET PRODUCT. $X$ $k$

Głównymi czynnikami są dokładnie członkowie . Czynniki pierwsze liczb w odpowiadają dokładnie członom podzbiorów Zatem każde rozwiązanie nowego przykład PODZBIÓR produktu może być przekształcona w roztwór X3C przez odwzorowywanie elementów w roztworze tyłu do podzbiorach . $k$ $X$ $L$ $C$ $L$ $C$

Każdy z 3 etapów transformacji obejmuje operacje wielomianowe względem wielkości danych wejściowych lub rozmiar członek . Pierwszy liczby pierwsze można generować w czasie O ( ) za pomocą sita Eratostenesa i gwarantuje się, że mieszczą się w przestrzeni według twierdzenia o liczbie pierwszej . $|X|$ $X$ $|X|$ $|X|$ $O(|X|^2 \ln |X|)$

Kyle Jones
źródło

+1, ale aby przejść przez redukcję, myślę, że potrzebujemy pierwszego | X | liczby pierwsze mogą być reprezentowane w wielu bitach, które są wielomianowe w | X | - czy mam rację, a jeśli tak, to czy mamy taką gwarancję?

j_random_hacker

Doskonały punkt Dodałem akapit, aby to rozwiązać.

Kyle Jones

Dzięki, to twierdzenie je cementuje! Nie, aby wybrać nitpick, ale zgodnie ze stroną, do której prowadzisz link, k-ta liczba pierwsza wynosi około k log k, a biorąc pod uwagę, że sito Eratostenesa najwyraźniej oblicza wszystkie liczby pierwsze do n w czasie O (n log log n) , zastępując n = k log k wydaje się podawać czas O (k * log (k) * log (log (k log k))), a nie O (k) (twoje O (| X |)), do obliczenia pierwszego k przygotowuje się w ten sposób.

j_random_hacker

Kyle Jones, czy nie jest krytyczne, że krok 3 stworzy liczbę

wielkości wykładniczej? Czy ta redukcja jest rzeczywiście czasem wielomianowym?

k

$k$

user1742364,

k

$k$

k

$k$

| X |

$|X|$

O (n^{2})

$O(n^2)$

k

$k$

P

$P$

X

$X$

k

$k$

O (\log P)

$O(\log P)$

Według [ 1 ]: Tak jest

Przytaczam również to samo odniesienie: Komentarze: Istnieje subtelne techniczne rozróżnienie między tym a Problemem 42: pierwszy przypadek ma pseudoefektywny algorytm uzyskany przez umożliwienie reprezentacji liczb w jedności; chyba że wszystkie problemy NP-zupełne mogą zostać rozwiązane za pomocą szybkich algorytmów, jednak problemu z podzbiorem produktu nie da się rozwiązać metodami „wydajnymi” przy użyciu nawet tej nieuzasadnionej reprezentacji danych wejściowych.

spójrz na [2], aby uzyskać redukcję. [2]: Fellows, Michael i Neal Koblitz. „Złożoność stałych parametrów i kryptografia”. Applied Algebra, Algebraic Algorytmy and Kody korygujące błędy (1993): 121-131.

AJed
źródło

Rzeczywista redukcja lub cytowanie w artykule w czasopiśmie byłoby fajne, jeśli to możliwe.

templatetypedef

@templatetypedef W przypadku Garey i Johnson redukcja dotyczy dokładnej ochrony o 3 zestawy. Ze względu na prywatną komunikację z Yao.

AJed

Zmniejszenie papieru do kryptografii wiąże się z innym problemem, w którym docelowy produkt jest zastępowany przez zgodność z modułem docelowej liczby moduł podanym w instancji. (Chociaż, jeśli dobrze rozumiem dowód, i tak uzyskują słabą twardość, ponieważ moduł ma wykładniczą wielkość.)

Jeffrey Bosboom