Suma podzbiorów a iloczyn podzbiorów (twardość vs. słaba NP)

Miałem nadzieję, że ktoś może mi wyjaśnić, dlaczego dokładnie problem produktu z podzbiorem jest silnie trudny do NP, podczas gdy problem sumy z podzbiorem jest trudny do NP.

Podzbiór Suma: Biorąc pod uwagę, i , czy istnieje podzbiór , tak że . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\sum_{i\in X'}x_i = T$

Podzbiór produktu: Biorąc pod uwagę, i , czy istnieje podzbiór , tak że . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\prod_{i\in X'}x_i = T$

Zawsze uważałem, że dwa problemy są równoważne - instancja SS może zostać przekształcona w instancję SP za pomocą potęgowania, a instancja SP w SS za pomocą logarytmów. Doprowadziło mnie to do wniosku, że oba należały do tej samej klasy NP-twardych - tj. Oba były słabo NP-twarde.

Ponadto wydaje się, że ta sama rekurencja może być wykorzystana do rozwiązania obu problemów za pomocą programowania dynamicznego z bardzo małą zmianą (zastępując odejmowanie w SS dzieleniem w SP).

Tak było, dopóki nie przeczytałem rozdziału 8 „Teorii obliczeń” Bernarda Moreta (dla tych, którzy nie mają książki, ma dowód twardości podzbioru przez X3C - problem silnie NP).

Rozumiem redukcję, ale nie mogę zrozumieć, co było nie tak z moim wcześniejszym wnioskiem (równoważność dwóch problemów).

AKTUALIZACJA : Okazuje się, że produkt podzbioru słabo uzupełnia NP (produkt docelowy jest wykładniczy w ). Gary i Johnson opublikowali to w kolumnie NP-zupełność w 1981 r. , Ale myślę, że było to mniej widoczne niż ich wcześniejsze twierdzenie w ich książce. $\Omega (n)$

cc.complexity-theory np-hardness reductions subset-sum RDN
źródło

Prawdopodobnie dobrze byłoby wyobrazić sobie, jak zaimplementowałbyś algorytm programowania dynamicznego. Wtedy zobaczysz, co było nie tak.

Yoshio Okamoto,

@ MohammadAl-Turkistany: Jest w końcowej części tej kolumny

RDN

Odpowiedzi:

Odnośnie do problemu równoważności sumy podzbioru i produktu podzbioru Istnieją techniczne dane techniczne dotyczące podzbioru produktu. Iloczyn x = T jest faktycznie Psuedopolynomialem, jeśli T nie jest wykładniczy! Tak więc dowody na to, że Subset Product jest NP Hard, nie są (z przyczyn technicznych !!!) całkiem poprawne!

Jednak biorąc pod uwagę obietnicę, że T jest duża, wówczas redukcja za pomocą logarytmów do sumy podzbioru daje NADZWYCZAJNĄ SUMĘ SUBSETOWĄ, która jest ponad rzeczywiste! Oznacza to, że algorytm Psuedopolynomial dla sumy podzbiorów nie ma zastosowania! Chociaż logarytmy są małe, miejsca dziesiętne zaburzają dynamiczne programowanie Psuedopolynomial!

mam nadzieję, że to pomoże

Zelah

Zelah 02
źródło

Okazuje się, że przez cały czas miałeś rację co do niepoprawnych redukcji (tj. Twierdząc, że wykazują one silną kompletność NP, jeśli nie mają). Dzięki!

RDN

Po pierwsze, użycie potęgowania w celu przejścia z SS do SP działa (przy użyciu podstawy 2 zamiast zasady ), ale wysadza rozmiar zaangażowanych liczb. Słaba twardość NP oznacza, że jeśli liczby są małe (a dokładniej oznaczane jako jednoargumentowe), problem nie jest już trudny. Dlatego użycie potęgowania tworzy instancje wielkości SP o wykładniczej wielkości, nawet dla łatwych instancji SS, w których liczby zapisywane są w jedności. $e$

Po drugie, używanie logarytmów do przejścia ze SP do SS nie działa, ponieważ logarytmy zwykle generują wartości niecałkowite. SS i SP są definiowane za pomocą liczb całkowitych, a logarytmy często prowadzą do transcendentalnych wartości, które są trudne do przedstawienia lub wykonania matematyki.

<edit>

Niech będzie liczbą całkowitą, , to jest racjonalny, jeśli i tylko jeśli jest potęgą 2, a transcendentalny w przeciwnym razie. Po pierwsze, jeśli $A$ $A > 0$ $\log_2 A$ $A$ dla niezerowych liczb całkowitychi, a następnie $\log_2 A = \frac{p}{q}$ $p$ $q$ ,. Dlatego mamyprzez rozkład pierwotny. Ponadto, więc punktacjęmożemy odebraćiudowodnićjest racjonalne. $A = 2^{\frac{p}{q}}$ $A^q = 2^p$ $A = 2^r$ $A^{rq} = 2^p$ $A$ $q=1$ $p=r$ $\log_2 A$

Musimy tylko pokazać, że nigdy nie jest transcendentalny inaczej. Wynika to z twierdzenia Gelfonda-Schneidera , ponieważ równoważne sformułowanie (jak można znaleźć na stronie Wiki) brzmi „jeśli i są niezerowymi liczbami algebraicznymi, i przyjmujemy dowolny niezerowy logarytm , to jest albo racjonalny, albo transcendentalny. ” Łatwo to również zweryfikować, biorąc odwrotność twierdzenia i ustawiając a zatem $\log_2 A$ $\alpha$ $\gamma$ $\alpha$ $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ $\alpha^\beta = \gamma$ . $\beta = \log_\alpha \gamma$

</edit>

Na koniec zastanów się, co się stanie, gdy wypróbujemy algorytm programowania dynamicznego z SS na SP. Ponieważ korzystamy z produktów, a nie z sum, dane liczbowe ulegają ogromnemu wysadzeniu, a wymagana matematyka precyzji nagle staje się czynnikiem wpływającym na czas działania. Właśnie dlatego algorytm nie może szybko rozwiązać wystąpień SP, nawet jeśli liczby są jedności.

Alex ten Brink
źródło

prowadzi to do nieco interesującego specjalnego przypadku. bo jaką klasę liczb można wyrazić w logu jako wymierne i niewymagające nieskończonej precyzji? w takim przypadku problemy byłyby rzeczywiście prawie równoważne i można by je było zredukować. wydaje się również prowadzić do „naturalnego” algorytmu aproksymacji.

dniu

Dzięki za świetną odpowiedź! Mam tylko jeden problem - rozumiem, dlaczego pobieranie dzienników jest nielegalne (z wyjątkiem być może przypadków, w których dzienniki mają długość poli - jak wskazuje vzn), ale nadal nie jestem pewien, czy przejście z SS na SP jest legalne przez potęgowanie. WRT przechodząc z SS do SP, jak wspomniałeś (przez potęgowanie), czy nie napotkamy następującego problemu: Liczba bitów w wejściowej instancji

wynosi

i liczba bitów w wystąpieniem

jest

. To jest wykładniczy wzrost. Czy to jest nadal legalne? Jeśli tak, dlaczego?

I_{S S}

$I_{SS}$

O (n \log x)

$O(n\log x)$

I_{S P}

$I_{SP}$

O (n x)

$O(nx)$

RDN

@vzn, RDN: Edytowałem w charakterystyce, gdy logarytm jest transcendentalny. Jeśli chodzi o wybuch w redukcji, zależy to od twojej definicji „legalnej”: redukcja jest poprawna , ale jej skuteczność nie jest wielomianowa, a zatem nie mówi nic o twardości NP. W związku z tym nie jest to poprawna redukcja czasu , ale jest to poprawna redukcja (bez kwalifikacji).

Alex ten Brink

Również nie jest szczególny przypadek, w którym wszystkie liczby są w postaci

, każdy

racjonalne, dla każdej

, nie tylko

. algorytm aproksymacji, o którym myślałem, może znaleźć taki

, że konwersja wartości na tę „bazę” jest „bliska” oryginałom.

c^{n_{i}}

$c^{n_i}$

n_{i}

$n_i$

c

$c$

c = 2

$c=2$

c

$c$

dniu

Dosłowne wyjaśnienie polega na tym, że problem produktu podzbioru jest NP-zupełny przez redukcję z problemu silnie NP-zupełnego, takiego jak dokładna ochrona przez 3 zestawy. W przypadku takiej „silnej” redukcji wejściowe liczby całkowite są ograniczone pewną funkcją wielomianową w liczbie całkowitej w wynikowym wystąpieniu problemu produktu podzbioru.

$P=NP$

Mohammad Al-Turkistany
źródło

Tak rozumiem to. Moje pytanie dotyczyło tego, dlaczego wcześniej wyciągnięty przeze mnie wniosek był niepoprawny (tj. Równoważność SS i SP).

RDN

@rdn W tym sensie nie ma odpowiedników, chyba że P = NP.

Mohammad Al-Turkistany

Tak, rozumiem Ale chcę wiedzieć, co było nie tak z moimi redukcjami w obu kierunkach.

RDN

Czy możesz przedstawić swoje ograniczenia?

Mohammad Al-Turkistany

I (S S) = ⟨ X, S ⟩

$I(SS)=\langle X, S \rangle$

I (S P) = ⟨ Y, P ⟩

$I(SP)=\langle Y, P \rangle$

I (S S)

$I(SS)$

I (S P)

$I(SP)$

P = e^{S}

$P = e^S$

Y_{i} = e^{X_{i}}

$Y_i = e^{X_i}$

S

$S$

P = e^{S}

$P = e^S$

I (S P)

$I(SP)$

I (S S)

$I(SS)$

S = l o g (P)

$S = log(P)$

X_{i} = \log (Y_{i})

$X_i = \log(Y_i)$

P

$P$

S = \log (P)

$S = \log(P)$