Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?

Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym?

Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w którym wybrany zakres liczb jest większy niż , ale te metody nie są dobrze skalowane, aby przypadki o większych rozmiarach i negatywnej w regionie „o wysokiej gęstości”, gdy zakres liczb wybranych jest znacznie mniejsza niż . Tutaj niska gęstość i wysoka gęstość odnosi się do liczby rozwiązań. Region niskiej gęstości odnosi się do niewielu istniejących rozwiązań lub nie ma ich wcale, podczas gdy region wysokiej gęstości odnosi się do regionu z wieloma rozwiązaniami. $2^N$ $2^N$

W obszarze o wysokiej gęstości LLL znajduje (małe) relacje liczb całkowitych między podanymi instancjami, ale wraz ze wzrostem wielkości instancji prawdopodobieństwo znalezienia relacji, która jest wykonalnym rozwiązaniem problemu sumy podzbioru lub podziału partycji, staje się malejące.

Wykrywanie relacji liczb całkowitych jest wielomianowe w granicach wykładniczej granicy optymalnej, podczas gdy podzbiór Suma i NPP są oczywiście NP-Complete, więc na ogół prawdopodobnie nie jest to możliwe, ale jeśli instancja jest losowana równomiernie losowo, czy może to ułatwić?

Czy też nie powinienem nawet zadawać tego pytania, a zamiast tego pytać, czy istnieje sposób na ograniczenie wykładniczej granicy od optymalnej odpowiedzi zamiast wykładniczego wzrostu obliczeń?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum użytkownik834
źródło

Nie otrzymałem żadnych odpowiedzi, więc napisałem na mathoverflow: mathoverflow.net/questions/38063/...

user834

To bardzo interesujące pytanie, czekam też na odpowiedzi. Zasadniczo pytasz o redukcję czasu wielomianowego (być może losowego) z sumy podzbioru lub NPP do relacji liczby całkowitej. Co powiesz na to, jeśli

jest celem twojego problemu z podzbiorem, a

jest zbiorem liczb całkowitych dodatnich, przy czym

jest rozwiązaniem spełniającym

. Jest to dokładnie kombinacja liniowa z rzeczywistymi współczynnikami równymi 1. Jeśli dla każdego

masz to

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

zawsze istnieje rozwiązanie, a odwzorowanie na relację całkowitą da również rozwiązanie.

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

Marcos Villagra,

@Marcos Villagra: twój komentarz jest trochę trudny do przeanalizowania ... problem można osadzić jako problem podziału podzbioru suma / liczba w sieci (patrz tutaj recenzję), pytanie polega na znalezieniu sposobu ograniczenia współczynników do pożądany zestaw (powiedzmy 0,1 lub -1,1). LLL znajdzie relację całkowitą, nawet niewielką, ale tylko jedna 2 lub 3 jako współczynnik unieważni ją jako odpowiedź podziału podzbioru suma / liczba.

user834

Niech m będzie logarytmem największej liczby. Jeśli to można go rozwiązać w czasie wielomianowym za pomocą programowania dynamicznego. Zasadniczo każdy znany algorytm zajmuje co najmniej czasu. Nie jest znany algorytm wielomianu czasu, gdy i $m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

Jednak Flaxman i Przydatek zapewniają algorytm, który rozwiązuje problemy sumy podzbiorów o średniej gęstości w oczekiwanym czasie wielomianowym.

Sprawdź to odniesienie:

Flaxman i Przydatek, Rozwiązywanie problemów sumy podzbiorów średniej gęstości w oczekiwanym czasie wielomianowym

Mohammad Al-Turkistany
źródło

Ten wynik służy tylko do wybrania liczb w wystąpieniu podzbioru znacznie niższych niż chcę. Wybierają zakres liczb w kolejności log (n) ^ 2, natomiast interesuję się zakresem liczb w kolejności od 2 ^ n. Istnieją dobrze znane algorytmy rozwiązywania sumy podzbiorów, gdy zakres liczb jest ograniczony do tak niskiego poziomu i wygląda na to, że nieco rozszerzyli ten zakres, co jest świetne, po prostu nie tego szukałem. Ale dziękuję.

user834

Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?

Odpowiedzi: